2020/02/13 by Lélia Blin, Blin, Lélia, Anaïs Durand +3
Computer Science · Engineering · #Advanced Data Storage Technologies #Distributed #Distributed Control Multi-Agent Systems #Distributed systems and fault tolerance #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2002.05382
openalex publication_date 2020/02/13 · openalex created_date 2022/01/25 · openalex updated_date 2026/07/28
Self-stabilizing protocols enable distributed systems to recover correct\nbehavior starting from any arbitrary configuration. In particular, when\nprocessors communicate by message passing, fake messages may be placed in\ncommunication links by an adversary. When the number of such fake messages is\nunknown, self-stabilization may require huge resources: (a) generic solutions\n(a.k.a. data link protocols) require unbounded resources, which makes them\nunrealistic to deploy and (b) specific solutions (e.g., census or tree\nconstruction) require O(n\log n) or O(\Δ\log n) bits of memory per\nnode, where n denotes the network size and \Δ its maximum degree, which\nmay prevent scalability.\n We investigate the possibility of resource efficient self-stabilizing\nprotocols in this context. Specifically, we present a self-stabilizing protocol\nfor (\Δ+1)-coloring in any n-node graph, under the asynchronous\nmessage-passing model. It is deterministic, it converges in O(k\Δ n2\log\nn) message exchanges, where k is the bound of the link capacity in terms of\nnumber of messages, and it uses messages on O(\log\log n+\log\Δ) bits\nwith a memory of O(\Δ\log\Δ+\log\log n) bits at each node. The\nresource consumption of our protocol is thus almost oblivious to the number of\nnodes, enabling scalability. Moreover, a striking property of our protocol is\nthat the nodes do not need to know the number, or any bound on the number of\nmessages initially present in each communication link of the initial\n(potentially corrupted) network configuration. This permits our protocol to\nhandle any future network with unknown message capacity communication links. A\nkey building block of our coloring scheme is a spanning directed acyclic graph\nconstruction, that is of independent interest, and can serve as a useful tool\nfor solving other tasks in this challenging setting.\n