Formal fault-tolerance proofs for distributed algorithms

Abstract

Distributed Algorithms express problems as concurrent failing processes which co- operate and interact towards a common goal. Such algorithms arise in a wide range of applications, including distributed information processing, banking systems and airline reservation systems amongst others. It is desirable that distributed algorithms are well be- haved both in a failure free environment and even in the presence of failure (i.e. fault tolerant). To ensure well behavedness for all executions of distributed algorithms formal correctness proofs are needed. This is due to the concurrent nature of such algorithms, where executions of the algorithms result in different interleavings amongst parallel pro- cesses (i.e. there is a large number of possible execution paths).