论文标题
通过组合拓扑中的基于圆形模型的K设定界限
K set-agreement bounds in round-based models through combinatorial topology
论文作者
论文摘要
基于圆形的模型是非常常见的消息通讯模型；应用于分布式计算的组合拓扑提供了诸如一般下限之类的全面结果。我们将两者结合起来研究K-SET一致性的可计算性。在所有可能的基于圆形模型的模型中，我们考虑忽略的模型，其中约束仅通过一组允许的图表给出每回合。在遗忘的模型中，我们专注于封闭的模型，那就是模型，其中一组可能的图包含所有边缘的图形，比某些启动图。这些捕获某些通信模型所需的基础结构，例如包含环。然后，我们在一轮中得出了下限和上限，以获得K-ster的一致性，以便使用组合拓扑证明了这些界限，但仅在图形属性方面进行了说明。当将我们的算法忽略时，这些界限扩展到了多个回合 - 仅回想成对的过程和初始价值，而不是谁发送什么以及何时发送。
Round-based models are very common message-passing models; combinatorial topology applied to distributed computing provides sweeping results like general lower bounds. We combine both to study the computability of k-set agreement. Among all the possible round-based models, we consider oblivious ones, where the constraints are given only round per round by a set of allowed graphs. And among oblivious models, we focus on closed-above ones, that is models where the set of possible graphs contains all graphs with more edges than some starting graphs. These capture intuitively the underlying structure required by some communication model, like containing a ring. We then derive lower bounds and upper bounds in one round for k-set agreement, such that these bounds are proved using combinatorial topology but stated only in terms of graph properties. These bounds extend to multiple rounds when limiting our algorithms to be oblivious -- recalling only pairs of processes and initial value, not who send what and when.
