This paper shows, in the framework of the logical method,the unsolvability of $k$-set agreement task by devising a suitable formula of epistemic logic. The unsolvability of $k$-set agreement task is a well-known fact, which is a direct consequence of Sperner's lemma, a classic result from combinatorial topology. However, Sperner's lemma does not provide a good intuition for the unsolvability,hiding it behind the elegance of its combinatorial statement. The logical method has a merit that it can account for the reason of unsolvability by a concrete formula, but no epistemic formula for the general unsolvability result for $k$-set agreement task has been presented so far. We employ a variant of epistemic $\mu$-calculus, which extends the standard epistemic logic with distributed knowledge operators and propositional fixpoints, as the formal language of logic. With these extensions, we can provide an epistemic $\mu$-calculus formula that mentions higher-dimensional connectivity, which is essential in the original proof of Sperner's lemma, and thereby show that $k$-set agreement tasks are not solvable even by multi-round protocols. Furthermore, we also show that the same formula applies to establish the unsolvability for $k$-concurrency, a submodel of the 2-round protocol.


翻译:本文在逻辑方法的框架内显示, $k$- set 协议任务无法解析, 其方法是设计一个合适的缩写逻辑公式。 $k$- set 协议任务无法解解析, 是一个众所周知的事实, 这是Sperner lemma 的典型结果, 这是组合式表层学的经典结果 。 然而, Sperner 的 Lemma 没有为无法解析提供一种良好的直觉, 它隐藏在组合式语句的优雅背后。 这个逻辑方法有其优点, 它可以用一个具体公式来解释无法解析的原因, 但对于 $k$- set 协议任务的一般不可解析结果, 却没有提出如此远的缩写公式。 我们使用一个缩略式 $mum- calulus 的缩略图变量, 将标准的缩略图逻辑逻辑逻辑与分布式知识操作员和方略图固定点相扩展为同一语言。 通过这些扩展, 我们可以用一个缩写 $mall- $- colulual- 公式的缩略性公式来证明我们无法解 $- sal- fal- falal- commall

0
下载
关闭预览

相关内容

通过学习、实践或探索所获得的认识、判断或技能。
专知会员服务
123+阅读 · 2020年9月8日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Plenary Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年11月2日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年7月4日
Arxiv
0+阅读 · 2022年6月30日
Arxiv
0+阅读 · 2022年6月30日
Arxiv
15+阅读 · 2018年4月5日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Plenary Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年11月2日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员