For the most recent entries see the Petri Nets Newsletter.

Revisiting the Paxos Algorithm.

De Prisco, Roberto; Lampson, Butler; Lynch, Nancy

In: Mavronicolas, M.; Tsigas, Ph.: Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany, pages 111-125. Springer, September 1997.

Abstract: This paper develops a new I/O automaton model called the Clock General Timed Automaton (Clock GTA) model. The Clock GTA is based on the General Timed Automaton (GTA) of Lynch and Vaandrager. 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'' behavior. It can be used for practical time performance analysis based on the stabilization of the physical system. We use the Clock GTA automaton to model, verify and analyze the PAXOS algorithm. The PAXOS 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 is not widely known or understood. This paper contains a new presentation of the PAXOS algorithm, based on a formal decomposition into several interacting components. It also contains a correctness proof and a time performance and fault-tolerance analysis.

Keywords: I/O automata models, formal verification, distributed consensus, partially synchronous systems, fault-tolerance.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography