×

Merging ring-structured overlay indices: toward network-data transparency. (English) Zbl 1250.68076

Summary: Peer-to-peer index structures distributed and managed over the planet, commonly known as structured overlays (e.g., distributed hash tables) have been touted to play the role of a fundamental building block for internet-scale distributed systems. Traditional designs consider incremental or possibly even parallelized construction of a single overlay, which implicitly assumes global control and coordination to enforce the construction of an unique overlay. However, if merger of originally isolated overlays is made possible, then one can realize decentralized bootstrapping of overlays. So to say, smaller overlays can be constructed using any of the traditional mechanisms, which can then organically coalesce to form a larger overlay. Such self-organizational attributes of decentralized bootstrapping and organic growth are of paramount importance for large scale systems. In our previous works, we explained the challenges of merging important families of (tree and ring) structured overlays, and identified that tree structured overlays are relatively easier to merge in a transparent manner. In this paper we investigate how ring structured overlays can be merged, both in terms of the necessary algorithms, as well as how it performs during the merger process, taking into account not only the ‘network’ merger process, but also looking into how and whether this process is ‘transparent’ for applications/end-users accessing and using the overlay as an index. We introduce interesting new metrics to evaluate the merger process and carry out asymptotic analysis for estimating the same, besides conducting simulation experiments to validate the theory as well as measure other aspects of the overlays’ performance under merger.

MSC:

68M14 Distributed systems
68P05 Data structures

Software:

