direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Journal and Magazine Articles

The Gap in Circumventing the Impossibility of Consensus
Zitatschlüssel GK-GCIC-08
Autor Guerraoui, Rachid and Kouznetsov, Petr
Seiten 823–830
Jahr 2008
ISSN 0022-0000
DOI http://dx.doi.org/10.1016/j.jcss.2007.10.002
Journal Journal of Computer and System Sciences (JCSS)
Jahrgang 74
Nummer 5
Zusammenfassung The impossibility of reaching deterministic consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value in $0,1$, so that both 0 and 1 are possible decision values. On the other hand, approaches to circumventing the impossibility focused on a stronger variant of the problem, called consensus, where the processes need to decide on one of the values they initially propose (0 or 1). This paper studies the computational gap between the two problems. We show that any set of deterministic object types that, combined with registers, implements weak consensus, also implements consensus. Then we exhibit a non-deterministic type that implements weak consensus, among any number of processes, but, combined with registers, cannot implement consensus even among two processes. In modern terminology, this type has consensus power 1 and weak consensus power ∞.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe