Search

Your search keyword '"Binary consensus"' showing total 16 results
Start Over Descriptor "Binary consensus" Language english
16 results on '"Binary consensus"'

1. Hybrid binary consensus in anonymous asynchronous systems using coins and failure detectors.

Author

Jiménez, Ernesto, López-Presa, José Luis, and Martín-Rueda, Javier

Subjects
*COINS, *DETECTORS, *FAULT-tolerant control systems, *NUMBER systems, *FAULT-tolerant computing
Abstract

Fault tolerance and agreement are essential capabilities of current distributed systems. In this context, Binary Consensus is a key problem. It is well-known that consensus cannot be solved in a pure asynchronous system when at least one process can crash. To overcome this impossibility result, the asynchronous system is usually augmented with randomization, failure detectors or some kind of synchronization. Random binary consensus in classic asynchronous systems is usually solved using a common coin to achieve a constant expected number of rounds. However, to our knowledge, the literature lacks the existence of common coin algorithms for anonymous asynchronous systems. In this paper, an implementation of a common coin that runs on anonymous asynchronous systems is proposed and it is proved that the probability that this common coin gives the same outcome to all processes is bigger than 0.75 with small bias. This result allows to solve random consensus, in anonymous asynchronous systems, in four expected rounds, independently of the number of processes in the system. The main result of this paper is a hybrid (deterministic/random) binary consensus algorithm which solves consensus in anonymous asynchronous systems enriched with a common coin and a failure detector of class A Ω ′ , where less than half of the processes may fail, which is an optimal bound on the number of failures. To our knowledge, this is the first such algorithm. It only needs a quadratic number of interchanged messages per round, and the size of these messages is minimal (O(1) bytes). Consensus is achieved in one round by our hybrid algorithm if the failure detector does not make any errors or all processes propose the same value, and in four expected rounds if the adversary does not control the common coin. Additionally, we conducted an experimental evaluation whose results agree with the expected ones and slightly improve them. In particular, above 95% of the times, all processes get the same outcome from the coin, and random consensus is achieved in less than two rounds on average with very small standard deviation. This makes our algorithms good candidates for deployment in practical distributed systems. [ABSTRACT FROM AUTHOR]

Published
2019
Full Text
View/download PDF

2. Randomized Binary Consensus with Faulty Agents

Author

Alexander Gogolev and Lucio Marcenaro

Subjects
binary consensus, randomized consensus, self-organizing systems, faulty agents, Byzantine failure, density classification, Science, Astrophysics, QB460-466, Physics, QC1-999
Abstract

This paper investigates self-organizing binary majority consensus disturbed by faulty nodes with random and persistent failure. We study consensus in ordered and random networks with noise, message loss and delays. Using computer simulations, we show that: (1) explicit randomization by noise, message loss and topology can increase robustness towards faulty nodes; (2) commonly-used faulty nodes with random failure inhibit consensus less than faulty nodes with persistent failure; and (3) in some cases, such randomly failing faulty nodes can even promote agreement.

Published
2014
Full Text
View/download PDF

3. Implementation, validation and experimental evaluation of a self-stabilizing randomized Byzantine-tolerant binary consensus algorithm

Author

Demetriou, Constandinos, Georgiou, Chryssis, Marcoullis, Ioannis, Philippou, Anna, Πανεπιστήμιο Κύπρου, Σχολή Θετικών και Εφαρμοσμένων Επιστημών, Τμήμα Πληροφορικής, University of Cyprus, Faculty of Pure and Applied Sciences, Department of Computer Science, and Georgiou, Chryssis [0000-0003-4360-0260]

Subjects
BINARY CONSENSUS, DISTRIBUTED SYSTEMS, SELF-STABILIZATION, BYZANTINE FAULT-TOLERANCE, RANDOMIZATION
Abstract

Binary consensus is a problem in which a set of processors must agree on a single binary value. In asynchronous systems, where a subset of the processors may be malicious, this challenge gets more challenging. We study malicious and more serious problems in this work: transient faults. These are temporary violations of the system's operating assumptions that might cause the system's state to change unexpectedly, making recovery impossible without human intervention. We implement an existing protocol for randomized Byzantine-tolerant binary consensus algorithm that is loosely-self-stabilizing using the Go programming language and the ZeroMQ communication framework. This approach is optimal in terms of resilience and termination, requires only bounded memory, and ensures that the system will automatically converge to a legal state. This is the first time-free Byzantine-tolerant binary consensus algorithm to make such guarantees, to our knowledge. We describe the first known implementation of this algorithm in this work. With this implementation, we were able to: (a) validate the algorithm; (b) compare the algorithm to its non-stabilizing version and estimate the cost of self-stabilization in terms of processing time and message load; and (c) notice that different failures in the system (whether due to transient faults or malicious behavior) have no significant overhead on recovery and decision time.

Published
2022

4. Reaching consensus on a binary state by exchanging binary actions.

Author

Wang, Yunlong and Djuric, Petar M.

Abstract

In this paper, we study the problem of distributed hypothesis testing in cooperative networks of agents. All agents are trying to reach consensus on the state of nature by their private signals and the binary actions of their neighbors. This is a challenging problem because the exchanged information of the agents is highly compressed. We propose a gossip-type method where every agent's decision converges in probability to the optimal decision held by a fictitious fusion center. We prove the asymptotical property of the proposed method and provide simulation results that demonstrate the communication cost and convergence time of the method. [ABSTRACT FROM PUBLISHER]

Published
2012
Full Text
View/download PDF

5. Randomized Binary Consensus with Faulty Agents.

Author

Gogolev, Alexander and Marcenaro, Lucio

Subjects
*FAULT location (Engineering), *SELF-organizing systems, *SYSTEM failures, *RANDOM variables, *COMPUTER simulation, *CLASSIFICATION algorithms
Abstract

This paper investigates self-organizing binary majority consensus disturbed by faulty nodes with random and persistent failure. We study consensus in ordered and random networks with noise, message loss and delays. Using computer simulations, we show that: (1) explicit randomization by noise, message loss and topology can increase robustness towards faulty nodes; (2) commonly-used faulty nodes with random failure inhibit consensus less than faulty nodes with persistent failure; and (3) in some cases, such randomly failing faulty nodes can even promote agreement. [ABSTRACT FROM AUTHOR]

Published
2014
Full Text
View/download PDF

6. On the compression of locational and environmental data in multi-vehicle missions: a control systems approach.

Author

Luna, José Marcio, Fierro, Rafael, Abdallah, Chaouki Tanios, and Lewis, Frank

Subjects
*CONTROL theory (Engineering), *MOBILE agent systems, *AUTOMATIC control systems, *INFORMATION sharing, *ELECTRIC interference, *DIGITAL communications, *ERROR analysis in mathematics, *SIMULATION methods & models
Abstract

Mobile agents that take part in multi-vehicle missions usually need to share environmental and locational information with other agents and with control stations through a communication channel. In real scenarios, the agents have to deal with different communication issues, such as interference, loss of connectivity and unexpected reduction of available bandwidth. One way to overcome these issues is by minimising the amount of data in the communication channel, which not only speeds up the sharing of information, but would also avoid the loss of data. We propose a control systems approach that allows the compression of the shared information. Given some problem-dependent mathematical assumptions, our method aims to simplify the calculation of the stationary errors by computing the sign of the errors rather than their exact values and the control law may then be used to stabilise the system. The approach allows for the compression of the outputs involved in the calculation of the errors as such outputs represent the shared information among agents. We carry out the theoretical analysis of our approach and apply it to two case studies, namely a formation control and a coverage control with consensus. We finally validate our theoretical results through simulations in Matlab. [ABSTRACT FROM AUTHOR]

Published
2013
Full Text
View/download PDF

7. A Gossip Method for Optimal Consensus on a Binary State From Binary Actions.

Author

Wang, Yunlong and Djuric, Petar M.

Abstract

