ArithNet

Abstract

Distributed Hash Tables (DHTs) have been noted as a promising paradigm that provides an efficient lookup service for peer-to-peer applications. However, as many peer-to-peer applications are associated with a semantic and multi-attribute lookup service, existing DHTs have been modified to accommodate multi-attribute complex queries. Randomizing hash functions (e.g., SHA-1) that has been traditionally adopted by DHTs are now being replaced by the na$\"{i}$ve-order preserving mapping, and a multi-attribute scheme has been integrated into DHT-based systems. However, most existing approaches focus on reducing the load imbalance caused by such a mapping with an external load balancing scheme (e.g., virtual server-based schemes). We have noted that it is not sufficient enough for large scale peer-to-peer systems since the overhead of an external load balancing becomes larger and larger as the systems’ size and the skewness of data distribution increase. This thesis proposes ArithNet, a scalable protocol for supporting multi-attribute complex queries and inherent load balancing. ArithNet differs from previous complex query supporting systems in that it supports multi-attribute complex queries and inherent load balancing simultaneously. To guarantee efficient routing and inherent load balancing, ArithNet uses Arithmetic Mapping and the most selective attribute query resolution based on statistics obtained from studying training models. Our evaluation shows that ArithNet is able to achieve its goals of logarithmic-hop routing and near-uniform inherent load balancing in a very efficient and sophisticated way.