On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time

Autor: Paul G. Spirakis, Othon Michail, Matthew Connor
Jazyk: angličtina
Rok vydání: 2021
Předmět:
FOS: Computer and information sciences
Class (set theory)
Computer science
MathematicsofComputing_GENERAL
polylogarithmic time protocol
0102 computer and information sciences
02 engineering and technology
Information technology
Population protocol
partial characterisation
01 natural sciences
0202 electrical engineering
electronic engineering
information engineering

distributed network construction
regular network
Time complexity
High probability
Discrete mathematics
spanning tree
Spanning tree
Node (networking)
020206 networking & telecommunications
Construct (python library)
T58.5-58.64
population protocol
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computer Science - Distributed
Parallel
and Cluster Computing

010201 computation theory & mathematics
Relaxation (approximation)
Distributed
Parallel
and Cluster Computing (cs.DC)

Information Systems
Zdroj: Information
Information, Vol 12, Iss 254, p 254 (2021)
Volume 12
Issue 6
Popis: 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 which 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(log n) parallel time with high probability. We show that constructing networks which are k-regular is Omega(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 = log log n 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.
19 Pages 7 Figures
Databáze: OpenAIRE