In this paper, we study the problem of distributed hypothesis testing in cooperative networks of agents over a given undirected graph. All the agents try to reach consensus on the state of nature based on their private signals and the binary actions of their neighbors. This is a challenging problem because the exchanged information of the agents regarding their observations used for making decisions is highly compressed. We propose a set of gossip-type methods for which two communicating agents reach the optimal local consensus with probability one by a few exchanges of binary actions at every time slot. We prove that the decision of each agent converges in probability to the optimal decision held by a fictitious fusion center. We also provide theoretical results on how the edge selection probability effects the expected time at which a consensus of all the agents is reached. Simulation results that demonstrate the communication cost and the convergence time of the method are provided. [ABSTRACT FROM PUBLISHER]

Published
2013
Full Text
View/download PDF

8. Binary Consensus Over Fading Channels.

Author

Mostofi, Yasamin and Malmirchegini, Mehrzad

Subjects
*RADIO transmitter fading, *WIRELESS communications, *WIRELESS sensor networks, *COMPUTER network protocols, *SIGNAL processing, *PERFORMANCE evaluation, *ELECTRONIC surveillance, *GRAPH theory
Abstract

In this paper, we consider a cooperative network that is trying to reach consensus on the occurrence of an event, by communicating over time-varying network topologies with fast fading channels. We mathematically characterize both the asymptotic and transient behaviors of the network. We show that the network converges to a memoryless state asymptotically, which is undesirable. However, the network can still be in consensus for a long period of time. In order to characterize the transient behavior, we then derive a tight approximation for the second largest eigenvalue of the underlying average probability transition matrix in fading environments. We show the impact of channel unreliability and network topology on consensus performance and shed light on the underlying tradeoffs in terms of speed of convergence and memoryless asymptotic behavior. [ABSTRACT FROM AUTHOR]

Published
2010
Full Text
View/download PDF

9. A New Insight into Local Coin-Based Randomized Consensus

Author

Michel Raynal, Matthieu Perrin, Achour Mostefaoui, Gestion de Données Distribuées [Nantes] (GDD), Laboratoire d'Informatique de Nantes Atlantique (LINA), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), Gestion de Données Distribuées (GDD), Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), The Hong Kong Polytechnic University [Hong Kong] (POLYU), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Gestion de Données Distribuées (LS2N - équipe GDD), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), and ANR-16-CE25-0005,OBrowser,Applications décentralisées sur navigateurs(2016)

Subjects
Consensus algorithm, 021110 strategic, defence & security studies, Theoretical computer science, Computer science, 0211 other engineering and technologies, Binary number, Process crash failure, 0102 computer and information sciences, 02 engineering and technology, Binary consensus, Local coin, 01 natural sciences, Message- passing asynchronous system, 010201 computation theory & mathematics, Asynchronous communication, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Constant (mathematics), Condition, ComputingMilieux_MISCELLANEOUS
Abstract

This paper presents a binary randomized consensus algorithm for n-process asynchronous message-passing systems in which (1) up to t O(sqrt(n)) it is no longer possible to implement a randomized consensus algorithm ensuring a constant number of communication steps despite unfair channels.

Published
2019
Full Text
View/download PDF

10. One for All and All for One: Scalable Consensus in a Hybrid Communication Model

Author

Jiannong Cao, Michel Raynal, the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Department of computing [Hong Kong], Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)

Subjects
Consensus algorithm, Theoretical computer science, Computer science, Modularity, Context (language use), 0102 computer and information sciences, 02 engineering and technology, Binary consensus, Local coin, 01 natural sciences, Message-passing, 0202 electrical engineering, electronic engineering, information engineering, Atomic register, Asynchronous system, Cluster analysis, ComputingMilieux_MISCELLANEOUS, Message passing, Scalability, Hybrid communication, Process crash failure, Compare-and-swap, Shared memory, Compare and swap, 010201 computation theory & mathematics, Asynchronous communication, Cluster, Models of communication, 020201 artificial intelligence & image processing, Common coin, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

