N. Set, M. {?}, and . {?}, Send request(Nr) to the replier r

N. {r}, else {r has not answered after t time-steps are elapsed} 11: Abort the random exchange; 12: end if Algorithm 5 GRPSd Replier r: Passive Thread 1: If performing, finish the previous random exchange Send Nr to the petitioner, wait for the answer, |N \M | = c ? 1 then 5: Set N \M := N \M ? {p} Nr := N \M , the new set of neighbors of r

A. J. Demers, D. H. Greene, C. Hauser, W. Irish, J. Larson et al., Epidemic algorithms for replicated database maintenance, ACM SIGOPS Operating Systems Review, vol.22, issue.1, pp.8-32, 1988.
DOI : 10.1145/43921.43922

M. Jelasity, A. Montresor, and O. Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems, vol.23, issue.3, pp.219-252, 2005.
DOI : 10.1145/1082469.1082470

M. Jelasity, A. Montresor, and . Babaoglu, A Modular Paradigm for Building Self-Organizing Peer-to-Peer Applications, Proc. of the Engineering Self-Organising Systems, Nature-Inspired Approaches to Software Engineering, pp.265-282, 2003.
DOI : 10.1007/978-3-540-24701-2_18

S. Voulgaris and M. Van-steen, An Epidemic Protocol for Managing Routing Tables in Very Large Peer-to-Peer Networks, Proc. of DSOM, pp.41-54, 2003.
DOI : 10.1007/978-3-540-39671-0_5

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

Q. Sun and D. C. Sturman, A gossip-based reliable multicast for large-scale high-throughput applications, Proc. of DSN, p.347, 2000.

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, pp.8-43, 2007.
DOI : 10.1145/1275517.1275520

M. Gurevich and I. Keidar, Correctness of gossip-based membership under message loss, Proc. of PODC, pp.151-160, 2009.

E. Bortnikov, M. Gurevich, I. Keidar, G. Kliot, and A. Shraer, Brahms, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, PODC '08, pp.145-154, 2008.
DOI : 10.1145/1400751.1400772

Z. Bar-yossef, R. Friedman, and G. Kliot, RaWMS -, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing , MobiHoc '06, pp.238-249, 2006.
DOI : 10.1145/1132905.1132932

C. Gkantsidis, M. Mihail, and A. Saberi, Random walks in peer-topeer networks, P2P Computing Systems, vol.63, issue.3, pp.241-263, 2006.

C. Avin, M. Kouck´ykouck´y, and Z. Lotker, How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs), Proc. of ICALP, pp.121-132, 2008.
DOI : 10.1007/978-3-540-70575-8_11

C. Cooper, M. 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

P. Mahlmann and C. Schindelhauer, Distributed random digraph transformations for peer-to-peer networks, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures , SPAA '06, pp.308-317, 2006.
DOI : 10.1145/1148109.1148162

F. Bonnet, F. Tronel, and S. Voulgaris, Brief Announcement: Performance Analysis of Cyclon, an Inexpensive Membership Management for Unstructured P2P Overlays, Proc. of DISC, pp.560-562, 2006.
DOI : 10.1007/11864219_45

A. Bakker and M. Van-steen, PuppetCast: A Secure Peer Sampling Protocol, 2008 European Conference on Computer Network Defense, pp.3-10, 2008.
DOI : 10.1109/EC2ND.2008.7

S. Voulgaris, D. Gavidia, and M. Van-steen, CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays, Journal of Network and Systems Management, vol.21, issue.6, pp.197-217, 2005.
DOI : 10.1007/s10922-005-4441-x

P. Mahlmann and C. Schindelhauer, Peer-to-peer networks based on random transformations of connected regular undirected graphs, Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures , SPAA'05, pp.155-164, 2005.
DOI : 10.1145/1073970.1073992

M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2005.
DOI : 10.1017/CBO9780511813603