The Multiplicative Power of Consensus Numbers

Damien Imbs 1 Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
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, a 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 (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(n₁, t₁, x₁) and ASM(n₂, t₂, x₂) have the same computational power for colorless decision tasks if and only if [t₁/x₁] = [t₂/x₂]. 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; t0; x) and ASM(n; t; 1) are equivalent for colorless decision tasks iff (t x x) ≤ t' ≤ (t x x) + (x - 1).
Type de document :
[Research Report] PI 1949, 2010, pp.17
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
Contributeur : Ist Rennes <>
Soumis le : mercredi 5 mai 2010 - 15:15:36
Dernière modification le : samedi 24 mars 2018 - 01:39:16
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 13:05:47


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00454399, version 2



Damien Imbs, Michel Raynal. The Multiplicative Power of Consensus Numbers. [Research Report] PI 1949, 2010, pp.17. 〈inria-00454399v2〉



Consultations de la notice


Téléchargements de fichiers