论文标题
分布式计算的弱异步模型的分类
A Classification of Weak Asynchronous Models of Distributed Computing
论文作者
论文摘要
我们对由相同的有限状态设备组成的分布式计算的异步模型进行了系统研究，该模型在网络中合作，以决定网络是否满足给定的图理论属性。文献中讨论的模型在网络节点上所居住的代理的检测能力（检测邻居的一组或计算每个状态中邻居的数量），接受的概念（通过在特定的配置中停止或通过稳定的状态），或仲裁的阶级，同步，统一移动的诺言， （非静止或类似随机的）。我们研究这些特征组合的表达能力，并表明最初二十种可能的组合符合七个等效类别。分类是几种静电性结果的结果，并具有明确的解释。特别是，我们表明，如果将配置与计数结合在一起，则仅停止配置的接受仅具有非平凡的表达能力，并且同步和交织模型具有与任意节点可以同时移动的功率相同的功率。我们还确定了区分七个类的表达能力的简单图形属性。
We conduct a systematic study of asynchronous models of distributed computing consisting of identical finite-state devices that cooperate in a network to decide if the network satisfies a given graph-theoretical property. Models discussed in the literature differ in the detection capabilities of the agents residing at the nodes of the network (detecting the set of states of their neighbors, or counting the number of neighbors in each state), the notion of acceptance (acceptance by halting in a particular configuration, or by stable consensus), the notion of step (synchronous move, interleaving, or arbitrary timing), and the fairness assumptions (non-starving, or stochastic-like). We study the expressive power of the combinations of these features, and show that the initially twenty possible combinations fit into seven equivalence classes. The classification is the consequence of several equi-expressivity results with a clear interpretation. In particular, we show that acceptance by halting configuration only has non-trivial expressive power if it is combined with counting, and that synchronous and interleaving models have the same power as those in which an arbitrary set of nodes can move at the same time. We also identify simple graph properties that distinguish the expressive power of the seven classes.
