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: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

N-Consensus is the Second Strongest Object for N+1 Processes
Zitatschlüssel GK-NSSONP-07
Autor Gafni, Eli and Kuznetsov, Petr
Buchtitel 11th International Conference On Principles Of DIstributed Systems (OPODIS 2007)
Seiten 260–273
Jahr 2007
ISBN 978-3-540-77095-4
ISSN 0302-9743
DOI http://dx.doi.org/1007/978-3-540-77096-1_19
Ort Guadeloupe, French West Indies
Adresse Berlin / Heidelberg, Germany
Jahrgang 4878
Monat December
Verlag Springer
Serie Lecture Notes in Computer Science (LNCS)
Zusammenfassung Objects like queue, swap, and test-and-set allow two processes to reach consensus, and are consequently “universal” for a system of two processes. But are there deterministic objects that do not solve 2-process consensus, and nevertheless allow two processes to solve a task that is not otherwise wait-free solvable in read-write shared memory? The answer “no” is a simple corollary of the main result of this paper: Let A be a deterministic object such that no protocol solves consensus among n+1 processes using copies of A and read-write registers. If a task T is wait-free solvable by n+1 processes using read-write shared-memory and copies of A, then T is also wait-free solvable when copies of A are replaced with n-consensus objects. Thus, from the task-solvability perspective, n-consensus is the second strongest object (after (n+1)-consensus) in deterministic shared memory systems of n+1 processes, i.e., there is a distinct gap between n- and (n+1)-consensus. We derive this result by showing that any (n+1)-process protocol P that uses objects A can be emulated using only n-consensus objects. The resulting emulation is non-blocking and relies on an a priori knowledge of P. The emulation technique is another important contribution of this paper.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Under Construction

This page/section is
still under construc-
tion. Please try again