CONACyT: Topological Methods in Distributed and Concurrent Computation

CONACyT：分布式并发计算中的拓扑方法

• 批准号: 9613785
• 负责人: Maurice Herlihy
• 金额: $ 30万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-09-15 至 1999-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9613785&HistoricalAwards=false
• 关键词: CONACyT; Topological; Methods; Distributed; Concurrent

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.***

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