loading...
Intersecting Sets: a Basic Abstraction for Asynchronous Agreement Problems
Changsha, Hunan, China December 12-December 14
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PRDC.2005.3711th Pacific Rim International Sympos ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Roy FRIEDMAN, Technion, Haifa 32000, Israel
Achour MOSTEFAOUI, IRISA, Universite de Rennes 1, Campus de Beaulieu, 35042 Rennes Cedex, France
Michel RAYNAL, IRISA, Universite de Rennes 1, Campus de Beaulieu, 35042 Rennes Cedex, France

Defining good abstractions is a central issue when one wants to understand the deep structure and basic principles that underlie computing mechanisms. This paper introduces a basic and particularly simple distributed computing abstraction suited to asynchronous distributed agreement problems. This abstraction, called Intersecting Sets, requires each process to deposit a value and allows each non-faulty process to obtain a subset of these values such that any two such sets have a non-empty intersection. This simple abstraction captures an essential part of distributed agreement problems. After having introduced and motivated this abstraction, the paper investigates its properties, its power and its benefit when solving distributed agreement problems.

Index Terms:
Asynchronous system, Computing abstraction, Consensus, Distributed algorithm, Failure detector, Message passing, Non blocking atomic commit.
Citation:
Roy FRIEDMAN, Achour MOSTEFAOUI, Michel RAYNAL, "Intersecting Sets: a Basic Abstraction for Asynchronous Agreement Problems," prdc, pp.15-22, 11th Pacific Rim International Symposium on Dependable Computing (PRDC'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.