Distributed Graph Realizations

doi:10.1109/TPDS.2021.3104239

Distributed Graph Realizations

2022-06-01

1

OA

AI

Sivasubramaniam, Sumathi

S

Suman Sourav

DOI：10.1109/TPDS.2021.3104239

Original

Original request for help

Save

Abstract

En 中文

We study graph realization problems for the first time from a distributed perspective. Graph realization problems are encountered in distributed construction of overlay networks that must satisfy certain degree or connectivity properties. We study them in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer overlay 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. (Note that all our algorithms are randomized Las Vegas algorithms unless specified otherwise. The stated running times hold with high probability.) 1) An (O) over bar (min {root m., Delta) time algorithm for implicit realization of a degree sequence. Here, Delta = max(v)d(v) is the maximum degree and m - (1/2) Sigma(v)d(v) is the number of edges in the final realization. 2) (O) over bar(Delta) 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 (O) over bar(Delta) additional rounds. 3) An (O) over bar(Delta) time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved (O) over bar (1) algorithm for implicit realization when all nodes know each other's IDs. These algorithms yield 2-approximations w.r.t. the number of edges. We complement our upper bounds with lower bounds to show that the above algorithms are tight up to factors of log o. Additionally, we provide algorithms for realizing trees (including a procedure for obtaining a tree with a minimal diameter), an (O) over bar (1) round algorithm for approximate degree sequence realization and finally an O(log(2)n) algorithm for degree sequence realization in the non-preassigned case namely, where the input degree sequence may be permuted among the nodes.

Keywords:

Peer-to-peer overlay networks

node capacitated clique model

graph realization

degree realization

connectivity realization

Distributed Graph Realizations

Abstract

Journal

Organization