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 |
Externí odkaz: |