A Separation of n-consensus and (n + 1)-consensus Based on Process Scheduling

Carole Delporte-Gallet 1, 2 Hugues Fauconnier 2, 1 Sam Toueg 3
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : A fundamental research theme in distributed computing is the comparison of systems in terms of their ability to solve basic problems such as consensus that cannot be solved in completely asynchronous systems. In particular, in a seminal work [12], Herlihy compares shared-memory systems in terms of the shared objects that they have: he proved that there are shared objects that are powerful enough to solve consensus for n processes, but are too weak to solve consensus for n + 1 processes; such objects are placed at level n of a wait-free hierarchy. As in [12], we compare shared-memory systems with respect to their ability to solve consensus for n processes. But instead of comparing systems defined by the shared objects that they have, we compare read-write systems defined by the set of process schedules that can occur in these systems. Defining systems this way can capture many types of systems, e.g., systems whose synchrony ranges from fully synchronous to completely asynchronous, several systems with failure detectors, and “obstruction-free” systems. In this paper, we consider read-write systems defined in terms of sets of process schedules, and investigate the following fundamental question: Is there a system of n + 1 processes such that consensus can be solved for every subset of n processes in the system, but consensus cannot be solved for the n + 1 processes of the system? We show that the answer to the above question is “yes”, and so these systems can be classified into hierarchy akin to Herlihy’s hierarchy.
Type de document :
Communication dans un congrès
Structural Information and Communication Complexity - 22nd International Colloquium, 2015, Jul 2015, Montserrat, France. Structural Information and Communication Complexity - 22nd International Colloquium, 2015, Springer LNCS, 9439, pp.385-398, 2015, Springer LNCS. 〈10.1007/978-3-319-25258-2_27〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01251571
Contributeur : Carole Delporte-Gallet <>
Soumis le : mercredi 6 janvier 2016 - 13:55:10
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg. A Separation of n-consensus and (n + 1)-consensus Based on Process Scheduling. Structural Information and Communication Complexity - 22nd International Colloquium, 2015, Jul 2015, Montserrat, France. Structural Information and Communication Complexity - 22nd International Colloquium, 2015, Springer LNCS, 9439, pp.385-398, 2015, Springer LNCS. 〈10.1007/978-3-319-25258-2_27〉. 〈hal-01251571〉

Partager

Métriques

Consultations de la notice

123