Merging ring-structured overlay indices : toward network-data transparency
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/97384 http://hdl.handle.net/10220/13152 |
| _version_ | 1811677762280226816 |
|---|---|
| author | Datta, Anwitaman |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Datta, Anwitaman |
| author_sort | Datta, Anwitaman |
| collection | NTU |
| description | 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 (Datta and Aberer in international workshop on self-organizing systems, 2006), and identified that tree structured overlays are relatively easier to merge in a transparent manner (Datta in IEEE international conference on self-adaptive and self-organizing systems, 2007). 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. |
| first_indexed | 2024-10-01T02:42:31Z |
| format | Journal Article |
| id | ntu-10356/97384 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:42:31Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/973842020-05-28T07:18:09Z Merging ring-structured overlay indices : toward network-data transparency Datta, Anwitaman School of Computer Engineering DRNTU::Engineering::Computer science and engineering 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 (Datta and Aberer in international workshop on self-organizing systems, 2006), and identified that tree structured overlays are relatively easier to merge in a transparent manner (Datta in IEEE international conference on self-adaptive and self-organizing systems, 2007). 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. 2013-08-16T03:53:23Z 2019-12-06T19:42:05Z 2013-08-16T03:53:23Z 2019-12-06T19:42:05Z 2012 2012 Journal Article Datta, A. (2012). Merging ring-structured overlay indices: toward network-data transparency. Computing, 94(8-10), 783-809. https://hdl.handle.net/10356/97384 http://hdl.handle.net/10220/13152 10.1007/s00607-012-0201-4 en Computing |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Datta, Anwitaman Merging ring-structured overlay indices : toward network-data transparency |
| title | Merging ring-structured overlay indices : toward network-data transparency |
| title_full | Merging ring-structured overlay indices : toward network-data transparency |
| title_fullStr | Merging ring-structured overlay indices : toward network-data transparency |
| title_full_unstemmed | Merging ring-structured overlay indices : toward network-data transparency |
| title_short | Merging ring-structured overlay indices : toward network-data transparency |
| title_sort | merging ring structured overlay indices toward network data transparency |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/97384 http://hdl.handle.net/10220/13152 |
| work_keys_str_mv | AT dattaanwitaman mergingringstructuredoverlayindicestowardnetworkdatatransparency |