Logical Obstruction to Set Agreement Tasks for Superset-Closed Adversaries
Logical Obstruction to Set Agreement Tasks for Superset-Closed Adversaries
复制标题
为超集封闭对手设定协议任务的逻辑障碍
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Nishimura
中科院分区：
文献类型：
--
作者：
Koki Yagi;S. Nishimura
在他们最近的论文（GandALF 2018）中，Goubault、Ledent和Rajsbaum为分布式计算提供了一个正式的认知模型。他们的逻辑模型，作为被充分研究的拓扑模型的替代方案，提供了一个有吸引力的框架，可以通过逻辑障碍来反驳给定分布式任务的可解性：人们只需要设计一个公式，用认知逻辑的形式语言，描述计算模型和任务模型之间的差异。然而，他们的论文中很少提出逻辑障碍的实例，特别是无等待2集协议任务的逻辑障碍是一个悬而未决的问题。不久之后，Nishida通过为无等待协议任务提供归纳定义的逻辑障碍公式，肯定地回答了这个问题。
In their recent paper (GandALF 2018), Goubault, Ledent, and Rajsbaum provided a formal epistemic model for distributed computing. Their logical model, as an alternative to the well-studied topological model, provides an attractive framework for refuting the solvability of a given distributed task by means of logical obstruction: One just needs to devise a formula, in the formal language of epistemic logic, that describes a discrepancy between the model of computation and that of the task. However, few instances of logical obstruction were presented in their paper and specifically logical obstruction to the wait-free 2-set agreement task was left as an open problem. Soon later, Nishida affirmatively answered to the problem by providing inductively defined logical obstruction formulas to the wait-free $k$-set agreement tasks.
The present paper refines Nishida's work and devises logical obstruction formulas to $k$-set agreement tasks for superset-closed adversaries, which supersede the wait-free model. These instances of logical obstruction formulas exemplify that the logical framework can provide yet another feasible method for showing impossibility of distributed tasks, though it is currently being confined to one-round distributed protocols. The logical method has an advantage over the topological method that it enjoys a self-contained, elementary induction proof. This is in contrast to topological methods, in which sophisticated topological tools, such as Nerve lemma, are often assumed as granted.
影响因子：
1.3
作者：
D. Kozlov
通讯作者：
D. Kozlov