Revisiting the algorithm

by: Roberto D Prisco, Butler Lampson, Nancy Lynch

Theoretical Computer Science, Vol. 243, No. 1-2. (28 July 2000), pp. 35-91.

View FullText article

DOI, ScienceDirect

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

kistijantoro, rahul, iunadi, SRL (group), HenryR, ddqseven

Find related articles with these CiteULike tags

algorithm, consensus, distributedsystems, general_timed_automaton, gta, io_automata, nonblocking, no-tag, paxos

Abstract

The algorithm is an efficient and highly fault-tolerant algorithm, devised by Lamport, for reaching consensus in a distributed system. Although it appears to be practical, it seems to be not widely known or understood. This paper contains a new presentation of the algorithm, based on a formal decomposition into several interacting components. It also contains a correctness proof and a time performance and fault-tolerance analysis. The formal framework used for the presentation of the algorithm is provided by the Clock General Timed Automaton (Clock GTA) model. The Clock GTA provides a systematic way of describing timing-based systems in which there is a notion of "normal" timing behavior, but that do not necessarily always exhibit this "normal" timing behavior.

@article{citeulike:93197, abstract = {The algorithm is an efficient and highly fault-tolerant algorithm, devised by Lamport, for reaching consensus in a distributed system. Although it appears to be practical, it seems to be not widely known or understood. This paper contains a new presentation of the algorithm, based on a formal decomposition into several interacting components. It also contains a correctness proof and a time performance and fault-tolerance analysis. The formal framework used for the presentation of the algorithm is provided by the Clock General Timed Automaton (Clock GTA) model. The Clock GTA provides a systematic way of describing timing-based systems in which there is a notion of "normal" timing behavior, but that do not necessarily always exhibit this "normal" timing behavior.}, author = {Prisco, Roberto D. and Lampson, Butler and Lynch, Nancy }, citeulike-article-id = {93197}, doi = {10.1016/S0304-3975(00)00042-6}, journal = {Theoretical Computer Science}, keywords = {algorithm}, month = {July}, number = {1-2}, pages = {35--91}, posted-at = {2007-05-28 11:10:16}, priority = {2}, title = {Revisiting the algorithm}, url = {http://dx.doi.org/10.1016/S0304-3975(00)00042-6}, volume = {243}, year = {2000} }

RIS record

TY - JOUR ID - citeulike:93197 L3 - citeulike-article-id:93197 TI - Revisiting the algorithm JF - Theoretical Computer Science VL - 243 IS - 1-2 SP - 35 EP - 91 N2 - The algorithm is an efficient and highly fault-tolerant algorithm, devised by Lamport, for reaching consensus in a distributed system. Although it appears to be practical, it seems to be not widely known or understood. This paper contains a new presentation of the algorithm, based on a formal decomposition into several interacting components. It also contains a correctness proof and a time performance and fault-tolerance analysis. The formal framework used for the presentation of the algorithm is provided by the Clock General Timed Automaton (Clock GTA) model. The Clock GTA provides a systematic way of describing timing-based systems in which there is a notion of "normal" timing behavior, but that do not necessarily always exhibit this "normal" timing behavior. KW - algorithm AU - Prisco, Roberto AU - Lampson, Butler AU - Lynch, Nancy PY - 2000/07/28/ UR - http://dx.doi.org/10.1016/S0304-3975(00)00042-6 ER -

RIS BibTeX