Skip to main content
Register
Springer Professional
SEARCH
Menu 1 2 3 4
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Peer-to-Peer Networking and Applications 1/2015

01-01-2015

Distributed deterministic 1–2 skip list for peer-to-peer system

Authors: Subhrangsu Mandal, Sandip Chakraborty, Sushanta Karmakar

Published in: Peer-to-Peer Networking and Applications | Issue 1/2015

Login to get access
share
SHARE

Abstract

Data management in the peer-to-peer system is a challenging task due to the random distribution of data among several participating peers. Efficient data structures like distributed hash tables (DHT) and its variants are designed and implemented to reduce the complexity of data management in such environment. However, DHT has its limitations in supporting range queries and its variants like distributed segment trees often perform poorly when the number of peers is high. Further, distributed lists and distributed balanced trees require significant amount of time for stabilizing after a new peer joins or a peer leaves. In this paper, a new distributed data structure called deterministic 1–2 skip list is introduced as an alternate solution for data management in the peer-to-peer systems. A deterministic skip list can be viewed as an alternate of a balanced tree, where the semantic locality of each key is preserved. Thus it can support the range queries as well as the single shot queries. This paper proposes three main operations on this data structure - searching data based on keys, insertion when a new peer joins, and deletion when a peer leaves. The correctness of the proposed operations are analyzed using theoretical arguments and mathematical proofs. The proposed scheme is simulated using NS-2.34 network simulator, and the efficiency of the scheme has been compared with DHT, DST, distributed list and distributed tree based data management.
previous article Towards an immunity based distributed algorithm to detect harmful files shared in P2P networks
next article A P2P tuple space implementation for disconnected MANETs

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe



 


Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko





Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

