Dealing with network partitions in structured overlay networks |
| |
Authors: | Tallat M Shafaat Ali Ghodsi Seif Haridi |
| |
Affiliation: | (1) KTH - Royal Institute of Technology, Electrum 229, 164 40 Kista, Sweden;(2) Swedish Institute of Computer Science (SICS), Box 1263, 164 29 Kista, Sweden |
| |
Abstract: | 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 paper, we present an algorithm for merging multiple similar ring-based overlays when the underlying network merges.
We examine the solution in dynamic conditions, showing how our solution is resilient to churn during the merger, something
widely believed to be difficult or impossible. We evaluate the algorithm for various scenarios and show that even when falsely
detecting a merger, the algorithm quickly terminates and does not clutter the network with many messages. The algorithm is
flexible as the tradeoff between message complexity and time complexity can be adjusted by a parameter. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|