Distributed Computation and Reconfiguration in Actively Dynamic Networks

Michail, Othon ORCID: 0000-0002-6234-3960, Skretas, Georgios ORCID: 0000-0003-2514-8004 and Spirakis, paul ORCID: 0000-0001-5396-3749 (2022) Distributed Computation and Reconfiguration in Actively Dynamic Networks. Distributed Computing, 35 (2). pp. 185-206.

This is the latest version of this item.

Access the full-text of this item by clicking on the Open Access link.

Text
MSS-DC21.pdf - Author Accepted Manuscript
Available under License : See the attached licence file.
Download (762kB) | Preview

Official URL: http://dx.doi.org/10.1007/s00446-021-00415-5

Abstract

We study here 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 to carry out a given task. Also, the distributed task itself may now require a global reconfiguration from a given initial network Gs to a target network Gf from a desirable family of networks. To formally capture costs associated with creating and maintaining connections, we define three 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 task of transforming any Gs into a Gf of diameter (poly)log(n), while minimizing the edge-complexity. Our main lower bound shows that Ω(n) total edge activations and Ω(n/logn) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of Θ(logn) rounds. We give three distributed algorithms for our general task. The first runs in O(logn) time, with at most 2n active edges per round, a total of O(nlogn) 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(logn) 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 o(log2n) running time.

Item Type:	Article
Uncontrolled Keywords:	Distributed algorithms, Dynamic networks, Reconfiguration, Transformation, Polylogarithmic time, Edge complexity
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	04 Apr 2022 15:50
Last Modified:	18 Jan 2023 21:05
DOI:	10.1007/s00446-021-00415-5
Open Access URL:	https://doi.org/10.1007/s00446-021-00415-5
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3152076