Welcome to the licentiate defense of Tallat M. Shafaat, May 8 th, 2009

4 May, 2009 - 15:56

Title: Dealing with Network Partitions and Mergers in Structured Overlay

Time: May 8th, 2009
at 14:00
Location: Sal D, KTH-Forum, Isafjordsgatan 39, Kista, Stockholm

Opponent: Anwitaman Datta, NTU Singapore
Advisors: Seif Haridi and Ali Ghodsi, KTH Sweden

Thesis link:
Structured overlay networks form a major class of peer-to-peer systems,
which are touted for their abilities to scale, tolerate failures, and
self-manage. Any long lived Internet-scale distributed system is
destined to face network partitions. Although the problem of network
partitions and mergers is highly related to fault-tolerance and
self-management in large-scale systems, it has hardly been studied in
the context of structured peer-to-peer systems. These systems have
mainly been studied under churn (frequent joins/failures), which as a
side effect solves the problem of network partitions, as it is similar
to massive node failures. Yet, the crucial aspect of network mergers has
been ignored. In fact, it has been claimed that ring-based structured
overlay networks, which constitute the majority of the structured
overlays, are intrinsically ill-suited for merging rings.

In this thesis, we present a number of research papers representing our
work on handling network partitions and mergers in structured overlay
networks. The contribution of this thesis is threefold. First, we
provide a solution for merging ring-based structured overlays. Our
solution is tuneable, by a fanout parameter, to achieve a trade-off
between message and time complexity. Second, we provide a network size
estimation algorithm for ring-based structured overlays. We believe that
an estimate of the current network size can be used for tuning overlay
parameters that change according to the network size, for instance the
fanout parameter in our merger solution. Third, we extend our work from
fixing routing anomalies to achieving data consistency. We argue that
decreasing lookup inconsistencies on the routing level aids in achieving
data consistency in applications built on top of overlays. We study the
frequency of occurrence of lookup inconsistencies and discuss solutions
to decrease the affect of lookup inconsistencies.