We consider the fundamental problem of clock synchronization in a synchronous multi-agent system. Each agent holds a clock with an arbitrary initial value, and clocks must eventually indicate the same value. Previous algorithms worked in static networks with drastic connectivity properties and assumed that global information is available at each agent. In this paper, we propose different solutions for time-varying topologies that require neither strong connectivity nor any global knowledge on the network. First, we study the case of unbounded clocks, and propose a self-stabilizing $MinMax$ algorithm that works if, in each sufficiently long but bounded period of time, there is an agent, called a root, that can send messages, possibly indirectly, to all other agents. Such networks are highly dynamic in the sense that roots may change arbitrarily over time. Moreover, the bound on the time required for achieving this rootedness property is unknown to the agents. Then we present a finite-state algorithm that synchronizes periodic clocks in dynamic networks that are strongly connected over bounded period of time. Here also, the bound on the time for achieving strong connectivity exists, but is not supposed to be known. Interestingly, our algorithm unifies several seemingly different algorithms proposed previously for static networks. Next, we show that strong connectivity is actually not required: our algorithm still works when the network is just rooted over bounded period of time with a set of roots that becomes stable. Finally, we study the time and space complexities of our algorithms, and discuss how initial timing information allows for more efficient solutions.

翻译：我们考虑的是同步多试剂系统中的时钟同步这一根本问题。 每个代理商持有一个带有任意初始值的时钟, 并且时钟最终必须显示相同的值。 以前的算法在静态网络中运作, 具有巨大的连通性, 并假定每个代理商都有全球信息。 在本文中, 我们为时间变化的表层提出了不同的解决方案, 既不需要强大的连通性, 也不需要网络上的任何全球知识。 首先, 我们研究无线时钟的情况, 并提议一个自稳定 $Minmax$的算法, 如果在足够长但受约束的时期内, 有一个代理商, 叫做根, 可以间接地向所有其他代理商发送信息。 这些网络具有高度的动态性, 因为根基可能随时间变化而变化。 此外, 实现这一根基属性所需的时间被限制在时间上。 然后我们提出一个固定的算法, 在动态网络中同步的时钟会同步, 并且密切连接在受约束的时期里拉。 这里, 一个固定的时段, 我们的算法最终会显示我们是如何固定的周期。