Distributed Computation and Reconfiguration in Actively Dynamic Networks

Michail, Othon ORCID: 0000-0002-6234-3960, Skretas, george ORCID: 0000-0003-2514-8004 and Spirakis, paul
(2020) Distributed Computation and Reconfiguration in Actively Dynamic Networks. In: 39th ACM Symposium on Principles of Distributed Computing (PODC), 2020-08-03 - 2020-08-07.

This is the latest version of this item.

[img] Text
MSS-podc20.pdf - Submitted Version

Download (673kB) | Preview
[img] Text
MSS-podc20-final.pdf - Accepted Version

Download (613kB) | Preview


In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network Gs to a target network Gf from a family of networks having some good properties, like small diameter. To formally capture costs associated with creating and maintaining connections, we define three reasonable edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. We give (poly)log(n) time algorithms for the general task of transforming any Gs into a Gf of diameter (poly)log(n), while minimizing the edge-complexity. There is a natural trade-off between time and edge complexity. Our main lower bound shows that Ω(n) total edge activations and Ω(n/log n) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of Θ(log n) rounds. On the positive side, we give three distributed algorithms for our general task. The first runs in O(log n) time, with at most 2n active edges per round, a total of O(n log n) edge activations, a maximum degree n − 1, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter O(log n) and uses O(n) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n) then we can achieve a running time of o(log2n). This novel model of distributed computation and reconfiguration in actively dynamic networks and the proposed measures of the edge complexity of distributed algorithms, may open new avenues for research in the algorithmic theory of dynamic networks.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 09 Jul 2020 08:50
Last Modified: 06 Jan 2022 13:39
DOI: 10.1145/3382734.3405744
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3090448

Available Versions of this Item