M. Ajtai, J. Komlós, and E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing , STOC '83, pp.1-9, 1983.
DOI : 10.1145/800061.808726

D. Alistarh, J. Aspnes, S. Gilbert, and R. Guerraoui, The Complexity of Renaming, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp.718-727, 2011.
DOI : 10.1109/FOCS.2011.66

D. Angluin, J. Aspnes, J. Chen, Y. Wu, and Y. Yin, Fast construction of overlay networks, Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures , SPAA'05, pp.145-154, 2005.
DOI : 10.1145/1073970.1073991

H. Attiya, A. Bar-noy, D. Dolev, D. Peleg, and R. Reischuk, Renaming in an asynchronous environment, Journal of the ACM, vol.37, issue.3, pp.524-548, 1990.
DOI : 10.1145/79147.79158

K. E. Batcher, Sorting networks and their applications, Proceedings of the April 30--May 2, 1968, spring joint computer conference on, AFIPS '68 (Spring), pp.307-314, 1968.
DOI : 10.1145/1468075.1468121

M. Bawa, H. Garcia-molina, A. Gionis, and R. Motwani, Estimating Aggregates on a Peer-to-Peer Network, 2003.

P. Berenbrink, R. Elsässer, and T. Friedetzky, Efficient randomized broadcasting in random regular networks with applications in peer-to-peer systems, Proc. 27th PODC, pp.155-164, 2008.

S. P. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Randomized gossip algorithms, IEEE Transactions on Information Theory, vol.52, issue.6, pp.2508-2530, 2006.
DOI : 10.1109/TIT.2006.874516

C. Cooper, M. E. Dyer, and A. J. Handley, The flip markov chain and a randomising P2P protocol, Proceedings of the 28th ACM symposium on Principles of distributed computing, PODC '09, pp.141-150, 2009.
DOI : 10.1145/1582716.1582742

A. J. Demers, D. H. Greene, C. Hauser, W. Irish, J. Larson et al., Epidemic algorithms for replicated database maintenance, Proc. 6th PODC, pp.1-12, 1987.

M. Dietzfelbinger and P. Woelfel, Tight lower bounds for greedy routing in uniform small world rings, Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, STOC '09, pp.591-600, 2009.
DOI : 10.1145/1536414.1536494

B. Doerr and M. Fouz, Asymptotically optimal randomized rumor spreading, Proc. 38th ICALP, pp.502-513, 2011.

B. Doerr, M. Fouz, and T. Friedrich, Social networks spread rumors in sublogarithmic time, Proc. 43rd STOC, pp.21-30, 2011.

B. Doerr, T. Friedrich, and T. Sauerwald, Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness, Proc. 36th ICALP, pp.366-377, 2009.
DOI : 10.1007/978-3-642-02927-1_31

R. Elsässer and T. Sauerwald, On the runtime and robustness of randomized broadcasting, Theoretical Computer Science, vol.410, issue.36, pp.3414-3427, 2009.
DOI : 10.1016/j.tcs.2008.04.017

T. Feder, A. Guetz, M. Mihail, and A. Saberi, A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp.69-76, 2006.
DOI : 10.1109/FOCS.2006.5

P. Felber, Epidemic algorithms: A " systems " perspective. Talk at the Dagstuhl Seminar 13042, Epidemic Algorithms and Processes: From Theory to Practice, Slides available online at, 2013.

N. Fountoulakis, A. Huber, and K. Panagiotou, Reliable Broadcasting in Random Networks and the Effect of Density, 2010 Proceedings IEEE INFOCOM, pp.2552-2560, 2010.
DOI : 10.1109/INFCOM.2010.5462084

G. Giakkoupis, Tight bounds for rumor spreading in graphs of a given conductance, Proc. 28th STACS, pp.57-68, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00573638

M. Jelasity and A. Kermarrec, Ordered Slicing of Very Large-Scale Overlay Networks, Sixth IEEE International Conference on Peer-to-Peer Computing (P2P'06), pp.117-124, 2006.
DOI : 10.1109/P2P.2006.25

M. Jelasity, S. Voulgaris, R. Guerraoui, A. Kermarrec, and M. Van-steen, Gossip-based peer sampling, ACM Transactions on Computer Systems, vol.25, issue.3, p.8, 2007.
DOI : 10.1145/1275517.1275520

R. M. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking, Randomized rumor spreading, Proceedings 41st Annual Symposium on Foundations of Computer Science, pp.565-574, 2000.
DOI : 10.1109/SFCS.2000.892324

D. Kempe, A. Dobra, and J. Gehrke, Gossip-based computation of aggregate information, 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp.482-491, 2003.
DOI : 10.1109/SFCS.2003.1238221

D. Kempe, J. M. Kleinberg, and A. J. Demers, Spatial gossip and resource location protocols, Journal of the ACM, vol.51, issue.6, pp.943-967, 2004.
DOI : 10.1145/1039488.1039491

J. M. Kleinberg, Navigation in a small-world, Nature, p.845, 2000.

J. M. Kleinberg, The small-world phenomenon, Proceedings of the thirty-second annual ACM symposium on Theory of computing , STOC '00, pp.163-170, 2000.
DOI : 10.1145/335305.335325

D. E. Knuth, Sorting and Searching, The Art of Computer Programming, vol.3, 1998.

D. Mosk-aoyama and D. Shah, Fast Distributed Algorithms for Computing Separable Functions, IEEE Transactions on Information Theory, vol.54, issue.7, pp.2997-3007, 2008.
DOI : 10.1109/TIT.2008.924648

I. Stoica, R. Morris, D. Liben-nowell, D. R. Karger, M. F. Kaashoek et al., Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking, vol.11, issue.1, pp.17-32, 2003.
DOI : 10.1109/TNET.2002.808407

A. C. Yao and F. F. Yao, On Fault-Tolerant Networks for Sorting, SIAM Journal on Computing, vol.14, issue.1, pp.120-128, 1985.
DOI : 10.1137/0214009