# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 1 Introduction  
Decentralized systems have generated interest worldwide among the computer networking community. Although they have existed for many years, they have become prevalent nowadays and are promoted as the future of Internet networking. They are widely used for sharing resources and storing extensive data sets, using small computers instead of large, costly servers. Typical examples include cloud computing environments, node-to-node (P2P) systems, and the Internet. According to [1], in a decentralized network, individual nodes act as both suppliers and consumers of resources, without the need for centralized coordination by servers, in contrast to the centralized client-server model, where client nodes request access to resources provided by central servers. In decentralized systems, data are stored at the network nodes, and the most crucial operations are data search and data updates. A decentralized network is represented by a graph, a logical _overlay network_, where its nodes correspond to the network nodes. In contrast, its edges may not correspond to existing communication links but to communication paths. We assume constant size messages between nodes through links and asynchronous communication. Furthermore, it is considered that the network provides an upper bound on the time needed for a node to send a message and receive an acknowledgement. In this way, the network provides a mechanism to identify communication problems, which may refer to communication links or nodes that are down. The complexity (cost) of an operation is measured by the number of messages issued during its execution (internal computations at nodes are considered insignificant). With respect to its _structure_, the overlay supports the operations _Join_ (of a new node \(v\), \(v\) communicates with an existing node \(u\) in order to be inserted into the overlay) and _Departure_ (of an existing node \(u\); \(u\) leaves the overlay announcing its intent to other nodes of the overlay). Moreover, the overlay implements an _indexing scheme_ for the stored data, supporting the operations _Insert_ (a new element), _Delete_ (an existing element), _Search_ (for an element), and _Range Query_ (for elements in a specific range). Range query processing in decentralized network environments is a complex problem to solve efficiently and scalably. In cloud infrastructures, a most significant and apparent requirement is the monitoring of thousands of computer nodes, which often requires support for range queries: consider range queries issued to identify under-utilized nodes to assign them more tasks, or to identify overloaded nodes to avoid bottlenecks in the cloud. For example, we wish to execute range queries such as:  
SELECT NodeID  
FROM CloudNodes  
WHERE Low < utilization < High  
or both single and range queries such as:  
SELECT NodeID  
FROM CloudNodes  
WHERE Low < utilization < High AND os = UNIX  
Moreover, in cloud infrastructures that support social network services like Facebook, stored user profiles are distributed in several nodes and we wish to retrieve user activity information, executing range queries such as:  
SELECT COUNT(userID)  
FROM CloudNodes  
WHERE 3/1/2015 < time < 3/31/2015 AND userID = 123456  
AND NodeID IN Facebook  
An acceptable solution for processing range queries in such large-scale decentralized environments must scale in terms of the number of nodes and the number of data items stored. For very large volume data (trillions of data items at millions of nodes), the classic logarithmic complexity offered by solutions in literature is still too expensive for single and range queries. Further, all available solutions incur large overheads concerning other critical operations, such as join/leave of nodes and insertion/deletion of items.