On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time

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 co...

Full description

Saved in:
Bibliographic Details
Published in:Information (Basel) 2021-06, Vol.12 (6), p.254
Main Authors: Connor, Matthew, Michail, Othon, Spirakis, Paul
Format: Article
Language:English
Subjects:
Algorithms
Communication
distributed network construction
Networks
partial characterisation
polylogarithmic time protocol
Polynomials
Population
population protocol
regular network
spanning tree
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2078-2489
2078-2489
DOI:10.3390/info12060254