### Page Content

# Publications by Type: Journal and Magazine Articles

Citation key | GK-FDATB-08 |
---|---|

Author | Guerraoui, Rachid and Kouznetsov, Petr |

Pages | 343–358 |

Year | 2008 |

ISSN | 0178-2770 |

DOI | http://dx.doi.org/10.1007/s00446-007-0043-z |

Address | Berlin / Heidelberg, Germany |

Journal | Distributed Computing Journal (DC) |

Volume | 20 |

Number | 5 |

Month | February |

Publisher | Springer |

Abstract | The power of an object type T can be measured as the maximum number n of processes that can solve consensus using only objects of T and registers. This number, denoted cons(T), is called the consensus power of T. This paper addresses the question of the weakest failure detector to solve consensus among a number k>n of processes that communicate using shared objects of a type T with consensus power n. In other words, we seek for a failure detector that is sufficient and necessary to ``boost'' the consensus power of a type T from n to k. It was shown in Neiger (Proceedings of the 14th annual ACM symposium on principles of distributed computing (PODC), pp. 100–109, 1995) that a certain failure detector, denoted Ω_n , is sufficient to boost the power of a type T from n to k, and it was conjectured that Ω_n was also necessary. In this paper, we prove this conjecture for one-shot deterministic types. We first show that, for any one-shot deterministic type T with cons(T)≤n, Ω_n is necessary to boost the power of T from n to n+1. Then we go a step further and show that Ω_n is also the weakest to boost the power of (n+1)-ported one-shot deterministic types from n to any k>n. Our result generalizes, in a precise sense, the result of the weakest failure detector to solve consensus in asynchronous message-passing systems (Chandra et al. in J ACM 43(4):685–722, 1996). As a corollary, we show that Ω_t is the weakest failure detector to boost the resilience level of a distributed shared memory system, i.e., to solve consensus among n>t processes using (t−1)-resilient objects of consensus power t. |

### Zusatzinformationen / Extras

## Quick Access:

Schnellnavigation zur Seite über Nummerneingabe