The Multiplicative Power of Consensus Numbers
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).
Origine : Fichiers produits par l'(les) auteur(s)
Loading...