I meccanismi proposti danno un buon contributo in termini di raggiungibilit`a media, ma una questione fondamentale che deve essere chiarita `e il costo di questo miglioramento in termini di crescita della dimensione della vista. Da una prima analisi si `e riscontrato un aumento delle dimensioni delle viste che non consente di mantenere la peculiarit`a di SCAMP (ossia la crecita in maniera logaritmica del degree rispetto alla dimensione del sistema) ma che `e considerata tuttavia sopportabile per un’applicazione; il passo successivo da compiere, verso cui `e rivolto il seguito del presente studio, `e lo studio della variazione delle dimensioni della vista scalando sulla dimensione del sistema.
[1] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart & D. Terry . Epidemic Algorithms for Replicated Database Maintenance. Proceedings of the 6th annual ACM Symposium on Principles of Distributed Computing, 1987.
[2] A. Rowstron and P. Druschel. Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. In Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms, vol. 2218, 2001.
[3] A. Stavrou, D. Rubenstein, & S. Sahu. A lightweight, robust p2p system to handle flash crowds. IEEE Journal on Selected Areas in Communications, 2004.
[4] A.Fiat and J.Saia. Censorship resistant peer-to-peer content addressable networks. Pro-ceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, USA, 2002.
[5] A.J. Demers, D.H. Greene, C. Hauser, W. Irish, and J. Larson. Epidemic algorithms for replicated database maintenance. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 1-12, Vancouver, British Columbia, Canada, August 1987.
[6] A.M. Kermarrec, L. Massouli´e, and A.J. Ganesh. Probabilistic reliable dissemination in large-scale systems. IEEE Transactions on Parallel and Distributed Systems.
[7] Y. Amir, D. Dolev, S. Kramer, and D. Malki. Transis: A Communication Sub-System for High Availability. In Proc. of the 22nd Annual International Symposium on Fault-Tolerant Computing, pages 76–84, July 1992.
[8] Andr´e Allavena, Alan Demers, John E. Hopcroft. Correctness of a Gossip Based Membership Protocol. To appear in PODC’05, July 2005.
[9] Androutsellis-Theotokis & Spinellis. Correctness of a gossip based membership protocol. in Proceedings of the twenty-fourth annual ACM SIGACTSIGOPS symposium on Principles of Distributed Computingu, 2004.
[10] Ayalvadi J. Ganesh, Anne-Marie Kermarrec, Laurent Massouli´e. Peer-to-Peer Membership Management for Gossip-Based Protocols. IEEE Trans. Computers 52(2): 139-149, 2003. [11] R. Baldoni, S. Bonomi, L. Querzoni, A. Rippa, S. Tucci Piergiovanni, and A. Virgillito.
Evaluation of Unstructured Overlay Maintenance Protocols under Churn. In Technical Report - MIDLAB 2/06 , Dip. Informatica e Sistemistica, Universit`a di Roma La Sapienza, 2006, (to appear) International Workshop on Dynamic Distributed Systems (IWDDS), 1 2006.
[12] K. Birman. The Process Group Approach to Reliable Distributed Computing. Communications of the ACM, 36(12):37–53, December 1993.
[13] Castro M., Costa M. & Rowstron A. Peer-to-peer overlays: structured, unstructured, or both? tech. rep., microsoft research, 2004.
[14] Chonggang Wang, Bo Ling. Peer-to-Peer Overlay Networks: A Survey. Technical Report, April, 20 2003.
[15] Cohen, E. & Shenker, S. Replication strategies in unstructured peer-to-peer networks., 2002. http://citeseer.ist.psu.edu/cohen02replication.html.
[16] F. Cristian. Probabilistic Clock Synchronization. Distributed Computing, 3:146–158, 1989. [17] Lewin D. Consistent hashing and random trees: Algorithms for caching in distributed
networks. Master’ s thesis, MIT, 1998. http://thesis.mit.edu.
[18] D. Dolev, D. Malki and H.R. Strong. A Framework for Partitionable Membership Service. TR 95-4, Institute of Computer Science, Hebrew University, March 1995.
[19] D. Dolev, G. Chockler, N. Huleihel. An adaptive totally ordered multicast protocol that tolerates partitions. In 17th ACM Symposium on Principles of Distributed Computing (PODC), pp. 237-246, June 1998.
[20] Daniel Stutzbach, Reza Rejaie. Characterizing Churn in Peer-to-Peer Networks. Technical Report CIS-TR-05-03, June 2003. Department of Computer Science, University of Oregon. [21] D. Dolev, C. Dwork, and L. Stockmeyer. On the Minimal Synchronism Needed for
Distributed Consensus. Journal of the ACM, 34(1):77–97, January 1987.
[22] D.S.Milojicic, V.Kalogeraki, R.Lukose, K.Nagaraja, J.Pruyne, B.Richard, S.Rollins & Z.Xu. Peer-to-peer computing. tech. rep., hewlett-packard development company, 2002. [23] C. Dwork and N.A. Lynch L. Stockmeyer. Consensus in the Presence of Partial Synchrony.
Journal of the ACM, 35(2):288–323, April 1988.
[24] P. Ezhilchelvan, R. Macedo, and S. Shrivastava. Newtop: A Fault-Tolerant Group Com-munication Protocol. Technical report, Computer Science Department, University of Newcastle, Newcastle upon Tyne, United Kingdom, August 1994.
[25] Ayalvadi J. Ganesh, Anne-Marie Kermarrec, and Laurent Massouli´e. Scamp: Peer-to-peer lightweight membership service for large-scale group communication. In Third Internation-al Workshop on Networked Group Communications (NGC 2001), London, UK, November 2001.
[26] Gkantsidis, C., Mihail, M. & Saberi, A. Random walks in peer-to-peer networks., 2004. http://citeseer.ist.psu.edu/gkantsidis04random.html.
[27] Gnutella. http://www.gnutella.com.
[28] Gregory V.Chockler, Idit Keidar and Roman Vitenberg. Group Communication Specifications: A Comprehensive Study.
[29] V. Hadzilacos and S. Toueg. Faul-Tolerant Broadcast and Related Problems. In S. Mullender, editor, Distributed Systems, chapter 16. Addison Wesley, 1993.
[30] S. G. Miller O.Sandberg I. Clarke, T. W. Hong and B. Wiley. Protecting free expression online with Freenet. IEEE Internet Computing 6(1).
[31] I. Gupta, K.P. Birman, and R. van Renesse. Fighting Fire with Fire: using Random-ized Gossip to Combat Stochastic Scalability Limits. Quality and Reliability Engineering International, 18: 165-184, March 2002.
[32] David Liben-Nowell David R. Karger M. Frans Kaashoek Frank Dabek Hari Balakrishnan Ion Stoica, Robert Morris. Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications. To Appear in IEEE/ACM Transactions on Networking, August 2001. [33] John Jannotti, David K. Gifford, Kirk L. Johnson, M. Frans Kaashoek, James W. O’Toole.
Overcast: Reliable Multicasting with an Overlay Network. In OSDI, San Diego, 2000. [34] J.Saia, A.Fiat, S.Gribble, A.R.Karlin, and S.Saroiu. Dynamically fault-tolerant content
addressable networks. Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS ’02),, 2002.
[35] Karger D., Lehman E., Leighton F., Levine M., Lewin D. & Panigrahy R. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 654–663, 1997.
[36] Kenneth P. Birman and Thomas A. Joseph. Reliable Communication in the Presence of Failures. ACM Transactions on Computer Systems, 5(1): 47-76, February 1987.
[37] Kenneth P. Birman, Robert Cooper, and Barry Gleeson. Programming with process groups: group and multicast semantics. Technical report TR-91-1185, 29 January 1991. Department of Computer Science, Cornell University.
[38] L. Lamport and P. M. Melliar-Smith. Synchronizing Clocks in the Presence of Faults. Journal of the ACM, 32(1):52–78, 1985.
[39] M. Hiltunen, R. Schlichting. Properties of Membership Service. In 2nd International Symposium on Autonomous Decentralized Systems, pp. 200-207, 1995.
[40] Kazaa media desktop. http://www.kazaa.com.
[41] Miguel Castro, Peter Druschel, Anne-Marie Kermarrec and Antony Rowstron. Scribe: A Large-scale and Decentralized Application-level Multicast Infrastructure. IEEE Journal on Selected Areas in communications, 2002.
[42] Mk Jelasity, Richard Guerraoui, Anne-Marie Kermarrec and Maarten van Steen. The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-Based Implementations. Middleware, 2004.
[43] Napster. http://www.napster.com.
[44] Pandurangan G., Raghavan P. & Upfal E. Building low-diameter p2p net-works. IEEE Symposium on Foundations of Computer Science, pages 492–499, 2001. http://citeseer.ist.psu.edu/pandurangan01building.html.
[45] Patrick Th. Eugster, Rachid Guerraoui, Sidath B. Handurukande, Petr Kouznetsov, Anne-Marie Kermarrec. Lightweight Probabilistic Broadcast. ACM Trans. Comput. Syst. 21(4): 341-374, 2003.
[46] Peersim. http://peersim.sourceforge.net.
[47] B. Pittel. On spreading a rumour. SIAM J. Appl. Math., 47:213–223, 1987.
[48] B. Pittel. On spreading a rumor. SIAM Journal on Applied Mathematics, 47:213-223, 1987.
[49] Leonardo Querzoni, 2005.
[50] A. Ricciardi. Dissecting distributed coordination. In 9th International Workshop on Distributed Algorithms (WDAG), pages 101-118, September 1995.
[51] Roberto Baldoni and Sara Tucci Piergiovanni. Group Membership for Peer-to-Peer Communication. Technical Report, May 2005. available on http://www.dis.uniroma1.it/vmidlab/publications.
[52] S.E.Ansary, L.O.Alima, P.Brand & S.Haridi. A framework for peer-to-peer lookup services based on k-ary search. SICS technical report T2002–06, 2002.
[53] S.Ratnasamy, P.Francis, M.Handley, R.Karp, and S.Shenker. A scalable content addressable network. Proceedings of ACM SIGCOMM’2001, 2001.
[54] S. Voulgaris, D. Gavidia, and M. van Steen. CYCLON: Inexpensive Membership Manage-ment for Unstructured P2P Overlays. Journal of Network and System ManageManage-ment. To appear in 2005.
1.1 Classificazione dei failure model . . . 10
1.2 Riduzione di una Precise Membership a un Eventually Perfect Failure Detector . . . 19
1.3 Funzionamento dei protocolli di Gossip . . . 24
1.4 Modelli di sistema. . . 26
1.5 Modello di funzionamento di un sistema p2p centralizzato. . . 27
1.6 Strutture Napster-like e Gnutella-like . . . 29
1.7 Strutture Chord-like e CAN-like . . . 30
1.8 Key Space in Chord . . . 30
1.9 Schematizzazione di un’overlay network . . . 32
1.10 Disseminazione: uno schema . . . 35
2.1 Ricezione dei messaggi . . . 43
2.2 Management dei messaggi di New Subscription . . . 51
2.3 Management dei messaggi Forwarded Subscription . . . 51
2.4 Sottografo ottenuto in una simulazione . . . 55
2.5 Sottografo ottenuto in una simulazione dopo le leave . . . 56
2.6 ADH: Aggiornamento della vista . . . 60
2.7 ADH: Procedura di Join . . . 62
2.8 ADH: Procedura di Leave . . . 63
2.9 Cyclon: Procedura di Basic Shuffling . . . 64
2.10 Cyclon: Procedura di Enhanced Shuffling . . . 66
2.11 Cyclon: Procedura di Join . . . 68
2.12 Cyclon: Procedura di Leave . . . 70
2.13 Cyclon: Individuazione dei nodi Down . . . 71 119
2.14 Cyclon: Shortest Path e Clustering Coefficient . . . 72
2.15 Cyclon: distribuzione dell’In-degree . . . 73
2.16 Cyclon: Convergenza della distribuzione dell’In-degree . . . 73
3.1 Frammenti di un file di configurazione utilizzato in Peersim . . . 77
4.1 Variazione di R in funzione di t per differenti Churn Rate . . . 82
4.2 Stato di Clustering della rete al termine della simulazione . . . 83
4.3 Impatto della politica di View Selection su R . . . 84
4.4 Impatto della politica di Peer Selection su R . . . 85
4.5 Comparazione tra la distribuzione del degree nella nostra implemen-tazione e in quella degli autori . . . 87
4.6 Variazione della raggiungibilit`a media su scala temporale al variare del churn rate . . . 88
4.7 Clustering alla fine del periodo di stabilit`a per differenti churn rate . . . 89
4.8 Variazione della raggiungibilit`a media su scala temporale al variare della porzione di rete stabile . . . 90
4.9 Variazione di R per differenti valori di N e lo stesso rapporto N/C . . . 91
4.10 Variazione di R per diversi churn rate . . . 92
4.11 Variazione di R nel tempo per differenti valori di C . . . 93
4.12 Variazione di R in funzione del numero di operazioni per LPBCast e SCAMP . . . 94
5.1 Situazione di Leave Conflitting . . . 98
5.2 Gestione della Leave . . . 99
5.3 Gestione della ricezione dei messaggi di Update . . . 100
5.4 Meccanismo di Ack Applicato alla Procedura di Leave del Protocollo Scamp . . . 102
5.5 Schematizzazione del Meccanismo di ack . . . 103
5.6 Impatto del Meccanismo di Ack sulle Performance dell’Algoritmo Scamp 104 5.7 Impatto dei Meccanismi di Ack, Heartbeat e Ping sulle Performance dell’Algoritmo Scamp . . . 106
5.8 Diagnosi di Clustering all’Interno dell’Overlay . . . 107
5.9 Impatto dei Meccanismi di Ack, Heartbeat e Ping e dell’euristica di re-join sulle Performance dell’Algoritmo Scamp . . . 109
5.10 Variazione di R durante il periodo di stabilit`a sfruttando l’euristica di re-join . . . 110 5.11 Variazione del Clustering durante il periodo di stabilit`a . . . 110