Back to Search Start Over

The Multiplicative Power of Consensus Numbers

Authors :
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)
Frey, Davide
Source :
[Research Report] PI 1949, 2010, pp.17, 29th ACM Symposium on Principles of Distributed Computing (PODC'10), 29th ACM Symposium on Principles of Distributed Computing (PODC'10), Jul 2010, Zurich, Switzerland. pp.26-35, PODC
Publication Year :
2010
Publisher :
HAL CCSD, 2010.

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

Details

Language :
English
Database :
OpenAIRE
Journal :
[Research Report] PI 1949, 2010, pp.17, 29th ACM Symposium on Principles of Distributed Computing (PODC'10), 29th ACM Symposium on Principles of Distributed Computing (PODC'10), Jul 2010, Zurich, Switzerland. pp.26-35, PODC
Accession number :
edsair.doi.dedup.....dbaf93a0be3e6df07b125b7cfb235921