direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Selected Publications on Distributed Systems

Turning Adversaries into Friends: Simplified, Made Constructive, and Extended
Zitatschlüssel GK-TAFSMCE-10
Autor Gafni, Eli and Kuznetsov, Petr
Buchtitel Proceedings of 14th International Conference On Principles Of Distributed Systems (OPODIS '10)
Seiten 380–394
Jahr 2010
ISBN 978-3-642-17652-4
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/978-3-642-17653-1_28
Ort Tozeur, Tunesia
Adresse Berlin / Heidelberg, Germany
Jahrgang 6490
Monat December
Verlag Springer
Serie Lecture Notes in Computer Science (LNCS)
Zusammenfassung A liveness contract is an agreement between the specifier of a system and a task to solve, and the programmer who makes her living by delivering protocols. In a shared-memory system, a liveness contract specifies infinite suffixes of executions in which the programmer is required to solve a distributed task. If the behavior of the system does not comply with the specification, no output is required. A convenient way to describe a large class of liveness contracts was recently proposed by Delporte et al. For a system Π of n processes, an adversary is a set A of subsets of Π. The system is required to make progress only in executions in which the set of correct processes is in A. Given an adversary A and a task T, should the programmer sign the contract? Can she deliver? In this paper, we give a very simple resolution of this question for colorless tasks that contrasts with more involved arguments of the original paper of Delpote et al. More importantly, our resolution is constructive – it tells the programmer how to use A to solve T, when it is solvable. Our framework naturally generalizes to systems enriched with more powerful objects than read-write registers. We determine necessary and sufficient conditions for an adversary A to solve consensus using j-process consensus objects and read-write registers, which resolves an open question raised recently by Taubenfeld.
Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe