2020/07/01 by Matthew Connor, Matthew P. Connor, Othon Michail +5
Computer Science · Mathematics · #Cellular Automata and Applications #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Stochastic processes and statistical mechanics #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.2007.00625
19 Pages 7 Figures
arxiv created 2020/07/01 · openalex publication_date 2020/07/01 · arxiv updated 2020/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.