论文标题
关于稳定网络的分布式构造在聚类平行时间中
On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time
论文作者
论文摘要
我们研究可以通过网络构造函数在Polygarithmic平行时间中创建的网络类别：在均匀的随机调度程序下随机交互的匿名代理组，能够彼此之间形成连接。从一个空网络开始，目标是构建一个属于给定家庭的稳定网络。我们证明，每个节点具有任何K> = 2个孩子的树类可以在O（log n）并行时间以很高的概率构建。 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多项式时间。我们使用它来提供一类Polyogarithmic时间网络构造函数的部分表征。
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.