This paper addresses consensus in an asynchronous model where the processes are partitioned into clusters. Inside each cluster, processes can communicate through a shared memory, which favors efficiency. Moreover, any pair of processes can also communicate through a message-passing communication system, which favors scalability. In such a "hybrid communication" context, the paper presents two simple binary consensus algorithms (one based on local coins, the other one based on a common coin). These algorithms are straightforward extensions of existing message-passing randomized round-based consensus algorithms. At each round, the processes of each cluster first agree on the same value (using an underlying shared memory consensus algorithm), and then use a message-passing algorithm to converge on the same decided value. The algorithms are such that, if all except one processes of a cluster crash, the surviving process acts as if all the processes of its cluster were alive (hence the motto "one for all and all for one"). As a consequence, the hybrid communication model allows us to obtain simple, efficient, and scalable fault-tolerant consensus algorithms. As an important side effect, according to the size of each cluster, consensus can be obtained even if a majority of processes crash.

Published
2019
Full Text
View/download PDF

11. Patrolling on Dynamic Ring Networks

Author

Shantanu Das, Leszek Gasieniec, Giuseppe Antonio Di Luna, Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Algorithmique Distribuée (DALGO), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Liverpool], and University of Liverpool

Subjects
FOS: Computer and information sciences, Ring (mathematics), Matching (graph theory), business.industry, Computer science, Unit of time, Patrolling, Node (networking), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Network protocols, Distributed computer systems, Binary consensus, 01 natural sciences, Idle time, Set (abstract data type), Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Computer network
Abstract

International audience; We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every I(n) time units, with the objective of minimizing the idle time I(n). While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for k = 2 or k > 2 agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs.

Published
2019
Full Text
View/download PDF

12. Compacting and grouping mobile agents on dynamic rings

Author

Giuseppe Prencipe, Shantanu Das, Linda Pagli, Giuseppe Antonio Di Luna, Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix-Marseille Université - Faculté des Sciences (AMU SCI), Aix Marseille Université (AMU), Algorithmique Distribuée (DALGO), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 050101 languages & linguistics, Ring (mathematics), Computer science, Node (networking), Computation, 05 social sciences, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Ring network, 02 engineering and technology, Binary consensus, Topology, Network protocols, Distributed computer systems, ComputingMethodologies_ARTIFICIALINTELLIGENCE, Computer Science::Multiagent Systems, Set (abstract data type), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, Monochromatic color, Host (network), ComputingMilieux_MISCELLANEOUS
Abstract

We consider computations by a distributed team of autonomous mobile agents that move on an unoriented dynamic ring network. In particular, we consider 1-interval connected dynamic rings (i.e. at any time, at most one of the edges might be missing). The agents move according to a Look-Compute-Move life cycle, under a synchronous scheduler. The agents may be homogenous (thus identical and monochromatic) or they may be heterogenous (distinct agents have distinct colors from a set of \(c \ge 1\) colors). For monochromatic agents starting from any dispersed configuration we want the agents to form a compact segment, where agents occupy a continuous part of the ring and no two agents are on the same node – we call this the Compact Configuration Problem. In the case of multiple colors (\(c>1\)), agents of the same color are required to occupy continuous segments, such that agents having the same color are all grouped together, while agents of distinct colors are separated. These formation problems are different from the classical and well studied problem of Gathering all agents at a node, since unlike the gathering problem, we do not allow collisions (each node may host at most one agent of a color).

Published
2019
Full Text
View/download PDF

14. On the Power of Weaker Pairwise Interaction: Fault-Tolerant Simulation of Population Protocols

Author

Taisuke Izumi, Tomoko Izumi, Giovanni Viglietta, Nicola Santoro, Giuseppe Antonio Di Luna, and Paola Flocchini

Subjects
FOS: Computer and information sciences, education.field_of_study, Hierarchy, Theoretical computer science, Pairwise interaction, Computer science, Distributed computing, Population, Fault tolerance, 0102 computer and information sciences, 02 engineering and technology, Binary consensus, Network protocols, Distributed computer systems, 01 natural sciences, Power (physics), Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), Focus (optics), education
Abstract

