SOFSEM 2001 28th Annual Conference on Current Trends in Theory and Practice of Informatics November 24 - December 1, 2001 Piestany, Slovak Republic, Europe

Fault-Tolerant Distributed Algorithms

by Bernadette Charron-Bost

Reaching agreement in a distributed system is a fundamental issue of both theoretical and practical importance. Consensus, Atomic Commitment, Atomic Broadcast, Group Membership which are different versions of this paradigm underly much of existing fault-tolerant distributed systems. We describe these problems, explain their relationships, and state some fundamental results on their solvability, depending on the system model. We then review and compare basic techniques to circumvent impossibility results in asynchronous systems: randomization, models of partial synchrony, unreliable failure detection, hybrid algorithms. We finally discuss some open questions, and we present a few problems stemming from the design of new distributed applications.