论文标题
网络中本地计算的拓扑
The Topology of Local Computing in Networks
论文作者
论文摘要
以某种方式对分布式计算进行建模是一种挑战，它是从不同角度开始处理的，其中两种技术在本世纪之交中出现了：协议复合体和定向代数拓扑。在这两种情况下，被考虑的计算模型通常都通过共享对象进行通信，通常是由读取寄存器集合组成的共享内存。我们的论文关注的是网络计算，其中流程位于网络节点，并通过沿该网络边缘交换消息来通信。在网络计算中应用拓扑方法进行验证是一个巨大的挑战，主要是因为分配给节点的标识符的存在会产生协议复合物，其大小随着基础网络的大小而成倍增长。但是，在这种情况下研究的许多问题都是局部性质，它们的定义不取决于标识符或网络的大小。我们利用这种独立性来满足上述挑战，并呈现$ \ textit {local} $协议复合体，其大小不取决于网络的大小。作为“紧凑型”协议复合物的设计的应用，我们在代数拓扑框架中重新制定了$ω（\ log^*n）$ roughs $ω（\ log^*n）$ rounds的$ω（\ log^*n）$ rounds。
Modeling distributed computing in a way enabling the use of formal methods is a challenge that has been approached from different angles, among which two techniques emerged at the turn of the century: protocol complexes, and directed algebraic topology. In both cases, the considered computational model generally assumes communication via shared objects, typically a shared memory consisting of a collection of read-write registers. Our paper is concerned with network computing, where the processes are located at the nodes of a network, and communicate by exchanging messages along the edges of that network. Applying the topological approach for verification in network computing is a considerable challenge, mainly because the presence of identifiers assigned to the nodes yields protocol complexes whose size grows exponentially with the size of the underlying network. However, many of the problems studied in this context are of local nature, and their definitions do not depend on the identifiers or on the size of the network. We leverage this independence in order to meet the above challenge, and present $\textit{local}$ protocol complexes, whose sizes do not depend on the size of the network. As an application of the design of "compact" protocol complexes, we reformulate the celebrated lower bound of $Ω(\log^*n)$ rounds for 3-coloring the $n$-node ring, in the algebraic topology framework.
