论文标题
蜂示模型中的时间和空间最佳时钟同步
Time- and Space-Optimal Clock Synchronization in the Beeping Model
论文作者
论文摘要
我们考虑（离散）哔哔声模型中的时钟同步问题：给定每个节点的网络，每个节点都具有时钟值$δ（v）\ in \ {0，\ ldots t-1 \} $，目标是使所有节点的时钟值在任何一轮中都相同。按照时钟同步的标准，我们假设所有节点的\ emph {任意激活}，即节点在任意回合中启动其协议（不限于$ \ {0，\ ldots，t-1 \} $）。我们提供了一种偶然的最佳算法，该算法以$ 4D + \ bigl \ lfloor \ frac {d} {\ lfloor t/4 \ rfloor} \ bigr \ bigr \ rfloor \ cdot（t \ mod 4）= o（t \ mod 4）= o（d）$ found，$ d $ d $ d $ d diamorth。一旦所有节点都同步，它们就会在同一回合中发出每回合。该算法在$ O（t d）$上大大改善了[ACGL'13]的限制（其中$ t $至少为$ 4N $，因此绑定不超过$ o（nd）$）。我们的算法非常简单，因为除了$ \ lceil \ log t \ rceil $位以维护时钟所需的$ \ lceil \ log t \ rceil $位外，节点只需维护$ 3 $。此外，我们研究了时钟同步问题的\ emph {自动稳定}解决方案的复杂性：我们首先在运行时显示$ω（\ max \ {t，n \}）$ roughs的下限和$ω（\ log（\ max \ max \ max \ {t，n \}）$ bits $ bits $ bits $ bits $ bits $ bits $ bits $ bits（\ max \ max \ max \ max \ max \ max \ max \ max（\ max max）。之后，我们提出了一个协议，该协议以$ o（\ max \ {t，n \}）$ rounds运行，最多只能使用$ o（\ log（\ max \ {t，n \}）$ bits $ bits $ bits，在每个节点上，这是均非最佳的，均与符合符号，运行时和内存要求。
We consider the clock synchronization problem in the (discrete) beeping model: Given a network of $n$ nodes with each node having a clock value $δ(v) \in \{0,\ldots T-1\}$, the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume \emph{arbitrary activations} for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to $\{0,\ldots,T-1\}$). We give an asymptotically optimal algorithm that runs in $4D + \Bigl\lfloor \frac{D}{\lfloor T/4 \rfloor} \Bigr \rfloor \cdot (T \mod 4) = O(D)$ rounds, where $D$ is the diameter of the network. Once all nodes are in sync, they beep at the same round every $T$ rounds. The algorithm drastically improves on the $O(T D)$-bound of [ACGL'13] (where $T$ is required to be at least $4n$, so the bound is no better than $O(nD)$). Our algorithm is very simple as nodes only have to maintain $3$ bits in addition to the $\lceil \log T \rceil$ bits needed to maintain the clock. Furthermore we investigate the complexity of \emph{self-stabilizing} solutions for the clock synchronization problem: We first show lower bounds of $Ω(\max\{T,n\})$ rounds on the runtime and $Ω(\log(\max\{T,n\}))$ bits of memory required for any such protocol. Afterwards we present a protocol that runs in $O(\max\{T,n\})$ rounds using at most $O(\log(\max\{T,n\}))$ bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.
