Distributed Universal Constructions: a Guided TourReport as inadecuate

Distributed Universal Constructions: a Guided Tour - Download this document for free, or read online. Document in PDF available to download.

1 IUF - Institut Universitaire de France 2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE

Abstract : The notion of a universal construction is central in computing science: the wheel has not to be reinvented for each new problem. In the context of n-process asynchronous distributed systems, a universal construction is an algorithm that is able to build any object defined by a sequential specification despite the occurrence of up to n − 1 process crash failures. The aim of this paper is to present a guided tour of such universal constructions. Its spirit is not to be a catalog of the numerous constructions proposed so far, but a as simple as possible presentation of the basic concepts and mechanisms that constitute the basis these constructions rest on.

Keywords : Abortable object Agreement problem Asynchronous read-write system Atomic opera- tions Computability Concurrent object Consensus Crash failure Disjoint-access parallelism Help mechanism LL-SC instruction Memory location Non-blocking Obstruction-freedom Progress condition Sequential specification k-Set agreement k-Simultaneous consensus Speculative execu- tion Universal construction Wait-freedom

Author: Michel Raynal -

Source: https://hal.archives-ouvertes.fr/


Related documents