January 20 – 25 , 2013, Dagstuhl Seminar 13042
Epidemic Algorithms and Processes: From Theory to Applications
1 / 2 >
For support, please contact
The Dagstuhl seminar 13042 "Epidemic Algorithms and Processes: From Theory to Applications" took place from January 20 to 25, 2013, and the main goal of the seminar was to fertilize interaction between theory and applications in this emerging research area. Especially in the algorithmic community several fundamentally new ideas have been developed in recent years. At our Dagstuhl seminar, we explored them further, by mixing various ideas coming from experts working on different fields. Theoretical computer scientists presented their results and methods, in order to disseminate them to a wider community. Researchers from application areas presented their curent findings and new challenging research directions, in order to influence (theoretical) research toward real-world applications. The interaction between the seminar participants led to ample discussions and further research collaborations between different domains.
Epidemic algorithms provide a powerful paradigm for distributed computing. Some of the most interesting application areas are the efficient dissemination of updates in replicated data-bases, as well as data dissemination in peer-to-peer sytems or wireless sensor networks. By contacting random neighbors in parallel, and making them join forces, an epidemic like progress can be achieved. Furthermore, epidemic processes inherently possess a high level of simplicity and robustness, and therefore the corresponding algorithms can easily deal with the dynamically changing structure of the networks mentioned before.
Theoretical Computer Science makes these useful observations precise and provides certain performance guearantees. One of the well-known algorithms is the so called randomized rumor spreading, which disseminates a piece of information in a network to all nodes in a number of communication rounds. In the corresponding communication model, in each round every informed node (i.e, a node which possesses the message) passes/retrieves the information to/from a randomly chosen neighbor. Since 2008, epidemic algorithms received an increased attention by the theory community, leading to a series of new developments such as the development of new analysis techniques for e.g. the bit-complexity of random phone call algorithms, flooding protocols for dynamic graphs, or relating the performance of an epidemic algorithm to the conductance of the network. On the other side, new algorithm design principles have been introduced, which allow the nodes to remember (and avoid) a certain number of previously contacted neighbors, or the use of intentionally dependent randomized decisions. The first modification resulted in an exponential improvement in the number of message transmissions, and lead to the remarkable result that in social networks information can be spread in sublogarithmic time. The second idea gave rise to a number of high-quality papers ranging from, e.g., a theoretical analysis of the amount of randomness needed to the design of the first epidemic rumor spreading algorithm having a safe termination criterion.
One of the main goals of the seminar was to intensify the collaboration between theory and application fields on epidemic algorithms and processes. We mainly concentrated on two major applications. The first one focuses on the construction and maintenance of peer-to-peer networks in a highly dynamic scenario. Since the epidemic algorithms described above are scalable, robust against edge or node failures, and only require a small amount of message transmissions, they can successfully deal with the challenges imposed in a peer-to-peer environment.
The second focus was on the generation of personalized connections in social networks by using epidemic algorithms. Personalization is applied to fundamental processes such as dissemination, search, and navigation, in order to improve the benefits of social networking. The generated views give rise to certain clusters within the network, and the gossip algorithm for communicating profiles and broadcasting messages distinguishes then between intra-cluster and inter-cluster connections.
Creative Commons BY 3.0 Unported license
Benjamin Doerr,Robert Elsässer, Pierre Fraigniaud and Rachid Guerraoui
Creative Commons BY 3.0 Unported license
Benjamin Doerr and Robert Elsässer and Pierre Fraigniaud
- Data Structures / Algorithms / Complexity
- Epidemic algorithms
- Gossip-based algorithms
- Rumor spreading
- Distributed computing
- Randomized algorithms
- Wireless sensor networks