TU Berlin

Internet Network ArchitecturesPetr Kuznetsov's Publications

Page Content

to Navigation

Petr Kuznetsov's Publications

Turning Adversaries into Friends: Simplified, Made Constructive, and Extended
Citation key GK-TAFSMCE-10
Author Gafni, Eli and Kuznetsov, Petr
Title of Book Proceedings of 14th International Conference On Principles Of Distributed Systems (OPODIS '10)
Pages 380–394
Year 2010
ISBN 978-3-642-17652-4
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/978-3-642-17653-1_28
Location Tozeur, Tunesia
Address Berlin / Heidelberg, Germany
Volume 6490
Month December
Publisher Springer
Series Lecture Notes in Computer Science (LNCS)
Abstract 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 entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe