Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
Almost every computing system
nowadays is distributed, ranging from multi-core laptops to
Internet-scale services; understanding the principles of distributed
computing is hence important for the design and engineering of modern
computing systems. Fundamental issues that arise in reliable and
efficient distributed systems include developing adequate methods for
modeling failures and synchrony assumptions, determining precise
performance bounds on implementations of concurrent data structures,
capturing the trade-off between consistency and efficiency, and
demarcating the frontier of feasibility in distributed computing.
For example, popular Internet services and applications such as CNN.com, YouTube, Facebook, Skype, BitTorrent attract millions of users every day, and only by the effective load-balancing and collaboration of many thousand machines, an acceptable Quality-of-Service/Quality-of-Experience can be guaranteed. While distributed systems promise a good scalability as well as a high robustness, they pose challenging research problems, such as: How to design robust and scalable distributed architectures and services? How to coordinate access to a shared resource, e.g., by electing a leader? Or how to provide incentives for cooperation in an open, collaborative distributed system?
|Autor||Gafni, Eli and Kuznetsov, Petr|
|Buchtitel||Proceedings of 14th International Conference On Principles Of Distributed Systems (OPODIS '10)|
|Adresse||Berlin / Heidelberg, Germany|
|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.|