2019/06/21 by Bernadette Charron-Bost, Charron-Bost, Bernadette, Shlomo Moran +1
Computer Science · #Distributed #Distributed Control Multi-Agent Systems #Distributed systems and fault tolerance #FOS: Computer and information sciences #Mobile Agent-Based Network Management #Opportunistic and Delay-Tolerant Networks #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1906.09073
openalex publication_date 2019/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the stabilizing consensus problem, each agent of a networked system has an input value and is repeatedly writing an output value; it is required that eventually all the output values stabilize to the same value which, moreover, must be one of the input values. We study this problem for a synchronous model with identical and anonymous agents that are connected by a time-varying topology. Our main result is a generic MinMax algorithm that solves the stabilizing consensus problem in this model when, in each sufficiently long but bounded period of time, there is an agent, called a root, that can send messages, possibly indirectly, to all the agents. Such topologies are highly dynamic (in particular, roots may change arbitrarily over time) and enforce no strong connectivity property (an agent may be never a root). Our distributed MinMax algorithms require neither central control (e.g., synchronous starts) nor any global information (eg.,on the size of the network), and are quite efficient in terms of message size and storage requirements.