The week's pick
Random Articles
Reseach Article
Deterministic Cluster-based Skip List Protocol for Dynamic Distributed Systems
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 176 - Number 3 |
| Year of Publication: 2017 |
| Authors: Ahmed A. A. Gad-ElRab, T. A. A. Alzohairy, Khaled A. A. Khalf-Allah |
10.5120/ijca2017915552
|
Ahmed A. A. Gad-ElRab, T. A. A. Alzohairy, Khaled A. A. Khalf-Allah . Deterministic Cluster-based Skip List Protocol for Dynamic Distributed Systems. International Journal of Computer Applications. 176, 3 ( Oct 2017), 1-11. DOI=10.5120/ijca2017915552
Abstract
Dynamic distributed system (DDS) is a continually running system with a large number of entities as processes or nodes that are connected with each other and each of them has only a partial view of the system as Peer-to-peer (P2P) system which can be decentralized, centralized or hybrid of both to make the system operations faster as possible. In P2P, any number of entities can join and leave the system at any moment which makes the topology of the system continuously changed. So, the system must deal with these changes to be stable as possible. So, data management algorithms are needed to build an overlay network which is a logical layer that used to store the information about these entities. Skip list structure is the most common and efcient overlay structure for data management in P2P systems. However, using this structure cannot minimize the time delay for query processes as searching, inserting, and deleting in case of there is a huge number of entities in the skip list. In addition, most of existing algorithms that use this structure have been developed based on a special structure of skip list and they did not be applicable for another structure of the skip list. In this paper, to overcome these drawbacks, a new skip List structure and query processing methods are proposed. The conducted simulation results show that the proposed structure and algorithm are much better than the existing algorithms in the time delay and the required number of steps to nish any query process.
References
- Stephanos Androutsellis-Theotokis and Diomidis Spinellis. A survey of peer-to-peer content distribution technologies. ACM Comput. Surv., 36(4):335–371, December 2004.
- Roberto ”Baldoni, Marin Bertier, Michel Raynal, and Sara” Tucci-Piergiovanni. ”looking for a definition of dynamic distributed systems”. ”Springer Berlin Heidelberg”, pages ”1– 14”, ”2007”.
- Paolo Boldi and Sebastiano Vigna. Compressed perfect embedded skip lists for quick inverted-index lookups. Springer, pages 25–28, 2005.
- Thomas Clouser, Mikhail Nesterenko, and Christian Scheideler. Tiara: A self-stabilizing deterministic skip list. Springer, pages 124–140, 2008.
- Yi Cui, Baochun Li, and K. Nahrstedt. ostream: asynchronous streaming multicast in application-layer overlay networks. IEEE Journal on Selected Areas in Communications, 22(1):91–106, Jan 2004.
- Tingjian Ge and Stan Zdonik. A skip-list approach for efficiently processing forecasting queries. Proc. VLDB Endow., 1(1):984–995, August 2008.
- Michael T Goodrich and Roberto Tamassia. Efficient authenticated dictionaries with skip lists and commutative hashing. Google Patents, 2000. US Patent 7,257,711.
- Eric N. Hanson and Theodore Johnson. The interval skip list: A data structure for finding all intervals that overlap a point. Springer, pages 153–164, 1992.
- Nicholas J.A. Harvey, John Dunagan, Mike Jones, Stefan Saroiu, Marvin Theimer, and Alec Wolman. Skipnet: A scalable overlay network with practical locality properties. microsoft, page 38, December 2002.
- Y. J. Lee, S. M. Yoon, J. H. Ji, H. G. Cho, and G. Woo. How to apply the skip list to the management of a massive set of replying comments in web bulletins by exploiting the powerlaw distribution. 2010 10th IEEE International Conference on Computer and Information Technology, pages 674–681, June 2010.
- Subhrangsu Mandal, Sandip Chakraborty, and Sushanta Karmakar. Deterministic 1–2 skip list in distributed system. IEEE, pages 296–301, 2012.
- Subhrangsu Mandal, Sandip Chakraborty, and Sushanta Karmakar. Distributed deterministic 1–2 skip list for peer-to-peer system. Peer-to-Peer Networking and Applications, 8(1):63– 86, 2015.
- J. Ian Munro, Thomas Papadakis, and Robert Sedgewick. Deterministic skip lists. Society for Industrial and Applied Mathematics, pages 367–375, 1992.
- Rizal Mohd Nor, Mikhail Nesterenko, and Christian Scheideler. Corona: A stabilizing deterministic message-passing skip list. Theoretical Computer Science, 512:119 – 129, 2013.
- William Pugh. Skip lists: A probabilistic alternative to balanced trees. Commun. ACM, 33(6):668–676, June 1990.
- D.Wang and J. Liu. Peer-to-peer asynchronous video streaming using skip list. 2006 IEEE International Conference on Multimedia and Expo, pages 1397–1400, July 2006.
- Changxi Zheng, Guobin Shen, Shipeng Li, and Scott Shenker. Distributed segment tree: Support of range query and cover query over dht. The 5th International Workshop on Peer-to- Peer Systems, 2006.
Index Terms
Keywords