On Multicast Primitives in Large Networks and Partial Replication Protocols

Staff - Faculty of Informatics

Start date: 9 October 2009

End date: 10 October 2009

On Friday October 9th, 2009 at 15h30 in the Informatics Building (room SI-006), Mr. Nicolas SCHIPER will defend his Ph.D. dissertation titled:

'On Multicast Primitives in Large Networks and Partial Replication Protocols'

The dissertation committee is composed of:

  • Prof. Fernando Pedone, Università della Svizzera Italiana, Switzerland (advisor)
  • Prof. Antonio Carzaniga, Università della Svizzera Italiana, Switzerland (internal member)  
  • Prof. Matthias Hauswirth, Università della Svizzera Italiana, Switzerland (internal member) 
  • Prof. Lorenzo Alvisi, University of Texas at Austin, United Sates (external member) 
  • Prof. Robbert van Renesse, Cornell University, United Sates (external member) 



Recent years have seen the rapid growth of internet-scale applications such as search engines, social networks, and e-commerce platforms. These applications are often composed of several data centers to provide low latency to clients. To handle high loads, data centers typically consist of thousands of computers. In these settings, failures are the norm rather than the exception. Reliability and scalability are thus of prime importance.

In this thesis, we consider large networks composed of several groups of machines located in the same geographical region. Groups may be data centers, each located in a local area network, connected through high-latency links. In these settings, the goal is to minimize the use of inter-group links. We mask failures using data replication: if one copy of the data is not available, a replica is accessed instead.

Guaranteeing data consistency in the presence of failures while offering good performance constitutes the main challenge of this thesis.

To reach this goal, we first study and devise fault-tolerant multicast communication primitives that offer various message ordering guarantees.

The majority of the algorithms we present are latency-optimal and either assume that each group contains at least one process that is always alive, or do not have this assumption, in which case groups may entirely crash.

We then rely on these multicast abstractions to propose replication protocols in which machines hold a subset of the application’s data, denoted partial replication. In contrast to full replication, partial replication may potentially offer better scalability since updates need not be applied to every machine in the system.