We study graph realization problems from a distributed perspective. The problem is naturally applicable to the distributed construction of overlay networks that must satisfy certain degree or connectivity properties, and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks.We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization. In the degree sequence problem, each node v is associated with a degree d(v), and the resulting degree sequence is realizable if it is possible to construct an overlay network in which the degree of each node v is d(v). The minimum threshold-connectivity problem requires us to construct an overlay network that satisfies connectivity constraints specified between every pair of nodes.Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge.The main realization algorithms we present are the following. (1) A $\tilde O(\min \{ \sqrt m ,\Delta \} )$ time algorithm for implicit realization of a degree sequence. Here, Δ = maxvd(v) is the maximum degree and m = (1/2) v d(v) is the number of edges in the final realization. (2) A $\tilde O\left( \Delta \right)$ time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde O\left( \Delta \right)$ additional rounds. (3) A $\tilde O\left( \Delta \right)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde O\left( 1 \right)$ algorithm for implicit realization when all nodes know each other’s IDs. These algorithms are 2-approximations w.r.t. the number of edges. Our algorithms are complemented by lower bounds showing tightness up to log n factors. Additionally, we provide algorithms for realizing trees and an $\tilde O\left( 1 \right)$ round algorithm for approximate degree sequence realization.

A Peer-to-Peer (P2P) network is a dynamic collection of nodes that connect with each other via virtual overlay links built upon an underlying network (usually, the Internet). Typical P2P networks are highly dynamic and can experience very heavy churn, i.e., a large number of nodes join/leave the network every time step. We present an overlay framework called Sparse Robust Addressable Network (Spartan) that can tolerate heavy adversarial churn. We show that Spartan can be built efficiently in a fully distributed manner within O(log n) rounds. Furthermore, the Spartan overlay structure can be maintained, again, in a fully distributed manner despite adversarially controlled churn (i.e., nodes joining and leaving) and significant variation in the number of nodes. When the number of nodes in the network lies in [n, fn] for any fixed f ≥ 1 the adversary can remove up to ϵn nodes and add up to ϵn nodes (for some small but fixed ϵ > 0) within any period of P rounds for some P ∈ O(log log n). Moreover, the adversary can add or remove nodes from the network at will and without any forewarning. Despite such uncertainty in the network, Spartan maintains Θ(n/ log n) committees that are stable and addressable collections of Θ(log n) nodes each. Any node that enters the network will be able to gain membership in one of these committees within O(1) rounds. The committees are also capable of performing sustained computation and passing messages between each other. Thus, any protocol designed for static networks can be simulated on Spartan with minimal overhead. This makes Spartan an ideal platform for developing applications. All our results hold with high probability.

We investigate the problem of electing a leader in a sparse but well-connected synchronous dynamic network in which up to a fraction of the nodes chosen adversarially can leave/join the network per time step. At this churn rate, all nodes in the network can be replaced by new nodes in a constant number of rounds. Moreover, the adversary can shield a fraction of the nodes (which may include the leader) by repeatedly churning their neighbourhood and thus hinder their communication with the rest of the network. However, empirical studies in peer-to-peer networks have shown that a significant fraction of the nodes are usually stable and well connected. It is, therefore, natural to take advantage of such stability and well-connectedness to establish a leader that can maintain good communication with rest of the nodes. Since the dynamics could change eventually, it is also essential to re-elect a new leader whenever the current leader has either left the network or is not well-connected with rest of the nodes. In such re-elections, care must be taken to avoid premature and spurious leader election resulting in more than one leader present in the network at the same time. We assume a broadcast based communication model in which each node can send up to O(log3n) bits per round and is unaware of its receivers a priori. We present a randomized algorithm that can, in O(log n) rounds, detect and reach consensus about the health of the leader (i.e., whether it is able to maintain good communication with rest of the network). In the event that the network decides that the leader's ability to communicate is unhealthy, a new leader is re-elected in a further O(log2n) rounds. Our running times hold with high probability, and, furthermore, we are guaranteed with high probability that there is at most one leader at any time.