A Leader Election Protocol for Fault Recovery in Asynchronous Fully-Connected Networks

Abstract

We introduce a new algorithm for consistent failure detection in asynchronous systems. Informally, consistent failure detection requires processes in a distributed system to distinguish between two different populations: a fault free population and a faulty one. The major contribution of this paper is in combining ideas from group membership and leader election, in order to have an election protocol for a fault manager whose convergence is delayed until a new consistent view of the connectivity of the network is established by all processes. In our algorithm a group of processes agrees upon the failed population of the system, and then gives to a unique leader, called the fault manager, the possibility of executing distributed tasks in a centralized way. This research and the new perspective that we propose are driven by the study of an actual system, the Caltech RAIN (Reliable Array of Independent Nodes), on which our protocol has been implemented in order to perform fault recovery in distributed checkpointing. Other potential applications include fault tolerant distributed database services and fault tolerant distributed web servers.