OBST: A self-adjusting peer-to-peer overlay based on multiple BSTs

The design of scalable and robust overlay topologies has been a main research subject since the very origins of peerto-peer (p2p) computing. Today, the corresponding optimization tradeoffs are fairly well-understood, at least in the static case and from a worst-case perspective. This paper revisits the peer-to-peer topology design problem from a self-organization perspective. We initiate the study of topologies which are optimized to serve the communication demand, or even self-adjusting as demand changes. The appeal of this new paradigm lies in the opportunity to be able to go beyond the lower bounds and limitations imposed by a static, communication-oblivious, topology. For example, the goal of having short routing paths (in terms of hop count) does no longer conflict with the requirement of having low peer degrees. We propose a simple overlay topology OBST(k) which is composed of k (rooted and directed) Binary Search Trees (BSTs), where k is a parameter. We first prove some fundamental bounds on what can and cannot be achieved optimizing a topology towards a static communication pattern (a static OBST(k)). In particular, we show that the number of BSTs that constitute the overlay can have a large impact on the routing costs, and that a single additional BST may reduce the amortized communication costs from Ω(log n) to O(1), where n is the number of peers. Subsequently, we discuss a natural self-adjusting extension of OBST(k), in which frequently communicating partners are “splayed together”.