inform now
Literature
1.
Androutsellis-Theotokis S, Spinellis D (2004) A survey of peer-to-peer content distribution technologies. ACM Comput Surv 36:335–371 CrossRef
2.
3.
Bharambe AR, Agrawal M, Seshan S (2004) Mercury: supporting scalable multi-attribute range queries. In: ACM SIGCOMM computer communication review, vol 34. ACM, pp 353–366
4.
Bharambe AR, Agrawal M, Seshan S (2004) Mercury: supporting scalable multi-attribute range queries. SIGCOMM Comput Commun Rev 34(4):353–366 CrossRef
5.
Boldi P, Vigna S (2005) Compressed perfect embedded skip lists for quick inverted-index lookups. In: Proceedings SPIRE 2005. Lecture Notes in Computer Science, pp 25–28
6.
Cai M, Frank M (2004) RDFPeers: a scalable distributed RDF repository based on a structured peer-to-peer network. In: Proceedings of the 13th international conference on World Wide Web. ACM, pp 650–657
7.
Clement J, Herault T, Messika S, Peres O (2008) On the complexity of a self-stabilizing spanning tree algorithm for large scale systems. In: Proceedings of the 2008 14th IEEE pacific rim international symposium on dependable computing, pp 48–55
8.
Clouser T, Nesterenko M, Scheideler C (2008) Tiara: a self-stabilizing deterministic skip list. In: Proceedings of the 10th international symposium of stabilization, safety, and security of distributed systems, vol 5340, pp 124–140
9.
Crainiceanu A, Linga P, Gehrke J, Shanmugasundaram J (2004) Querying peer-to-peer networks using p-trees. In: Proceedings of the 7th international workshop on the web and databases: colocated with ACM SIGMOD/PODS 2004. ACM, pp 25–30
10.
Crainiceanu A, Linga P, Machanavajjhala A, Gehrke J, Shanmugasundaram J (2011) Load balancing and range queries in p2p systems using p-ring. ACM Trans Internet Technol 10(4):16:1–16:30 CrossRef
11.
Dabek F, Zhao B, Druschel P, Kubiatowicz J, Stoica I (2003) Towards a common API for structured peer-to-peer overlays. In: Proceedings of international workshop on peer-to-peer systems
12.
Dolev S, Kat RI (2004) Hypertree for self-stabilizing peer-to-peer systems. In: Proceedings of the network computing and applications. Third IEEE international symposium, pp 25–32
13.
El-Sana J, Azanli E, Varshney A (1999) Skip strips: maintaining triangle strips for view-dependent rendering. In: Proceedings of the conference on visualization ’99: celebrating ten years, pp 131–138
14.
Ganesan P, Yang B, Garcia-Molina H (2004) One torus to rule them all: multi-dimensional queries in P2P systems. In: Proceedings of the 7th international workshop on the web and databases. ACM, pp 19–24
15.
Ge T, Zdonik S (2008) A skip-list approach for efficiently processing forecasting queries. Proc VLDB Endow 1(1):984–995 CrossRef
16.
González-Beltrán A, Milligan P, Sage P (2008) Range queries over skip tree graphs. Comput Commun 31(2):358–374 CrossRef
17.
Goodrich MT, Tamassia R (2001) Efficient authenticated dictionaries with skip lists and commutative hashing. Tech. rep., Johns Hopkins Information Secutity Institute
18.
Gupta A, Agrawal D, Abbadi AE (2003) Approximate range selection queries in peer-to-peer systems. In: Proceedings of the first biennial conference on innovative data systems research CIDR, vol 2003
19.
Hanson EN, Johnson T (1992) The interval skip list: a data structure for finding all intervals that overlap a point. In: Proceedings of the 2nd workshop on algorithms and data structures, pp 153–164
20.
Harvey NJA, Jones MB, Saroiu S, Theimer M, Wolman A (2003) Skipnet: a scalable overlay network with practical locality properties. In: Proceedings of the 4th conference on USENIX symposium on internet technologies and systems
21.
Herlihy MP, Weihl WE (1991) Hybrid concurrency control for abstract data types. J Comput Syst Sci 43(1):25–61 CrossRefMATH
22.
Jagadish H, Ooi BC, Tan KL, Vu QH, Zhang R (2006) Speeding up search in peer-to-peer networks with a multi-way tree structure. In: Proceedings of the ACM SIGMOD international conference on management of data. ACM, pp 1–12
23.
Jagadish HV, Ooi BC, Vu QH (2005) BATON: a balanced tree structure for peer-to-peer networks. In: Proceedings of the 31st international conference on very large data bases, pp 661–672
24.
Jannotti J, Gifford DK, Johnson KL, Kaashoek MF, O’Toole JW Jr (2000) Overcast: reliable multicasting with on overlay network. In: Proceedings of the 4th conference on symposium on operating system design & implementation
25.
Lua EK, Crowcroft J, Pias M, Sharma R, Lim S (2005) A survey and comparison of peer-to-peer overlay network schemes. IEEE Commun Surv Tutor 7(2):72–93 CrossRef
26.
Mandal S, Chakraborty S, Karmakar S (2012) Deterministic 1–2 skip list in distributed system. In: Proceedings of the second IEEE international conference on parallel, distributed and grid computing
27.
Munro JI, Papadakis T, Sedgewick R (1992) Deterministic skip lists. In: Proceedings of the third annual ACM-SIAM symposium on discrete algorithms, pp 367–375
28.
Nor RM, Nesterenko M, Scheideler C (2011) Corona: a stabilizing deterministic message-passing skip list. In: Proceedings of the 13th international symposium of stabilization, safety, and security of distributed systems, pp 356–370
29.
30.
Onus M (2009) Overlay network construction in highly decentralized networks. Ph.D. thesis, Tempe
31.
32.
Ramabhadran S, Ratnasamy S, Hellerstein JM, Shenker S (2004) Prefix hash tree: an indexing data structure over distributed hash tables. In: Proceedings of the 23rd ACM symposium on principles of distributed computing
33.
Ratnasamy S, Francis P, Handley M, Karp R, Shenker S (2001) A scalable content-addressable network. In: Proceedings of the 2001 conference on applications, technologies, architectures, and protocols for computer communications, pp 161–172
34.
Rivest RL (1995) The RC5 encryption algorithm. In: Fast software encryption. Springer, pp 86–96
35.
Shu Y, Ooi BC, Tan KL, Zhou A (2005) Supporting multi-dimensional range queries in peer-to-peer systems. In: Proceedings of the fifth IEEE international conference on peer-to-peer computing. IEEE, pp 173–180
36.
Stoica I, Morris R, Karger D, Kaashoek MF, Balakrishnan H (2001) Chord: a scalable peer-to-peer lookup service for internet applications. In: Proceedings of the 2001 conference on applications, technologies, architectures, and protocols for computer communications, pp 149–160
37.
Tanin E, Harwood A, Samet H (2007) Using a distributed quadtree index in peer-to-peer networks. VLDB J 16(2):165–178 CrossRef
38.
Trunfio P, Talia D, Papadakis H, Fragopoulou P, Mordacchini M, Pennanen M, Popov K, Vlassov V, Haridi S (2007) Peer-to-peer resource discovery in grids: models and systems. Futur Gener Comput Syst 23(7):864–878 CrossRef
39.
Wang D, Liu J (2006) Peer-to-peer asynchronous video streaming using skip list. In: Proceedings of the IEEE international conference on multimedia and expo, pp 1397–1400
40.
Yu M, Li Z, Zhang L (2007) Supporting multi-attribute queries in peer-to-peer data management systems. In: Proceedings of the eighth international conference on parallel and distributed computing, applications and technologies, pp 515–522
41.
Zhang C, Krishnamurthy A, Wang RY (2005) Brushwood: distributed trees in peer-to-peer systems. In: Peer-to-Peer systems IV. Springer, pp 47–57
42.
Zhang K, Wang S (2005) Linknet: a new approach for searching in a large peer-to-peer system. In: Proceedings of the 7th asia-pacific web conference on web technologies research and development, pp 241–246
43.
Zheng C, Shen G, Li S, Shenker S (2006) Distributed segment tree: support range query and cover query over DHT. In: Proceedings of the fifth international workshop on peer-to-peer systems
Metadata
Title
Distributed deterministic 1–2 skip list for peer-to-peer system
Authors
Subhrangsu Mandal
Sandip Chakraborty
Sushanta Karmakar
Publication date
01-01-2015
Publisher
Springer US
Published in
Peer-to-Peer Networking and Applications / Issue 1/2015
Print ISSN: 1936-6442
Electronic ISSN: 1936-6450
DOI
https://doi.org/10.1007/s12083-013-0222-6

Other articles of this Issue 1/2015

Peer-to-Peer Networking and Applications 1/2015 Go to the issue

OriginalPaper

Towards an immunity based distributed algorithm to detect harmful files shared in P2P networks

OriginalPaper

A verifiable hierarchical circular shift cipher scheme for P2P chunk exchanges

OriginalPaper

A P2P tuple space implementation for disconnected MANETs

OriginalPaper

An efficient and distributed file search in unstructured peer-to-peer networks

OriginalPaper

Peer startup process and initial offset placement in peer-to-peer (P2P) live streaming systems

OriginalPaper

Improving lookup reliability in Kad

Premium Partner

Neuer Inhalt
    Image Credits