Towards a topological characterization of asynchronous complexity
Towards a topological characterization of asynchronous complexity
复制标题
DOI：
10.1145/259380.259440
复制
发表时间：
1997-08
期刊：
影响因子：
--
通讯作者：
G. Hoest;N. Shavit
中科院分区：
文献类型：
--
作者：
G. Hoest;N. Shavit
本文介绍了以前用于分析可计算性的拓扑模型和方法，作为对异步复杂性进行量化和分类的工具。在Borowsky和Gafni的迭代立即快照(IIS)模型中，我们给出了第一个应用于决策任务的异步复杂性定理。为此，我们引入了一种新的拓扑工具，称为非均匀色细分。在Herlihy和Shavit的拓扑可计算性模型的框架下，我们的定理指出，任何异步算法的时间复杂度与允许从任务的输入复杂到其输出复杂的单纯映射所需的非均匀色细分的水平成正比。为了证明该定理的有效性，我们利用它导出了在IIS模型中达到n进程近似一致所需时间的一个新的紧界：Logdmax Input−Min Input�，其中d=3表示两个进程，d=2表示三个或更多进程。这填补了Aspnes和Herlihy的工作所暗示的已知上界和下界之间的一个有趣的差距。除了新的界本身，我们的异步复杂性定理的重要性在于，它允许我们推导的算法和下界是直观和简单的，具有根本不需要提到并发性的拓扑证明。
This paper introduces the use of topological models and methods, formerly used to analyze computability, as tools for the quantification and classification of asynchronous complexity. We present the first asynchronous complexity theorem, applied to decision tasks in the iterated immediate snapshot (IIS) model of Borowsky and Gafni. We do so by introducing a novel form of topological tool called the nonuniform chromatic subdivision. Building on the framework of Herlihy and Shavit's topological computability model, our theorem states that the time complexity of any asynchronous algorithm is directly proportional to the level of nonuniform chromatic subdivisions necessary to allow a simplicial map from a task's input complex to its output complex. To show the power of our theorem, we use it to derive a new tight bound on the time to achieve n process approximate agreement in the IIS model: logd max input−min input � , where d = 3 for two processes and d = 2 for three or more. This closes an intriguing gap between the known upper and lower bounds implied by the work of Aspnes and Herlihy. More than the new bounds themselves, the importance of our asynchronous complexity theorem is that the algorithms and lower bounds it allows us to derive are intuitive and simple, with topological proofs that require no mention of concurrency at all.