Search

Your search keyword '"k-Set agreement"' showing total 13 results
Start Over Descriptor "k-Set agreement" Topic consensus
13 results on '"k-Set agreement"'

1. t-Resilient Immediate Snapshot Is Impossible

Author

Delporte, Carole, Fauconnier, Hugues, Rajsbaum, Sergio, Raynal, Michel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Suomela, Jukka, editor

Published
2016
Full Text
View/download PDF

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

Author

Biely, Martin, Robinson, Peter, Schmid, Ulrich, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Fernàndez Anta, Antonio, editor, Lipari, Giuseppe, editor, and Roy, Matthieu, editor

Published
2011
Full Text
View/download PDF

3. Reaching agreement in the presence of contention-related crash failures.

Author

Durand, Anaïs, Raynal, Michel, and Taubenfeld, Gadi

Subjects
*SYSTEM failures
Abstract

While consensus (and more generally agreement problems) is at the heart of many coordination problems in asynchronous distributed systems prone to process crashes, it has been shown to be impossible to solve in such systems where processes communicate by message-passing or by reading and writing a shared memory. Hence, these systems must be enriched with additional computational power for consensus to be solved on top of them. This article presents a new restriction of the classical basic computational model that combines process participation and a constraint on failure occurrences that can happen only while a predefined contention threshold has not yet been bypassed. This type of failure is called λ-constrained crashes , where λ defines the considered contention threshold. It appears that when assuming such contention-related crash failures and enriching the system with objects whose consensus number is x ≥ 1 , consensus for n processes can be solved for any n ≥ x assuming up to x failures. The article proceeds incrementally. It first presents an algorithm that solves consensus on top of read/write registers if at most one crash occurs before the contention threshold λ = n − 1 has been bypassed. Then, the article considers two extensions. The first one assumes that the system is enriched with objects whose consensus number is x ≥ 1 , and shows that when λ = n − x , consensus can be solved despite up to x λ -constrained crashes, for any n ≥ x , and when λ = n − 2 x + 1 , consensus can be solved despite up to 2 x − 1 λ -constrained crashes, assuming x divides n. The second extension prolongs the previous results to the k -set agreement problem (which is a natural generalization of consensus). Impossibility results are also presented for the number of λ -constrained failures that can be tolerated. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

4. Distributed Universality.

Author

Raynal, Michel, Stainer, Julien, and Taubenfeld, Gadi

Subjects
*DISTRIBUTED computing, *ALGORITHMS, *SEQUENTIAL analysis, *SYNCHRONIZATION, *SYSTEM analysis
Abstract

A notion of a universal construction suited to distributed computing has been introduced by Herlihy in his celebrated paper ' Wait-free synchronization' (ACM Trans Program Lang Syst 13(1):124-149, 1991). A universal construction is an algorithm that can be used to wait-free implement any object defined by a sequential specification. Herlihy's paper shows that the basic system model, which supports only atomic read/write registers, has to be enriched with consensus objects to allow the design of universal constructions. The generalized notion of a k -universal construction has been recently introduced by Gafni and Guerraoui (Proceedings of 22nd international conference on concurrency theory (CONCUR'11), Springer LNCS 6901, pp 17-27, 2011). A k-universal construction is an algorithm that can be used to simultaneously implement k objects (instead of just one object), with the guarantee that at least one of the k constructed objects progresses forever. While Herlihy's universal construction relies on atomic registers and consensus objects, a k-universal construction relies on atomic registers and k-simultaneous consensus objects (which are wait-free equivalent to k-set agreement objects in the read/write system model). This paper significantly extends the universality results introduced by Herlihy and Gafni-Guerraoui. In particular, we present a k-universal construction which satisfies the following five desired properties, which are not satisfied by the previous k-universal construction: (1) among the k objects that are constructed, at least $$\ell $$ objects (and not just one) are guaranteed to progress forever; (2) the progress condition for processes is wait-freedom, which means that each correct process executes an infinite number of operations on each object that progresses forever; (3) if any of the k constructed objects stops progressing, all its copies (one at each process) stop in the same state; (4) the proposed construction is contention-aware, in the sense that it uses only read/write registers in the absence of contention; and (5) it is generous with respect to the obstruction-freedom progress condition, which means that each process is able to complete any one of its pending operations on the k objects if all the other processes hold still long enough. The proposed construction, which is based on new design principles, is called a $$(k,\ell )$$ -universal construction. It uses a natural extension of k-simultaneous consensus objects, called $$(k,\ell )$$ -simultaneous consensus objects ( $$(k,\ell )$$ -SC). Together with atomic registers, $$(k,\ell )$$ -SC objects are shown to be necessary and sufficient for building a $$(k,\ell )$$ -universal construction, and, in that sense, $$(k,\ell )$$ -SC objects are $$(k,\ell )$$ - $$ {universal}$$ . [ABSTRACT FROM AUTHOR]

Published
2016
Full Text
View/download PDF

6. Failure Detectors in Dynamic Distributed Systems

Author

Jeanneau, Denis, DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Sorbonne Université, Pierre Sens, and Luciana Arantes

Subjects
Consensus, K-Accord, Détecteurs de fautes, Systèmes distribués, Exclusion mutuelle, Mutual Exclusion, Failure detectors, Systèmes dynamiques, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed systems, Dynamic systems, K-set agreement
Abstract

Dynamic systems are distributed systems in which (1) processes can join or leave the system during the run, and (2) the communication graph evolves over time. The failure detector abstraction was introduced as a way to circumvent the impossibility of solving consensus in asynchronous systems prone to crash failures. A failure detector is a local oracle that provides processes in the system with unreliable information on process failures. But a failure detector that is sufficient to solve a given problem in a static system is not necessarily sufficient to solve the same problem in a dynamic system. Additionally, some existing failure detectors cannot be implemented in dynamic systems. Therefore, it is necessary to redefine existing failure detectors and provide new algorithms. In this thesis, we provide a new definition of a failure detector for k-set agreement, and prove that it is sufficient to solve k-set agreement in dynamic systems. We also design a dynamic system model and an algorithm that implements this new failure detector. Additionally, we adapt an existing failure detector for mutual exclusion and prove that it is still the weakest failure detector to solve mutual exclusion in dynamic systems, which means that it is weaker than any other failure detector capable of solving mutual exclusion.; Les systèmes dynamiques sont des systèmes distribués dans lesquels (1) les processus peuvent rejoindre ou quitter le système en cours d'exécution, et (2) le graphe de communication évolue au fil du temps. L'abstraction des détecteurs de fautes a été introduite afin de contourner l'impossibilité de résoudre le consensus dans les systèmes asynchrones sujets aux pannes franches. Mais un détecteur de fautes qui est suffisant pour résoudre un problème donné dans un système statique n'est pas nécessairement suffisant pour résoudre le même problème dans un système dynamique. Par conséquent, il est nécessaire de redéfinir les détecteurs de fautes existants et de concevoir de nouveaux algorithmes. Dans cette thèse, nous fournissons une nouvelle définition d'un détecteur de fautes pour le k-accord, et nous prouvons qu'il est suffisant pour résoudre le k-accord dans un système dynamique. Nous définissons également un modèle de système dynamique, ainsi qu'un algorithme capable d'implémenter ce nouveau détecteur de fautes dans notre modèle. De plus, nous adaptons un détecteur existant pour l'exclusion mutuelle et nous prouvons que même dans les systèmes dynamiques, il s'agit toujours du détecteur de fautes le plus faible pour résoudre l'exclusion mutuelle. Cela signifie que ce détecteur est plus faible que tous les autres détecteurs capables de résoudre l'exclusion mutuelle.

Published
2018

7. Détecteurs de fautes pour les systèmes distribués dynamiques

Author

Jeanneau, Élise, DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Sorbonne Université, Pierre Sens, and Luciana Arantes

Subjects
Consensus, K-Accord, Détecteurs de fautes, Systèmes distribués, Exclusion mutuelle, Failure detectors, Mutual Exclusion, Systèmes dynamiques, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed systems, Dynamic systems, K-set agreement
Abstract

Dynamic systems are distributed systems in which (1) processes can join or leave the system during the run, and (2) the communication graph evolves over time. The failure detector abstraction was introduced as a way to circumvent the impossibility of solving consensus in asynchronous systems prone to crash failures. A failure detector is a local oracle that provides processes in the system with unreliable information on process failures. But a failure detector that is sufficient to solve a given problem in a static system is not necessarily sufficient to solve the same problem in a dynamic system. Additionally, some existing failure detectors cannot be implemented in dynamic systems. Therefore, it is necessary to redefine existing failure detectors and provide new algorithms. In this thesis, we provide a new definition of a failure detector for k-set agreement, and prove that it is sufficient to solve k-set agreement in dynamic systems. We also design a dynamic system model and an algorithm that implements this new failure detector. Additionally, we adapt an existing failure detector for mutual exclusion and prove that it is still the weakest failure detector to solve mutual exclusion in dynamic systems, which means that it is weaker than any other failure detector capable of solving mutual exclusion.; Les systèmes dynamiques sont des systèmes distribués dans lesquels (1) les processus peuvent rejoindre ou quitter le système en cours d'exécution, et (2) le graphe de communication évolue au fil du temps. L'abstraction des détecteurs de fautes a été introduite afin de contourner l'impossibilité de résoudre le consensus dans les systèmes asynchrones sujets aux pannes franches. Mais un détecteur de fautes qui est suffisant pour résoudre un problème donné dans un système statique n'est pas nécessairement suffisant pour résoudre le même problème dans un système dynamique. Par conséquent, il est nécessaire de redéfinir les détecteurs de fautes existants et de concevoir de nouveaux algorithmes. Dans cette thèse, nous fournissons une nouvelle définition d'un détecteur de fautes pour le k-accord, et nous prouvons qu'il est suffisant pour résoudre le k-accord dans un système dynamique. Nous définissons également un modèle de système dynamique, ainsi qu'un algorithme capable d'implémenter ce nouveau détecteur de fautes dans notre modèle. De plus, nous adaptons un détecteur existant pour l'exclusion mutuelle et nous prouvons que même dans les systèmes dynamiques, il s'agit toujours du détecteur de fautes le plus faible pour résoudre l'exclusion mutuelle. Cela signifie que ce détecteur est plus faible que tous les autres détecteurs capables de résoudre l'exclusion mutuelle.

Published
2018

8. Anonymous obstruction-free (n,k)-set agreement with n−k+1 atomic read/write registers

Author

Bouzid, Zohir, Raynal, Michel, Sutra, Pierre, 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), 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.), Département Informatique (TSP - INF), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Algorithmes, Composants, Modèles Et Services pour l'informatique répartie (ACMES-SAMOVAR), Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP)-Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Centre National de la Recherche Scientifique (CNRS), 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 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), and Département Informatique (INF)

Subjects
Consensus, Distributed algorithm, Colorless task, Atomic read/write register, Bounded num-ber of registers, Fault-tolerance, Distributed computability, Obstruction-freedom, Anonymous processes, Repeated k-set agreement, Asynchronous system, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Process crash, Upper bound, K-set agreement
Abstract

International audience; The k-set agreement problem is a generalization of the consensus problem. Namely, assuming that each pro- cess proposes a value, every non-faulty process must decide one of the proposed values, under the constraint that at most k different values are decided. This is a hard problem in the sense that it cannot be solved in a pure read/write asyn- chronous system, in which k or more processes may crash. One way to sidestep this impossibility result consists in weak- ening the termination property, requiring only that a process decides if it executes alone during a long enough period of time. This is the well-known obstruction-freedom progress condition. Consider a system of n anonymous asynchronous processes that communicate through atomic read/write reg- isters, and such that any number of them may crash. This paper addresses and solves the challenging open problem of designing an obstruction-free k-set agreement algorithm with only (n −k +1) atomic registers. From a shared memory cost point of view, our algorithm is the best algorithm known to date, thereby establishing a new upper bound on the number of registers needed to solve this problem. For the consensus case (k = 1), the proposed algorithm is up to an additive factor of 1 close to the best known lower bound. Further, the paper extends this algorithm to obtain an x-obstruction- free solution to the k-set agreement problem that employs (n − k + x) atomic registers (with 1 ≤ x ≤ k < n), as well as a space-optimal solution for the repeated ver- sion of k-set agreement. Using this last extension, we prove that n registers are enough for every colorless task that is obstruction-free solvable with identifiers and any number of registers

Published
2018
Full Text
View/download PDF

9. 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

10. Anonymous Obstruction-free $(n,k)$-Set Agreement with $n-k+1$ Atomic Read/Write Registers

Author

Bouzid, Zohir, Raynal, Michel, Sutra, Pierre, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), 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), Université de Neuchâtel (UNINE), univzrité de rennes 1, ASAP INRIA de Rennes, Université de Rennes (UR)-Inria Saclay - Ile de France, 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
Consensus, Distributed algorithm, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Atomic read/write register, k-Set agreement, Bounded number of registers, Key-words: Anonymous processes, Fault-tolerance, Distributed computability, Obstruction-freedom, Repeated k-set agreement, Asynchronous system, Upper bound, Process crash
Abstract

The $k$-set agreement problem is a generalization of the consensus problem.Namely, assuming each process proposes a value, each non-faulty process has to decide a value such that each decided value was proposed, and no more than $k$ different values are decided. This is a hard problem in the sense thatit cannot be solved in asynchronous systems as soon as $k$ or more processes may crash. One way to circumvent this impossibility consists in weakening its termination property, requiring that a process terminates (decides) only if it executes alone during a long enough period. This is the well-known obstruction-freedom progress condition. Considering a system of $n$ {\it anonymous asynchronous} processes, which communicate through atomic {\it read/write registers only}, and where {\it any number of processes may crash}, this paper addresses and solves the challenging open problem of designing an obstruction-free $k$-set agreement algorithm with $(n-k+1)$ atomic registers only. From a shared memory cost point of view, this algorithm is the best algorithm known so far, thereby establishing a new upper bound on the numberof registers needed to solve the problem (its gain is $(n-k)$ with respect to the previous upper bound). The algorithm is then extended to address the repeated version of $(n,k)$-set agreement. As it is optimal in the number of atomic read/write registers, this algorithm closes the gap on previously established lower/upper boundsfor both the anonymous and non-anonymous versions of the repeated $(n,k)$-set agreement problem. Finally, for $1 \leq x\leq k < n$, a generalization suited to $x$-obstruction-freedom is also described, which requires $(n-k+x)$ atomic registers only.; Cet article préente un algorithme asynchrone qui résoud l'accord k-ensenbliste dans un système de n processus asynchrones et anonymes communiquant via $(n-k+1)$ registres atomiques du type lire/écrire, et dans lequel un nombre quelconque d'entre eux peut s'arrêterde façon inopinée (crash failure). La propriété de vivacité garantie par l'algorithme est appelée "obstruction-freedom".

Published
2015

11. 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

12. 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

13. Synchronous Set Agreement: a Concise Guided Tour (with open problems)

Author

Raynal, Michel, Travers, Corentin, 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)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Round-based computation, Tolérance aux fautes, Consensus, Lower bound, Distributed algorithm, Agreement problem, Efficiency, Accord ensembliste, k-set agreement, ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.5: Reliability, ACM: C.: Computer Systems Organization/C.4: PERFORMANCE OF SYSTEMS, Early decision, Message-passing system, Crash failure, Omission en émission, Send omission failure, Synchronous system \\ Systèmes répartis asynchrones, Receive omission failure, Omission en réception, Crash de processus, [INFO.INFO-OS]Computer Science [cs]/Operating Systems [cs.OS], General omission failure
Abstract

The $k$-set agreement problem is a paradigm of coordination problems encountered in distributed computing. The parameter $k$ defines the coordination degree we are interested in. The case $k=1$ corresponds to the well-known uniform consensus problem. More precisely, the $k$-set agreement problem considers a system made up of $n$ processes where each process proposes a value. It requires that each non-faulty process decides a value such that a decided value is a proposed value, and no more than $k$ different values are decided. This paper visits the $k$-set agreement problem in synchronous systems where up to $t$ processes can experience failures. Three failure models are explored: the crash failure model, the send omission failure model, and the general omission failure model. Lower bounds and protocols are presented for each model. Open problems for the general omission failure model are stated. This paper can be seen as a short tutorial whose aim is to make the reader familiar with the $k$-set agreement problem in synchrony models with increasing fault severity. An important concern of the paper is simplicity. In addition to its survey flavor, several results and protocols that are presented are new. \\ Ce rapport constitue une visite guidé de l'accord ensembliste synchrone en présence de crashs, de fautes d'omission en émission, et de fautes d'omission en émission et réception.

Published
2006

Catalog

Books, media, physical & digital resources
See catalog results