Epidemic algorithms for large scale data dissemination

Abstract

Distributed systems lie at the core of modern IT infrastructures and services, such as the Internet, e-commerce, the stock exchange, Cloud Computing and the SmartGrid. These systems, built and developed throughout the last decades, have relied, due to their importance, on distributed algorithms with strong cor- rectness and safety guarantees. However, such algorithms have failed to accom- pany, for theoretical and practical reasons, the requirements of the distributed systems they support in terms of scale, scope and pervasiveness. Reality is unfor- giving and thus researchers had the need to design and develop new algorithms based on probabilistic principles that, despite their probabilistic yet quantifiable guarantees, are suitable to today’s modern distributed systems. In this dissertation, we study the challenges of and propose solutions for, ap- plying probabilistic dissemination algorithms, also known as epidemic- or gossip- based, in very large scale distributed systems. In particular, we focus on the issues of scalability of content types (topic-based publish-subscribe), content size (efficient data dissemination) and ordering requirements (total order). For each one of these issues, we present a novel distributed algorithm that solves the prob- lem while matching state-of-the art performance and trade-offs, and evaluate it on a realistic setting.