In this paper we investigate the computational power of Population Protocols (PP) under some unreliable and/or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. An omission failure, a notion that this paper introduces for the first time in the context of PP, is the loss by one or both parties of the information transmitted in an interaction. The failure may or may not be detected by either party. On the other hand, in one-way models, communication happens only in one direction: only one of the two agents can change its state depending on both agents' states, and the other agent may or may not be aware of the interaction. These notions can be combined, obtaining one-way protocols with (possibly detectable) omission failures. A general question is what additional power is necessary and sufficient to completely overcome the weakness of one-way protocols and enable them to simulate two-way protocols, with and without omission failures. As a basic feature, a simulator needs to implement an atomic communication of states between two agents; this task is further complicated by the anonymity of the agents, their lack of knowledge of the system, and the limited amount of memory that they may have. We provide the first answers to these questions by presenting and analyzing several simulators, i.e., wrapper protocols converting any protocol for the standard two-way model into one running on a weaker one.

Published
2017

15. Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages

Author

Amos Korman, Emanuele Natale, Lucas Boczkowski, Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centre National de la Recherche Scientifique (CNRS), Université Côte d'Azur (UCA), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)

Subjects
education.field_of_study, Theoretical computer science, Computer science, Population, Self-stabilization, 0102 computer and information sciences, 02 engineering and technology, Network protocols, Distributed computer systems, Binary consensus, 01 natural sciences, Clock synchronization, Atomic broadcast, Terminating Reliable Broadcast, Consensus, 010201 computation theory & mathematics, Asynchronous communication, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], education, Dissemination, ComputingMilieux_MISCELLANEOUS
Abstract

This paper is motivated by the aspiration to identify the weakest computational models that allow for efficient, robust distributed computation. We focus on one of the most fundamental building-blocks in distributed computing, namely, Broadcast. In this problem, a unique source agent $s$ needs to disseminate a bit $b$ to the rest of the population. To account for unpredictability issues that may result from uncoordinated executions, we consider a self-stabilizing setting, in which a correct configuration must be reached eventually, despite processors starting the execution with arbitrary initial states (that do not violate the requirement for the existence of a unique source). Similarly to many works on broadcast, we consider a synchronous communication model on a complete anonymous network, in which in each round, each agent can extract information from two other agents, chosen uniformly at random. Our focus is on identifying the smallest message size that is required in order to achieve fast self-stabilizing broadcast. We first observe that with an extra bit added to the message-size and a small additive penalty to the running time, the self-stabilizing broadcast problem can be reduced to a self-stabilizing clock-synchronization problem, where agents aim to synchronize their clocks modulo some integer T. Our main technical contribution lies in solving the latter problem in poly-logarithmic time using only 3 bits per interaction. This allows for a self-stabilizing broadcast protocol that uses only 4 bits per interaction and converges in O log n time.

Published
2016
Full Text
View/download PDF

16. Stably decidable graph languages by mediated population protocols

Author

Ioannis Chatzigiannakis, Paul G. Spirakis, and Othon Michail

Subjects
Discrete mathematics, Computer science, binary consensus, Comparability graph, Directed graph, distributed computer systems, law.invention, network protocols, Pathwidth, law, Line graph, Graph property, Null graph, Algorithm, Complement graph, Forbidden graph characterization
Abstract

We work on an extension of the Population Protocol model of Angluin et al. that allows edges of the communication graph, G, to have states that belong to a constant size set. In this extension, the so called Mediated Population Protocol model (MPP), both uniformity and anonymity are preserved. We study here a simplified version of MPP in order to capture MPP's ability to stably compute graph properties. To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph property is not computable if we allow disconnected communication graphs. As a result, we focus on studying (at least) weakly connected communication graphs only and give several examples of computable properties in this case. To do so, we also prove that the class of computable properties is closed under complement, union and intersection operations. Node and edge parity, bounded out-degree by a constant, existence of a node with more incoming than outgoing neighbors, and existence of some directed path of length at least k = O(1) are some examples of properties whose computability is proven. Finally, we prove the existence of symmetry in two specific communication graphs and, by exploiting this, we prove that there exists no protocol, whose states eventually stabilize, to determine whether G contains some directed cycle of length 2.

Published
2010

Catalog

Books, media, physical & digital resources
See catalog results