EpTO: An Epidemic Total Order Algorithm for Large-Scale Distributed Systems
Hugues Mercier (Université de Neuchâtel)
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 presented in this talk 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.
Hugues Mercier received the Ph.D. degree in electrical and computer engineering from the University of British Columbia in 2008. From 2008 to 2011, he was a postdoctoral research fellow at the Harvard School of Engineering and Applied Sciences, and at McGill University. Currently, he is a researcher at the Université de Neuchâtel in Switzerland. His current interests are the applications of coding theory, information theory, and algorithms to the study of communication networks. With a background in Mathematics, Computer Science and Electrical Engineering, he enjoys solving applied problems supported by theoretical results allowing a better understanding of the behavior and limits of communication systems.
Back to EBSIS Events section.