Building and Maintaining Structure in Distributed Networks
COM3 Level 2
SR21, COM3 02-60
Abstract:
Distributed networks have become a foundational infrastructure driven by the increasing demands of global storage and computation. However, novel computing paradigms and emerging technologies have introduced a variety of challenges, ranging from the need for rapid information dissemination in blockchains to the requirement for efficient routing protocols across the Internet. To mitigate these issues, distributed networks depend on the maintenance of a global “structure”. This thesis develops novel algorithms and techniques for the construction and maintenance of such structures for modern networks, with a primary focus on efficiency, Byzantine fault tolerance, and recovery.
The first contribution of this thesis revisits the classic problem of building efficient, routable structures in distributed networks with edge congestion. In this problem, each node must be able to send or receive a number of messages proportional to its degree, where the challenge is to route all the messages in parallel. While existing state-of-the-art solutions suffer from overhead factors subpolynomial in the network size, we account for the reality that only a subset of nodes—a “subnetwork”—may participate in a given computation. To that end, we design and analyze a novel branching random walk algorithm that achieves routing overhead factors subpolynomial in the subnetwork size, effectively localizing the complexity to the subnetwork.
Going beyond fixed networks, this thesis investigates the complex problem of maintaining structure in dynamic networks. Critical systems like blockchains rely on these dynamic networks for communication, yet they often lack a rigorous analysis of their peer-to-peer layers despite the rise in network-level attacks. We propose a novel design that leverages the blockchain itself to maintain a hypercubic overlay. This overlay is analyzed within a challenging model requiring robustness against both Byzantine faults and high churn. This section provides a tight analysis of tolerable churn rates and offers nontrivial recovery guarantees against “catastrophic failures,” including a wide range of connectivity issues, such as denial-of-service attacks.
Finally, this thesis explores the fundamental problem of self-stabilizing graph linearization, augmented with untrusted advice. In this problem, starting from any weakly connected network, nodes must converge to a “sorted path” network. We introduce a mechanism where nodes receive “advice”—small, potentially unreliable pieces of information intended to accelerate convergence. We demonstrate that if the provided advice is correct, the network achieves self-stabilization in optimal time; otherwise, it retains the self-stabilization time of the current state-of-the-art linearization algorithms. We conclude by presenting an asymptotically matching lower bound for convergence time in scenarios where advice can be corrupted.