Connor, Matthew, Michail, Othon 
ORCID: 0000-0002-6234-3960 and Spirakis, Paul ORCID: 0000-0001-5396-3749
(2021)
On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time.
Information, 12 (6).
p. 254.
|
Text
CMS21-Information.pdf - Published version Download (504kB) | Preview |
Abstract
<jats:p>We study the class of networks, which can be created in polylogarithmic parallel time by network constructors: groups of anonymous agents that interact randomly under a uniform random scheduler with the ability to form connections between each other. Starting from an empty network, the goal is to construct a stable network that belongs to a given family. We prove that the class of trees where each node has any k≥2 children can be constructed in O(logn) parallel time with high probability. We show that constructing networks that are k-regular is Ω(n) time, but a minimal relaxation to (l,k)-regular networks, where l=k−1, can be constructed in polylogarithmic parallel time for any fixed k, where k>2. We further demonstrate that when the finite-state assumption is relaxed and k is allowed to grow with n, then k=loglogn acts as a threshold above which network construction is, again, polynomial time. We use this to provide a partial characterisation of the class of polylogarithmic time network constructors.</jats:p>
| Item Type: | Article |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 22 Jun 2021 14:28 |
| Last Modified: | 17 Mar 2024 12:13 |
| DOI: | 10.3390/info12060254 |
| Open Access URL: | https://www.mdpi.com/2078-2489/12/6/254/htm |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3127305 |
Dimensions
Dimensions
