ELATS: Energy and locality aware aggregation tree for skip graph

Abstract

As a distributed hash table (DHT), Skip Graph acts as the underlying routing infrastructure of peer-to-peer (P2P) storage systems, distributed online social networks, search engines, and other DHT-based applications. For many P2P applications, data aggregation is vital, however, it is a missing feature of Skip Graph. The traditional aggregation algorithms cost noticeable message overhead which degrades the energy efficiency while increasing the response time. Likewise, the aggregation trees proposed for other DHTs are either inapplicable to the Skip Graph or apply some sort of randomness in their construction. Randomized features of an aggregation tree result in higher aggregation latency as well as enforcing unbalanced load on nodes which negatively affect the energy efficiency. In this paper, we propose ELATS which is the first energy and locality aware aggregation tree for Skip Graph. We define the energy awareness as minimizing the average energy cost of an aggregation tree, and the locality awareness as minimizing the latency on the path between the root and leaves of the aggregation tree. Performance analysis results show that ELATS algorithm provides both energy and locality awareness, and improves the aggregation latency with the gain of about 8% in comparison to the best existing solutions for DHTs which are either locality aware or energy aware.