The Notion of Universality in Crash-Prone Asynchronous Message-Passing Systems: a Tutorial

The notion of a universal construction is central in computing science and technology: general solutions make life easier and the wheel has not to be reinvented each time a new problem appears. In the context of message-passing asynchronous distributed systems made up of n processes, where some of them may commit crash failures, a universal construction is an algorithm that is able to build any object defined by a sequential specification despite the adversary effect resulting from the combination of asynchrony and process crashes. The aim of this tutorial is to introduce the reader to the notion of a distributed universal construction (and universal objects these constructions rely on), and more precisely, explain what can be done, what cannot be done, and which assumptions on the environment are necessary in order objects with provably reliability properties can be built. Its aim is be a guided tour providing the reader with the basic knowledge needed to understand and master asynchronous message-passing fault-tolerant computing. Its spirit is not to be a catalog of constructions proposed so far, but an as simple as possible presentation of concepts and mechanisms that constitute the basis these universal constructions rely on.