Self-organizing overlays networks may be used by many peer-to-peer applications over the Internet including large-scale event-notification or resource management. In our work, we seek to develop fully decentralized algorithms for constructing and maintaining peer-to-peer overlay networks. The goal is to support communication in very large groups of peer nodes (thousands to millions of nodes) spread over a wide area without requiring coordination between peers. We are in particular  investigating the use of probabilistic techniques to provide reliable and scalable delivery of information in large-scale settings.  These algorithms exhibit  a very stable behaviour in the presence of multiple transient unavailability of  link and participants.  The reliability of most  probabilistic gossip schemes depends on each user having knowledge of the global membership and choosing gossip targets uniformly at random. The requirement of global knowledge is undesirable in large-scale distributed systems. We are currently working on novel peer-to-peer membership services in that nobody has global knowledge of membership. Especially we are focusing on self-organizing membership services for gossip-based application operating in a fully decentralized manner.

SCAMP is a peer-to-peer membership protocol designed to provide each node with a partial list of other nodes in a decentralized manner. This partial list is then used to propagate gossip messages. SCAMP is designed to provide nodes with a partial list of size clog(N) on average, the multiple c being a design parameter. The size of partial list naturally increases logarithmically as N increases. The system configures itself towards views of size clog N on average, N being the number of nodes in the system, as explained below. We are currently working on a hierarchical version of Scamp to take into account the underlying topology.

Increasing Location awareness and Failure resilience: in this work, we aim at making the overlay reflect geographic locality so as to reduce network load as well as making the overlay resilient to random node failures or disconnections.

• Spinglass Project, Cornell University
• Directional Gossip
• Gossip versus Deterministic Flooding
• SWIM Project

Papers:

A.-M. Kermarrec, L. Massoulié and A.J, Ganesh "Probabilistic Reliable Dissemination in Large-Scale Systems", IEEE Transactions on Parallel and Distributed Systems, 14(3), March 2003.

A.J. Ganesh  A.-M. Kermarrec and L. Massoulié  "Peer-to-Peer membership management for gossip-based protocols", IEEE  Transactions on Computers, 52(2), February 2003.

I. Gupta, A.-M Kermarrec, and A.J. Ganesh, "Adaptive and efficient epidemic-style protocols for reliable and scalable multicast" ps file, in Proceedings of Symposium on Reliable and Distributed Systems (SRDS 2002), October 2002, Osaka, Japan

A.J.Ganesh, A.-M Kermarrec, L. Massoulie "SCAMP: Peer-to-peer lightweight membership service for large-scale group communication", in Proceedings of the 3rd International workshop on Networked Group Communication, November 6-9, 2001, London, UK.

P.Kouznetsov, R.Guerraoui, S.B.Handurukande, A.-M.Kermarrec "Reducing Noise in Gossip-based Reliable Broadcast", in Proceedings of the 20th Symposium on  Reliable Distributed Systems (SRDS 2001), October 28-31, 2001, New Orleans, USA

Patrick Eugster, Sidath Handurukande, Rachid Guerraoui, Anne-Marie Kermarrec and Petr Kouznetsov " Lightweight Probabilistic Broadcast", Proceedings of The International Conference on Dependable Systems and Networks (DSN 2001), 01-04 July 2001, Göteborg, Sweden. An extended version to appear in ACM Transaction on Computer Systems.

A.-M.Kermarrec, L. Massoulie and A.J. Ganesh, "Reliable Probabilistic Communication in Large-Scale Information Dissemination Systems" ps file , pdf file . MMSR-TR-2000-105 Oct. 2000.

• Distributed Programming Laboratory of Swiss Federal Institute of Technology, Lausanne, Switzerland
• Department of Informatics, Faculty of Sciences, University of Lisbon, Portugal