Search

Your search keyword '"k-Set agreement"' showing total 14 results
Start Over Descriptor "k-Set agreement" Search Limiters Available in Library Collection
14 results on '"k-Set agreement"'

1. Solving k-Set Agreement Using Failure Detectors in Unknown Dynamic Networks.

Author

Jeanneau, Denis, Rieutord, Thibault, Arantes, Luciana, and Sens, Pierre

Subjects
*DYNAMICAL systems, *STANDARDS, *ALGORITHMS, *COMMUNICATION, *GRAPHIC methods
Abstract

The failure detector abstraction has been used to solve agreement problems in asynchronous systems prone to crash failures, but so far it has mostly been used in static and complete networks. This paper aims to adapt existing failure detectors in order to solve agreement problems in unknown, dynamic systems. We are specifically interested in the k-set agreement problem. The problem of k-set agreement is a generalization of consensus where processes can decide up to k different values. Although some solutions to this problem have been proposed in dynamic networks, they rely on communication synchrony or make strong assumptions on the number of process failures. In this paper we consider unknown dynamic systems modeled using the formalism of Time-Varying Graphs, and extend the definition of the existing \Pi \Sigma x,y failure detector to obtain the \Pi \Sigma \bot, x,y failure detector, which is sufficient to solve k-set agreement in our model. We then provide an implementation of this new failure detector using connectivity and message pattern assumptions. Finally, we present an algorithm using \Pi \Sigma \bot, x,y to solve k-set agreement. [ABSTRACT FROM AUTHOR]

Published
2017
Full Text
View/download PDF

2. Distributed computability: Relating k-immediate snapshot and x-set agreement.

Author

Delporte, Carole, Fauconnier, Hugues, Rajsbaum, Sergio, and Raynal, Michel

Abstract

This paper introduces a generalization of the immediate snapshot object denoted k-immediate snapshot, requiring that the snapshot returned contains at least (n − k) pairs. The case k = n − 1 corresponds to the original immediate snapshot object, which requires that the snapshot returned contains at least one pair 〈process id, value〉 pair, that corresponds to the process id that invoked the operation). The paper first shows that k -immediate snapshot is impossible to implement in an asynchronous read/write system, even if k = n − 2 and t = 1. Then, the paper considers x -set agreement, another object stronger than the classical read/write t -crash read/write model (when x ≤ t), and studies the relation with the k -immediate snapshot object, establishing strong relations linking these two fundamental distributed computing abstractions. The paper shows conditions under which x -set agreement can be solved in read/write systems enriched with k -immediate snapshot objects. It also shwos when k -immediate snapshot and consensus are equivalent. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

3. Solving k-Set Agreement Using Failure Detectors in Unknown Dynamic Networks

Author

Pierre Sens, Thibault Rieutord, Luciana Arantes, Denis Jeanneau, Sens, Pierre, Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Département Informatique et Réseaux (INFRES), Télécom ParisTech, Labex SMART, supported by French state funds managed by the ANR within the Investissements d’Avenir programmeunder reference ANR-11-LABX-65., and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, 020203 distributed computing, K-set, Dynamic networks, Computer science, Detector, Failure detectors, k-Set agreement, 0102 computer and information sciences, 02 engineering and technology, Distributed systems, 01 natural sciences, Formalism (philosophy of mathematics), Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Asynchronous communication, Signal Processing, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Failure detector, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm
Abstract

The failure detector abstraction has been used to solve agreement problems in asynchronous systems prone to crash failures, but so far it has mostly been used in static and complete networks. This paper aims to adapt existing failure detectors in order to solve agreement problems in unknown, dynamic systems. We are specifically interested in the k-set agreement problem. The problem of k-set agreement is a generalization of consensus where processes can decide up to k different values. Although some solutions to this problem have been proposed in dynamic networks, they rely on communication synchrony or make strong assumptions on the number of process failures. In this paper we consider unknown dynamic systems modeled using the formalism of Time-Varying Graphs, and extend the definition of the existing $\Pi \Sigma _{x,y}$ failure detector to obtain the $\Pi \Sigma _{\bot, x,y}$ failure detector, which is sufficient to solve k-set agreement in our model. We then provide an implementation of this new failure detector using connectivity and message pattern assumptions. Finally, we present an algorithm using $\Pi \Sigma _{\bot, x,y}$ to solve k-set agreement.

Published
2017
Full Text
View/download PDF

4. k-Set Agreement and Renaming in the Presence of Contention-Related Crash Failures

Author

Michel Raynal, Gadi Taubenfeld, Anaïs Durand, 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 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), 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 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), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), The Hong Kong Polytechnic University [Hong Kong] (POLYU), Interdisciplinay Center Herzliya - Israel (IDC), Interdisciplinay Center Herzliya, 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-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016)

Subjects
Correctness, Renaming, Concurrency, l-Mutual exclusion, Crash, 0102 computer and information sciences, k-Set agreement, Contention, Lambda, 01 natural sciences, Set (abstract data type), 03 medical and health sciences, 0302 clinical medicine, Atomic register, Asynchronous system, Impossibility, Agreement algorithm, Mathematics, Discrete mathematics, Read/write register, Process crash failure, 16. Peace & justice, 010201 computation theory & mathematics, Asynchronous communication, 030220 oncology & carcinogenesis, Participating process, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; A new notion of process failure explicitly related to contention has recently been introduced by one of the authors (NETYS 2018). More precisely, given a predefined contention threshold λ, this notion considers the executions in which process crashes are restricted to occur only when process contention is smaller than or equal to λ. If crashes occur after contention bypassed λ, there are no correctness guarantees (e.g., termination is not guaranteed). It was shown that, when λ = n − 1, consensus can be solved in an n-process asynchronous read/write system despite the crash of one process, thereby circumventing the well-known FLP impossibility result. Furthermore, it was shown that when λ = n − k and k ≥ 2, k-set agreement can be solved despite the crash of 2k − 2 processes. This paper considers two types of process crash failures: "λ-constrained" crash failures (as previously defined), and classical crash failures (that we call "any time" failures). It presents two algorithms suited to these types of failures. The first algorithm solves k-set agreement, where k = m+f , in the presence of t = 2m + f − 1 crash failures, 2m of them being (n − k)-constrained failures, and (f − 1) being any time failures. The second algorithm solves (n + f)-renaming in the presence of t = m + f crash failures, m of them being (n − t − 1)-constrained failures, and f being any time failures. It follows that the differentiation between λ-constrained crash failures and any time crash failures enlarges the space of executions in which the impossibility of k-set agreement and renaming in the presence of asynchrony and process crashes can be circumvented. In addition to its behavioral properties, both algorithms have a noteworthy first class property, namely, their simplicity.

Published
2018
Full Text
View/download PDF

5. Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems

Author

Hammurabi Mendes and Maurice Herlihy, Mendes, Hammurabi, Herlihy, Maurice, Hammurabi Mendes and Maurice Herlihy, Mendes, Hammurabi, and Herlihy, Maurice

Abstract

In this paper, we show that the protocol complex of a Byzantine synchronous system can remain (k-1)-connected for up to ceil(t/k) rounds, where t is the maximum number of Byzantine processes, and t >= k >= 1. This topological property implies that ceil(t/k) + 1 rounds are necessary to solve k-set agreement in Byzantine synchronous systems, compared to floor(t/k) + 1 rounds in synchronous crash-failure systems. We also show that our connectivity bound is tight as we indicate solutions to Byzantine k-set agreement in exactly ceil(t/k) + 1 synchronous rounds, at least when n is suitably large compared to t. In conclusion, we see how Byzantine failures can potentially require one extra round to solve k-set agreement, and, for n suitably large compared to t, at most that.

Published
2017
Full Text
View/download PDF

6. k-Set Agreement in Communication Networks with Omission Faults

Author

Emmanuel Godard and Eloi Perdereau, Godard, Emmanuel, Perdereau, Eloi, Emmanuel Godard and Eloi Perdereau, Godard, Emmanuel, and Perdereau, Eloi

Abstract

We consider an arbitrary communication network G where at most f messages can be lost at each round, and consider the classical k-set agreement problem in this setting. We characterize exactly for which f the k-set agreement problem can be solved on G. The case with k = 1, that is the Consensus problem, has first been introduced by Santoro and Widmayer in 1989, the characterization is already known from [Coulouma/Godard/Peters, TCS, 2015]. As a first contribution, we present a detailed and complete characterization for the 2-set problem. The proof of the impossibility result uses topological methods. We introduce a new subdivision approach for these topological methods that is of independent interest. In the second part, we show how to extend to the general case with k in N. This characterization is the first complete characterization for this kind of synchronous message passing model, a model that is a subclass of the family of oblivious message adversaries.

Published
2017
Full Text
View/download PDF

7. t-Resilient Immediate Snapshot Is Impossible

Author

Carole Delporte, Sergio Rajsbaum, Hugues Fauconnier, Michel Raynal, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-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)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-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)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), 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), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Raynal, Michel, 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.), 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)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-CentraleSupélec-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)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec, and DELPORTE-GALLET, CAROLE

Subjects
Theoretical computer science, Linearizability, Consensus, t-resilience, Computer science, Distributed computabil-ity, Crash, 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], 01 natural sciences, Shared memory, Iterated model, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO]Computer Science [cs], Asynchronous system, Impossibility, Immediate snapshot, k-Set Agreement, Snapshot object, Process crash failure, 020207 software engineering, Atomic read/write register, ACM: F.: Theory of Computation, 010201 computation theory & mathematics, Wait-freedom, Snapshot (computer storage), Process identifier, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

Immediate snapshot is the basic communication object on which relies the read/write distributed computing model made up of n crash-prone asynchronous processes, called iterated distributed model. Each iteration step (usually called a round) uses a new immediate snapshot object, which allows the processes to communicate and cooperate. More precisely, the x-th immediate snapshot object can be used by a process only when it executes the x-th round. An immediate snapshot object can be implemented by an (n − 1)-resilient algorithm, i.e. an algorithm that tolerates up to (n − 1) process crashes (also called wait-free algorithm). Considering a t-crash system model (i.e. a model in which up to t processes are allowed to crash), this paper is on the construction of an extension of immediate snapshot objects to t-resiliency. In the t-crash system model, at each round each process may be ensured to get values from at least n − t processes, and t-immediate snapshot has the properties of classical immediate snapshot (1-immediate snapshot) but ensures that each process will get values form at least n − t processes. Its main result is the following. While there is a (deterministic) t-resilient read/write-based algorithm implementing t-immediate snapshot in a t-crash system when t = n − 1, there is no t-resilient algorithm in a t-crash model when t ∈ [1..(n−2)]. This means that the notion of t-resilience is inop-erative when one has to implement immediate snapshot for these values of t: the model assumption " at most t < n − 1 processes may crash " does not provide us with additional computational power allowing for the design of genuine t-resilient algorithms (genuine meaning that such a t-resilient algorithm would work in the t-crash model, but not in the (t + 1)-crash model). To show these results, the paper relies on well-known distributed computing agreement problems such as consensus and k-set agreement.

Published
2016

8. Modular randomized byzantine k-set agreement in asynchronous message-passing systems

Author

Hamouma Moumen, Michel Raynal, Achour Mostefaoui, Laboratoire des Sciences du Numérique de Nantes (LS2N), 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), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), Gestion de Données Distribuées (GDD), 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), Université Mustapha Ben Boulaid de Batna 2, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-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)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-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)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), ANR-14-CE35-0010,DISCMAT,Mathematical Methods in Distributed Computing(2014), 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 (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Gestion de Données Distribuées (LS2N - équipe GDD), 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), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Randomized algorithm, Asynchronous system, Theoretical computer science, Byzantine process, Distributed algorithm, Computer science, Message passing, Coin, 0102 computer and information sciences, 02 engineering and technology, k-Set agreement, 01 natural sciences, Set (abstract data type), Asynchronous message-passing system, Quantum Byzantine agreement, 010201 computation theory & mathematics, Asynchronous communication, Broadcast abstraction, 0202 electrical engineering, electronic engineering, information engineering, Signature-free algorithm, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Byzantine fault tolerance
Abstract

International audience; k-Set agreement is a central problem of fault-tolerant distibuted computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k dfferent values are decided, and the decided values satisfy some context-depending validity condition. Synchronous message-passing algorithms solving k-set agreement have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone asynchronous message-passing systems when t ≥ k. To circumvent this impossibility an asynchronous system must be enriched with additional computational power. Assuming t ≥ k, this paper presents a distributed algorithm that solves k-set agreement in an asynchronous message-passing system wher up to t processes may commit Byzantine failures. To that end, each process is enriched with randomization power. While randomized k-set agreement algorithms exist for the asynchronous process crash failure model where t ≥ k, to our knowledge the proposed algorithm is the first that solves k-set agreement in the presence of up to t ≥ k Byzantine processes. Interestingly, this algorithm is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Its design is based on a modular construction which rests on a "no-duplicity" one-to-all broadcast abstraction, and two all-to-all communication abstractions.

Published
2016

9. Simultaneous Consensus vs Set Agreement: A Message-Passing-Sensitive Hierarchy of Agreement Problems

Author

Michel Raynal, Julien Stainer, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), 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.), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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 Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, and Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Class (set theory), Reduction (recursion theory), Simultaneous consensus, Liveness, Structure (category theory), k-Set agreement, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Set (abstract data type), Distributed computability, Consensus, 0202 electrical engineering, electronic engineering, information engineering, Asynchronous system, Reduction, Mathematics, Failure detector, Discrete mathematics, Hierarchy (mathematics), Fault tolerance, Distributed computing, Message-passing system, Shared memory, 010201 computation theory & mathematics, Wait-freedom, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Quorum, Algorithm
Abstract

International audience; This paper investigates the relation linking the s-simultaneous consensus problem and the k-set agreement problem in wait-free message-passing systems. To this end, it first defines the (s,k)-SSA problem which captures jointly both problems: each process proposes a value, executes s simultaneous instances of a k-set agreement algorithm, and has to decide a value so that no more than sk different values are decided. The paper introduces then a new failure detector class denoted Z s,k , which is made up of two components, one focused on the "shared memory object" that allows the processes to cooperate, and the other focused on the liveness of (s,k)-SSA algorithms. A novelty of this failure detector lies in the fact that the definition of its two components are intimately related. Then, the paper presents a Z s,k -based algorithm that solves the (s,k)-SSA problem, and shows that the "shared memory"-oriented part of Z s,k is necessary to solve the (s,k)-SSA problem (this generalizes and refines a previous result that showed that the generalized quorum failure detector Σ k is necessary to solve k-set agreement). Finally, the paper investigates the structure of the family of (s,k)-SSA problems and introduces generalized (asymmetric) simultaneous set agreement problems in which the parameter k can differ in each underlying k-set agreement instance. Among other points, it shows that, for s,k > 1, (a) the (sk,1)-SSA problem is strictly stronger that the (s,k)-SSA problem which is itself strictly stronger than the (1,ks)-SSA problem, and (b) there are pairs (s 1,k 1) and (s 2,k 2) such that s 1 k 1 = s 2 k 2 and (s 1,k 1)-SSA and (s 2,k 2)-SSA are incomparable.; Cet article étudie les relations liant le problème du consensus s-simultané et celui de l'accord k-ensembliste.

Published
2013
Full Text
View/download PDF

10. Relations Linking Failure Detectors Associated with k-Set Agreement in Message-Passing Systems

Author

Michel Raynal, Julien Stainer, Achour Mostefaoui, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Xavier Défago et al., Rennes, Ist, SYSTÈMES LARGE ÉCHELLE (IRISA-D1), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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 Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), and Mostefaoui, Achour

Subjects
Reduction (recursion theory), K-set, Computer science, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], k-Set agreement, 0102 computer and information sciences, 02 engineering and technology, Topology, Equivalence, 01 natural sciences, Oracle, Distributed computability, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Theory, Eventual leader, ComputingMilieux_MISCELLANEOUS, Reduction, Failure detector, 020203 distributed computing, Computability, Detector, Message passing, Fault tolerance, Impossibility, Asynchronous message-passing system, Fault-tolerance, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], 010201 computation theory & mathematics, Asynchronous communication, Realistic failure detector, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Quorum, Algorithm
Abstract

The k-set agreement problem is a coordination problem where each process is assumed to propose a value and each process that does not crash has to decide a value such that each decided value is a proposed value and at most k different values are decided. While it can always be solved in synchronous systems, k-set agreement has no solution in asynchronous send/receive message-passing systems where up to t ≥ k processes may crash. A failure detector is a distributed oracle that provides processes with additional information related to failed processes and can consequently be used to enrich the computability power of asynchronous send/receive message-passing systems. Several failure detectors have been proposed to circumvent the impossibility of k-set agreement in pure asynchronous send/receive message-passing systems. Considering three of them (namely, the generalized quorum failure detector ∑k, the generalized loneliness failure detector Lk and the generalized eventual leader failure detector k) the paper investigates their computability power and the relations that link them. It has three mains contributions: (a) it shows that the failure detector k and the eventual version of Lk have the same computational power; (b) it shows that Lk is realistic if and only if k ≽ n=2; and (c) it gives an exact characterization of the difference between Lk (that is too strong for k-set agreement) and Lk (that is too weak for k-set agreement)., Ce rapport reprend les différents détecteurs de fautes introduits pour renforcer les systèmes asynchrones et rendre le problème de k-accord décidable. En effet, plusieurs détecteurs de fautes ont été introduits mais certains sont trop forts et d'autres trop faibles. Ce rapport a pour but de déterminer l'espace qui sépare les premiers des seconds afin d'essayer de se rapprocher du détecteur minimal.

Published
2011

11. Easy Impossibility Proofs for k-Set Agreement in Message Passing Systems

Author

Peter Robinson, Ulrich Schmid, Martin Biely, Fernandez Anta, Antonio, Lipari, Guiseppe, and Roy, Mathieu

Subjects
FOS: Computer and information sciences, Distributed Consensus, Theoretical computer science, K-set, Computer science, Proof of impossibility, 0102 computer and information sciences, 02 engineering and technology, Mathematical proof, k-set agreement, 01 natural sciences, Consensus, Lemma (logic), 0202 electrical engineering, electronic engineering, information engineering, C.2.4, Failure Detectors, Impossibility, Principle of bivalence, Discrete mathematics, 020203 distributed computing, Message passing, F.1.1, TheoryofComputation_GENERAL, 020207 software engineering, impossibility proofs, Shared memory, Computer Science - Distributed, Parallel, and Cluster Computing, consensus, 010201 computation theory & mathematics, Asynchronous communication, Distributed, Parallel, and Cluster Computing (cs.DC)
Abstract

Despite of being quite similar agreement problems, consensus and general k-set agreement require surprisingly different techniques for proving the impossibility in asynchronous systems with crash failures: Rather than relatively simple bivalence arguments as in the impossibility proof for consensus (= 1-set agreement) in the presence of a single crash failure, known proofs for the impossibility of k-set agreement in systems with at least k>1 crash failures use algebraic topology or a variant of Sperner's Lemma. In this paper, we present a generic theorem for proving the impossibility of k-set agreement in various message passing settings, which is based on a simple reduction to the consensus impossibility in a certain subsystem. We demonstrate the broad applicability of our result by exploring the possibility/impossibility border of k-set agreement in several message-passing system models: (i) asynchronous systems with crash failures, (ii) partially synchronous processes with (initial) crash failures, and (iii) asynchronous systems augmented with failure detectors. In (i) and (ii), the impossibility part is just an instantiation of our main theorem, whereas the possibility of achieving k-set agreement in (ii) follows by generalizing the consensus algorithm for initial crashes by Fisher, Lynch and Patterson. In (iii), applying our technique yields the exact border for the parameter k where k-set agreement is solvable with the failure detector class (Sigma_k,Omega_k), for (1, 15 pages

Published
2011

12. Chasing the Weakest Failure Detector for k-Set Agreement in Message-passing Systems

Author

Achour Mostefaoui, Julien Stainer, Michel Raynal, Rennes, Ist, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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 Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), 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), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Gestion de Données Distribuées [Nantes] (GDD), Laboratoire d'Informatique de Nantes Atlantique (LINA), 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), IUF, ANR Displexity, ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), 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), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-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)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique

Subjects
Reduction (recursion theory), K-set, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, 02 engineering and technology, k-Set agreement, 01 natural sciences, Electronic mail, Set (abstract data type), 0202 electrical engineering, electronic engineering, information engineering, Eventual leader, Set theory, Asynchronous system, Reduction, Discrete mathematics, Asynchronous distributed system, Failure detector, Wait-freedom, 020203 distributed computing, Message passing, Fault tolerance, Fault-tolerance, Message-passing system, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], 010201 computation theory & mathematics, Asynchronous communication, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Quorum
Abstract

This paper continues our quest for the weakest failure detector which allows the k-set agreement problem to be solved in asynchronous message-passing systems prone to any number of process failures. It has two main contributions which (we hope) will be instrumental to complete this quest. The first contribution is a new failure detector (denoted ∏∑x,y). This failure detector has several noteworthy properties. (a) It is stronger than ∑x which has been shown to be necessary. (b) It is equivalent to the pair (∑, Ω) when x = y = 1 (from which it follows that ∏∑1,1 is optimal to solve consensus). (c) It is equivalent to the pair (∑n−1, Ωn−1) when x = y = n − 1 (from which it follows that ∏∑n−1, n−1) is optimal for (n − 1)-set agreement). (d) It is strictly weaker than the pair (∑x,Ωy) (which has been investigated in previous works) for the pairs (x, y) such that 1 < y < x < n. (e) It is operational: the paper presents a ∏∑x,y-based algorithm that solves k-set agreement for k ⩾ xy. The second contribution of the paper is a proof that, for 1 < k < n − 1, the eventual leaders failure detector k (which eventually provides each process with the same set of k process identities, this set including at least one correct process) is not necessary to solve k-set agreement problem. More precisely, the paper shows that the weakest failure detector for k-set agreement and k cannot be compared.

Published
2011
Full Text
View/download PDF

13. The Multiplicative Power of Consensus Numbers

Author

Damien Imbs, Michel Raynal, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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 Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), and Frey, Davide

Subjects
Reduction (recursion theory), ACM: C.: Computer Systems Organization/C.1: PROCESSOR ARCHITECTURES, Value (computer science), 0102 computer and information sciences, 02 engineering and technology, k-Set agreement, Shared memory system, 01 natural sciences, Upper and lower bounds, Consensus number, Synchronization power, Distributed computability, t-Resilience, System model, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Asynchronous processes, Mathematics, Discrete mathematics, Shared memory model, Fault-Tolerance, Multiplicative function, Process (computing), Waitfreedom, Process crash failure, 020207 software engineering, Base (topology), Power (physics), 010201 computation theory & mathematics, [INFO.INFO-OS]Computer Science [cs]/Operating Systems [cs.OS], BG simulation, Algorithm, Reduction algorithm
Abstract

The Borowsky-Gafni (BG) simulation algorithm is a powerful reduction algorithm that shows that t-resilience of decision tasks can be fully characterized in terms of wait-freedom. Said in another way, the BG simulation shows that the crucial parameter is not the number n of processes but the upper bound t on the number of processes that are allowed to crash. The BG algorithm considers colorless decision tasks in the base read/write shared memory model. (Colorless means that if, process decides a value, any other process is allowed to decide the very same value.) This paper considers system models made up of n processes prone to up to t crashes, and where the processes communicate by accessing read/write atomic registers (as assumed by the BG) and (differently from the BG) objects with consensus number x accessible by at most x processes (with x ≤ t n). Let ASM(n,t,x) denote such a system model. While the BG simulation has shown that the models ASM(n,t,1) and ASM(t+1,t,1) are equivalent, this paper focuses the pair (t,x) of parameters of a system model. Its main result is the following: the system models ASM (n1,t1,x1) and ASM (n2,t2,x2) have the same computational power for colorless decision tasks if and only if ⌊t1⁄x1⌋ = ⌊t1⁄x1⌋. As can be seen, this contribution complements and extends the BG simulation. It shows that consensus numbers have a multiplicative power with respect to failures, namely the system models ASM(n,t',x) and ASM(n,t,1) are equivalent for colorless decision tasks iff (t x x) ≤ t' ≤ (t x x)+(x-1).

Published
2010

14. On the road to the weakest failure detector for k-set agreement in message-passing systems

Author

François Bonnet, Michel Raynal, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-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)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-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)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Japan Advanced Institute of Science and Technology (JAIST), 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), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Class (set theory), Reduction (recursion theory), General Computer Science, K-set, Computer science, Structure (category theory), Asynchronous systems, Value (computer science), Quorums, 0102 computer and information sciences, 02 engineering and technology, Failure detectors, 01 natural sciences, k-set agreement, Theoretical Computer Science, Set (abstract data type), 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Reduction, Discrete mathematics, Message passing, Eventual leaders, Shared memory, 010201 computation theory & mathematics, Message-passing systems, Wait-freedom, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm
Abstract

In the k -set agreement problem, each process (in a set of n processes) proposes a value and has to decide a proposed value in such a way that at most k different values are decided. While this problem can easily be solved in asynchronous systems prone to t process crashes when k > t , it cannot be solved when k ≤ t . For several years, the failure-detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the k -set agreement problem in read/write shared memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases k = 1 (consensus) and k = n − 1 (set agreement). This paper presents four contributions whose aim is to help pave the way to discover the weakest failure detector class for k -set agreement in message-passing systems. These contributions are the following. (a) The first is a new failure detector class, denoted Π k , that is such that Π 1 = Σ × Ω (the weakest class for k = 1 ), and Π n − 1 = L (the weakest class for k = n − 1 ). (b) The second is an investigation of the structure of Π k that shows that Π k is the combination of two failure detector classes Σ k (that is new) and Ω k (they generalize the previous “quorums” and “eventual leaders” failure detector classes, respectively). (c) The third contribution concerns Σ k that is shown to be a necessary requirement (as far as information on failure is concerned) to solve the k -set agreement problem in message-passing systems. (d) Finally, the last contribution is a Π n − 1 -based algorithm that solves the ( n − 1 ) -set agreement problem. This algorithm provides us with a new algorithmic insight on the way the ( n − 1 ) -set agreement problem can be solved in asynchronous message-passing systems. It is hoped that these contributions will help discover the weakest failure detector class for k -set agreement in message-passing systems.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results