EpTO: An Epidemic Total Order Algorithm for Large-Scale Distributed Systems

Miguel Matos, Hugues Mercier, Pascal Felber, Rui Oliveira & José Pereira

Résumé The ordering of events is a fundamental problem of distributed computing and has been extensively studied over several decades. From all the available orderings, total ordering is of particular interest as it provides a powerful abstraction for building reliable distributed applications. Unfortunately, deterministic total order algorithms scale poorly and are therefore unfit for modern large-scale applications. The main contribution of this paper is EpTO, a total order algorithm with probabilistic agreement that scales both in the number of processes and events. EpTO provides deterministic safety and probabilistic liveness: integrity, total order and validity are always preserved, while agreement is achieved with arbitrarily high probability. We show that EpTO is well-suited for large-scale dynamic distributed systems: it does not require a global clock nor synchronized processes, and it is highly robust even when the network suffers from large delays and significant churn and message loss.
Mots-clés large-scale distributed systems, data dissemination, total order, epidemic algorithm
Citation M. Matos, et al., "EpTO: An Epidemic Total Order Algorithm for Large-Scale Distributed Systems," in 2015 ACM/IFIP/USENIX Middleware conference, Vancouver, Canada, 2015.
Type Actes de congrès (Anglais)
Nom de la conférence 2015 ACM/IFIP/USENIX Middleware conference (Vancouver, Canada)
Date de la conférence 9-12-2015
URL http://dx.doi.org/10.1145/2814576.2814804