Non-blocking atomic commitment in distributed systems: A tutorial based on a generic protocol

Agreement problems allow a set of processes to agree on a common output value. These problems are of primary importance in distributed systems and difficult to solve in presence of failures. This paper is a tutorial on one of these problems whose practical interest is well known, namely the Non-Blocking Atomic Commitment Problem This tutorial is based on an original generic protocol that solves the problem at an abstract level. Instantiations of its generic statements are given for both synchronous and asynchronous distributed systems. It is shown that the main problem to ensure the "non-blocking" property lies in failures detection. While failures can be safely detected in synchronous distributed systems, they can only be "suspected" (maybe falsely) in asynchronous distributed systems. So, this tutorial also visits problems such as reliable communication, failures detection and consensus whose solutions are used when instantiating the generic protocol in a particular context. Seen that way, this paper can be seen as a state-of-the-art introduction to concepts, problems and protocols related to fault-tolerance in distributed systems.