Dagstuhl Seminar 13042
Epidemic Algorithms and Processes: From Theory to Applications
( Jan 20 – Jan 25, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/13042
Organizers
- Benjamin Doerr (MPI für Informatik - Saarbrücken, DE)
- Robert Elsässer (Universität Salzburg, AT)
- Pierre Fraigniaud (University of Paris VII, FR)
- Rachid Guerraoui (EPFL - Lausanne, CH)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Epidemic algorithms provide a powerful paradigm for distributed computing: By contacting random neighboring nodes and making them join forces, an epidemic-like progress can be achieved. This was first applied to efficiently disseminate updates in distributed data-bases.
Today, epidemic algorithms are massively applied in peer-to-peer communication as well as in wireless sensor networks and ad-hoc networks. Since epidemic processes inherently possess a high level of simplicity and robustness, these algorithms can easily deal with various computationally harsh settings, e.g., dynamically changing structures. In particular in the last few years, also the theoretical computer science community added significantly to the understanding of epidemic algorithms and developed new approaches. This not only includes several new analysis techniques, but also new ideas in the design of such algorithms leading to significant speed-ups, to greatly reduced communication efforts or to provably safe termination criteria.
In addition, computer science methods proved to be applicable to epidemic processes from other fields like viral marketing and mathematical epidemiology. In this Dagstuhl Seminar, we bring together experts both from the theory community and from different application areas. We shall discuss the recent advances in theoretical and applied research, hopefully intensifying the dialogue between the different areas.
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
- Chen Avin (Ben Gurion University - Beer Sheva, IL) [dblp]
- Keren Censor-Hillel (MIT - Cambridge, US) [dblp]
- Pierluigi Crescenzi (University of Florence, IT) [dblp]
- Oksana Denysyuk (INESC-ID - Lisboa, PT) [dblp]
- Benjamin Doerr (MPI für Informatik - Saarbrücken, DE) [dblp]
- Carola Doerr (MPI für Informatik - Saarbrücken, DE) [dblp]
- Robert Elsässer (Universität Salzburg, AT) [dblp]
- Pascal Felber (Université de Neuchâtel, CH) [dblp]
- Pierre Fraigniaud (University of Paris VII, FR) [dblp]
- Davide Frey (INRIA Rennes - Bretagne Atlantique, FR) [dblp]
- Tobias Friedrich (Universität Jena, DE) [dblp]
- Chryssis Georgiou (University of Cyprus, CY) [dblp]
- George Giakkoupis (INRIA Rennes - Bretagne Atlantique, FR) [dblp]
- Bernhard Haeupler (MIT - Cambridge, US) [dblp]
- Hovhannes a. Harutyunyan (Concordia University - Montreal, CA) [dblp]
- Anna Huber (Durham University, GB) [dblp]
- Amos Korman (University of Paris I, FR) [dblp]
- Silvio Lattanzi (Google - New York, US) [dblp]
- Andrea Marino (University of Florence, IT) [dblp]
- Gerhard Niederbrucker (Universität Wien, AT) [dblp]
- Adrian Ogierman (Universität Paderborn, DE) [dblp]
- Konstantinos Panagiotou (LMU München, DE) [dblp]
- Alessandro Panconesi (Sapienza University of Rome, IT) [dblp]
- Francesco Pasquale (Sapienza University of Rome, IT) [dblp]
- Luis Rodrigues (Technical University of Lisboa, PT) [dblp]
- Stefan Rührup (FTW Forschungszentrum Telekommunikation Wien GmbH, AT) [dblp]
- Thomas Sauerwald (MPI für Informatik - Saarbrücken, DE) [dblp]
- Christian Schindelhauer (Universität Freiburg, DE) [dblp]
- He Sun (MPI für Informatik - Saarbrücken, DE) [dblp]
- Philipp Woelfel (University of Calgary, CA) [dblp]
Classification
- data structures / algorithms / complexity
- networks
Keywords
- Epidemic algorithms
- gossip-based algorithms
- rumor spreading
- distributed computing
- randomized algorithms
- wireless sensor networks
