11th Pacific Rim International Symposium on Dependable Computing (PRDC'05) Intersecting Sets: a Basic Abstraction for Asynchronous Agreement Problems Changsha, Hunan, China December 12-December 14 ISBN: 0-7695-2492-3
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PRDC.2005.37
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||