CONACyT: Topological Methods in Distributed and Concurrent Computation

NSF-CONACyT协作更新奖继续将简单代数拓扑（在CCR-9505949下开发）的抽象数学领域的技术应用于分布式或并行计算系统中协调并发进程的问题。从紧耦合多处理器中对共享数据对象的同步访问，到ATM网络中的数据路径分配，现代分布式和并发系统的所有规模都会出现协调问题。协调是困难的，因为现代并行和分布式系统本质上是异步的（也就是说，由于各种原因，包括中断、抢占、缓存丢失、通信延迟或故障，进程可能在没有警告的情况下延迟）。这些延迟可以在规模上有很大的不同：(a)缓存丢失可能会延迟处理器少于10条指令；(b)几百万条指令的页面错误；(c)操作系统对数亿条指令的抢占。不考虑这种延迟的协调协议存在这样的风险：如果一个处理器意外延迟，那么其余进程可能无法取得进展。随着系统规模的扩大，这些问题变得越来越严重。在过去的几年中，许多研究人员在经典代数拓扑的基础上开发了一系列新技术，用于分析分布式和并发协议和数据结构。在CCR-9505949支持的美墨合作努力下，这些技术已经成功地应用于一系列计算问题。这个更新合作项目将这些代数拓扑技术扩展到一系列更困难的问题，不仅适用于分布式和并行计算，而且适用于任何需要对不确定性和部分信息进行推理的问题领域

This NSF-CONACyT Collaborative Renewal Award continues to apply techniques from the abstract mathematical area of simplicial algebraic topology (developed under CCR-9505949) to the problem of coordinating concurrent processes in a distributed or parallel computing system. Coordination problems arise at all scales of modern distributed and concurrent systems, way from synchronizing access to shared data objects in tightly-coupled multiprocessors, to allocating data paths in ATM networks. Coordination is difficult because modern parallel and distributed systems are inherently asynchronous (that is, processes may be delayed without warning for a variety of reasons, including interrupts, pre-emption, cache misses, communication delays, or failures). These delays can vary enormously in scale: (a) a cache miss might delay a processor for fewer than ten instructions; (b) a page fault for a few million instructions; and (c) operating system pre-emption for hundreds of millions of instructions. Coordination protocols that do not take such delays into account run the risk that if one processor is unexpectedly delayed, then the remaining processes may be unable to make progress. Such problems become increasingly severe as systems scale. In the past few years, a number of researchers have developed a range of new techniques, based on classical algebraic topology, for analyzing distributed and concurrent protocols and data structures. These techniques have been applied successfully, under the US-Mexico collaborative effort supported by CCR-9505949, to a range of computational problems. This renewal collaborative project extends these algebraic topological techniques to a range of more difficult problems, not just for distributed and parallel computing, but for any problem area that requires reasoning about uncertainty and partial information.***