Dynamo; Cassandra; Chord
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aberer K, Datta A, Hauswirth M, Schmidt R (2005) Indexing data-oriented overlay networks. In: International conference on very large databases (VLDB)
[2] Bhagwan R, Tati K, Cheng Y, Savage S, Voelker, GM (2004) TotalRecall: system support for automated availability management. The ACM/USENIX symposium on networked systems design and implementation
[3] Bharambe A, Agrawal M, Seshan S (2004) Mercury: supporting scalable multi-attribute range queries. In: ACM special interest group on data communication (SIGCOMM)
[4] Caesar M, Condie T, Kannan J, Lakshminarayanan K, Stoica I, Shenker S (2006): ROFL: routing on flat labels. In: ACM special interest group on data communication (SIGCOMM)
[5] Chaudhuri S, Narasayya V (1999) Index merging. In: International conference on data engineering (ICDE)
[6] Dabek F, Kaashoek MF, Karger D, Morris R, Stoica I (2001) Wide-area cooperative storage with CFS. In: ACM symposium on operating systems principles (SOSP)
[7] Datta A (2007) Merging intra-planetary index structures: decentralized bootstrapping of overlays. In: IEEE international conference on self-adaptive and self-organizing systems (SASO)
[8] Datta A, Aberer K (2006) The challenges of merging two similar structured overlays: a tale of two networks. In: International workshop on self-organizing systems (IWSOS)
[9] DeCandia G, Hastorun D, Jampani M, Kakulapati G, Lakshman A, Pilchin A, Sivasubramanian S, Vosshall P, Vogels W (2007) Dynamo: Amazon’s highly available key–value store. SIGOPS Oper Syst Rev 41(6): 205–220 · doi:10.1145/1323293.1294281
[10] Falkner J, Piatek M, John JP, Krishnamurthy A, Anderson T (2007) Profiling a million user DHT. In: Australasian conference on Computer science (IMC)
[11] Ganesan P, Bawa M, Garcia-Molina H (2004) Online balancing of range-partitioned data with applications to peer-to-peer systems. In: International conference on very large databases (VLDB)
[12] Ganesan P, Gummadi P, Garcia-Molina H (2004) Canon in G Major: Designing DHTs with hierarchical structure. In: International conference on distributed computing systems (ICDCS)
[13] Girdzijauskas S, Datta A, Aberer K (2010) Structured overlay for heterogeneous environments: design and evaluation of Oscar. ACM Trans Auton Adapt Syst 5(1): 2:1–2:25 · Zbl 05737048 · doi:10.1145/1671948.1671950
[14] Gummadi K, Gummadi R, Ratnasamy S, Shenker S, Stoica I (2003) The impact of DHT routing geometry on resilience and proximity. In: ACM special interest group on data communication (SIGCOMM)
[15] Harvey N, Jones M, Saroiu S, Theimer M, Wolman A (2003) Skipnet: a scalable overlay network with practical locality properties. In: USENIX symposium on internet technologies and systems (USITS)
[16] Hellerstein JM (2003) Toward network data independence. SIGMOD Rec 32(3): 34–40 · Zbl 05444211 · doi:10.1145/945721.945730
[17] Jelasity M, Montresor A, Babaoglu O (2006) The bootstrapping service. In: IEEE international conference on distributed computing systems workshops (ICDCSW)
[18] Joseph D, Kannan J, Kubota A, Lakshminarayanan K, Stoica I, Wehrle K (2006) OCALA: an architecture for supporting legacy applications over overlays. In: USENIX/ACM symposium on networked systems design and implementation (NSDI)
[19] Kis Z, Szabo R (2008) Chord-zip: A chord-ring merger algorithm. In: IEEE communications letters
[20] Kis Z, Szabo R (2010) Scalable merger of chord-rings. Int J Commun Netw Distrib Syst 4(4): 376–388 · doi:10.1504/IJCNDS.2010.033160
[21] Kleinberg J (2000) he small-world phenomenon: An algorithmic perspective. In: ACM symposium on theory of computing · Zbl 1296.05181
[22] Lakshman A, Malik P (2009) Cassandra–a decentralized structured storage system. In: The 3rd ACM SIGOPS international workshop on large scale distributed systems and middleware (LADIS)
[23] Lester N, Zobel J, Williams H (2004) In-place versus re-build versus re-merge: index maintenance strategies for text retrieval systems. In: Australasian conference on Computer science (ACSC)
[24] Li J, Stribling J, Morris R, Kaashoek M (2005) Bandwidth-efficient management of DHT routing tables. In: USENIX/ACM symposium on networked systems design and implementation (NSDI)
[25] Liben-Nowell D, Balakrishnan H, Karger D (2002) Analysis of the evolution of peer-to-peer systems · Zbl 1292.68014
[26] Manku G, Bawa M, Raghavan P (2003) Symphony: Distributed Hashing in a Small World. In: USENIX symposium on internet technologies and systems (USITS)
[27] Montresor A, Jelasity M, Babaoglu O (2005) Chord on Demand. In: IEEE International conference on peer-to-peer computing (P2P)
[28] Rhea S, Godfrey B, Karp B, Kubiatowicz J, Ratnasamy S, Shenker S, Stoica I, Yu H (2005) OpenDHT: A Public DHT Service and Its Uses. In: ACM special interest group on data communication (SIGCOMM)
[29] Rowstron A, Druschel P (2001) Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: IFIP/ACM international conference on distributed systems platforms (middleware) · Zbl 1051.68788
[30] Shafaat T, Ghodsi A, Haridi S (2007) Handling network partitions and mergers in structured overlay networks. In: IEEE international conference on peer-to-peer computing (P2P)
[31] Shafaat TM, Ghodsi A, Haridi S (2009) Dealing with network partitions in structured overlay networks. Peer-to-Peer Netw Appl 2(4): 334–347 · doi:10.1007/s12083-009-0037-7
[32] Stoica I, Morris R, Karger D, Kaashoek F, Balakrishnan H (2001) Chord: A scalable peer-to-peer lookup service for internet applications. In: ACM special interest group on data communication (SIGCOMM) (technical report version, http://pdos.csail.mit.edu/chord/papers/ )
[33] Stutzbach D, Rejaie R (2006) Understanding churn in peer-to-peer networks. In: Proceedings of the 6th ACM SIGCOMM conference on internet measurement, IMC
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.