CONACyT: Topological Methods in Distributed and Concurrent Computation

这个NSF-CONACyT协作更新奖继续将单纯代数拓扑抽象数学领域的技术(根据CCR-9505949开发)应用到分布式或并行计算系统中协调并发进程的问题上。协调问题出现在现代分布式和并发系统的所有规模上，从在紧耦合的多处理器中同步对共享数据对象的访问，到在ATM网络中分配数据路径。协调是困难的，因为现代并行和分布式系统本质上是异步的(即，进程可能由于各种原因而在没有警告的情况下延迟，包括中断、抢占、缓存未命中、通信延迟或故障)。这些延迟在规模上可能有很大的不同：(A)高速缓存未命中可能会使处理器延迟不到十条指令；(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.***