direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Aidan Walton's Publications

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

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe