Simple and efficient local codes for distributed stable network construction
Simple and efficient local codes for distributed stable network construction
复制标题
简单高效的本地代码，构建分布式稳定网络
DOI：
10.1007/s00446-015-0257-4
复制
发表时间：
2013
影响因子：
1.3
通讯作者：
P. Spirakis
中科院分区：
文献类型：
--
作者：
O. Michail;P. Spirakis
在这项工作中，我们研究协议，使人口的分布式进程可以构建网络。为了突出分布式网络构建的基本原则，我们在各个方面都保持了模型的最小化。特别是，我们假设有限状态的进程，所有开始从相同的初始状态和所有执行相同的协议。此外，我们假设由公平对手安排的进程之间的成对交互。为了允许进程构建网络，我们让它们激活和停用它们的成对连接。当两个进程交互时，协议将进程的状态和它们的连接状态作为输入，并更新它们。最初，所有连接都是不活动的，目标是在交互和激活/停用连接一段时间后，进程最终获得所需的稳定网络。我们给协议（在某些情况下是最佳的）和下界的几个基本的网络建设问题，如生成线，生成环，生成星星，和定期网络。我们的协议的预期收敛时间进行了分析下，一个统一的随机调度。最后，我们证明了几个通用性的结果，提出通用协议，能够模拟图灵机（TM），并利用它来构建一个大类的网络。我们还展示了如何将人口划分为k个超级节点，每个超级节点都是一行$$\log k$$logk节点，其中k是最大的。这个本地内存量足以让超级节点获得唯一的名称，并利用它们的名称和内存来实现非平凡的构造。
In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction, we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol. Moreover, we assume pairwise interactions between the processes that are scheduled by a fair adversary. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. The expected time to convergence of our protocols is analyzed under a uniform random scheduler. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. We additionally show how to partition the population into ksupernodes, each being a line of $$\log k$$logk nodes, for the largest such k. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions.