EpTO: An Epidemic Total Order Algorithm for Large-Scale Distributed Systems (Actes de congr�s) | Miguel Matos, Hugues Mercier, Pascal Felber, Rui Oliveira, Jos� Pereira - 2015 (2015 ACM/IFIP/USENIX Middleware conference)

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

Imprimer la page