Tree-structured Overlays with Minimal Height: Construction, Maintenance and Operation
Patrick Laskowski, Peter Detzner, Steffen Bondorf · 2023
Distributed systems, potentially growing large and consisting of heterogeneous nodes, are advised to be constructed following the Peer-to-Peer (P2P) networking paradigm. It becomes imperative that a Peer-to-Peer (P2P) network is paired with efficient protocols for each phase of its life cycle: construction as well as maintenance and operation. Three operations are fundamental for a Peer-to-Peer (P2P) network: nodes must be able to a) join, b) be located, c) leave. The main challenge for efficient protocols is that a single node will only possess limited information about the network, also known as the local view. In this paper, we present the minimal height tree overlay network (MINHTON), a Peer-to-Peer (P2P) overlay architecture featuring several beneficial structural properties added over existing tree-structured networks. The minimal height guarantees a global tree balance, yet, it must be retained at all times, even though the Peer-to-Peer (P2P) network may change dynamically. MINHTON provides efficient protocols for node Join and Departure, both retaining a minimal height tree. We show that the operations achieve performance in logarithmic order, comparable to tree overlays with less strict structural guarantees.