s'authentifier
version française rss feed

inria-00454399, version 2

The Multiplicative Power of Consensus Numbers

Damien Imbs () a1, Michel Raynal () a1

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
  • oai:hal.inria.fr:inria-00454399
  • Contributeur : 
  • Soumis le : Mercredi 5 Mai 2010, 15:15:36
  • Dernière modification le : Mardi 11 Mai 2010, 11:47:16
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...