inria-00454399, version 2
The Multiplicative Power of Consensus Numbers
Damien Imbs
a, 1Michel Raynal
a, 1
N° PI 1949 (2010)
Résumé : 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).
- a – Université de Rennes 1
- 1 : ASAP (INRIA - IRISA)
- CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
- Domaine : Informatique/Système d'exploitation
- Mots-clés : Asynchronous processes – BG simulation – Consensus number – Distributed computability – Fault-Tolerance – Process crash failure – Reduction algorithm – t-Resilience – k-Set agreement – Shared memory system – Synchronization power – System model – Waitfreedom
- Référence interne : PI 1949
- Versions disponibles : v1 (08-02-2010) v2 (05-05-2010)
- inria-00454399, version 2
- http://hal.inria.fr/inria-00454399
- oai:hal.inria.fr:inria-00454399
- Contributeur : Ist Rennes
- Soumis le : Mercredi 5 Mai 2010, 15:15:36
- Dernière modification le : Mardi 11 Mai 2010, 11:47:16






Documents associés
Exporter