论文标题
尽管能力链接未知，但当地任务有效稳定
Ressource Efficient Stabilization for Local Tasks despite Unknown Capacity Links
论文作者
论文摘要
自动化协议使分布式系统从任何任意配置开始恢复正确的行为。特别是，当处理器通过消息传递通信时，可以将伪造的消息放在对手的通信链接中。 When the number of such fake messages is unknown, self-stabilization may require huge resources: (a) generic solutions (a.k.a. data link protocols) require unbounded resources, which makes them unrealistic to deploy and (b) specific solutions (e.g., census or tree construction) require $O(n\log n)$ or $O(Δ\log n)$ bits of memory per node, where $n$ denotes the network size and $δ$其最高度，这可能会阻止可扩展性。 在这种情况下，我们研究了资源有效自动化协议的可能性。具体而言，我们为$（δ+1）$的自动稳定协议（在异步消息传播模型下）中的任何N节点图中的着色。它是确定性的，它在$ o（kδn^2 \ log n）$ seversanges中收敛，其中$ k $是链接容量的限制，并且它在$ o（\ log \ log \ log \ log \ log \ log n+\logΔ）$ bit上使用$ o（Δ\ logu flogu \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log n）$ bits $ bits bits bits bits bits上的消息。因此，我们的协议的资源消耗几乎忽略了节点的数量，从而实现了可伸缩性。此外，我们协议的惊人属性是节点不需要知道最初（可能损坏的）网络配置中每个通信链接中最初存在的消息数量或任何绑定的消息数。这允许我们的协议处理任何未来的网络，并具有未知的消息能力通信链接。我们着色方案的一个关键构建块是一个跨越的无环形构造，它具有独立的兴趣，可以作为在这种挑战性环境中解决其他任务的有用工具。
Self-stabilizing protocols enable distributed systems to recover correct behavior starting from any arbitrary configuration. In particular, when processors communicate by message passing, fake messages may be placed in communication links by an adversary. When the number of such fake messages is unknown, self-stabilization may require huge resources: (a) generic solutions (a.k.a. data link protocols) require unbounded resources, which makes them unrealistic to deploy and (b) specific solutions (e.g., census or tree construction) require $O(n\log n)$ or $O(Δ\log n)$ bits of memory per node, where $n$ denotes the network size and $Δ$ its maximum degree, which may prevent scalability. We investigate the possibility of resource efficient self-stabilizing protocols in this context. Specifically, we present a self-stabilizing protocol for $(Δ+1)$-coloring in any n-node graph, under the asynchronous message-passing model. It is deterministic, it converges in $O(kΔn^2\log n)$ message exchanges, where $k$ is the bound of the link capacity in terms of number of messages, and it uses messages on $O(\log\log n+\logΔ)$ bits with a memory of $O(Δ\logΔ+\log\log n)$ bits at each node. The resource consumption of our protocol is thus almost oblivious to the number of nodes, enabling scalability. Moreover, a striking property of our protocol is that the nodes do not need to know the number, or any bound on the number of messages initially present in each communication link of the initial (potentially corrupted) network configuration. This permits our protocol to handle any future network with unknown message capacity communication links. A key building block of our coloring scheme is a spanning directed acyclic graph construction, that is of independent interest, and can serve as a useful tool for solving other tasks in this challenging setting.
