Declarative Distirbuted Programming based on Combinatorial Topology

基于组合拓扑的声明式分布式编程

基本信息

批准号：
20K11678
负责人：
西村進
金额：
$ 2.83万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

近年、分散並列計算の組合せ幾何的モデルと、動的認識論理のKripkeモデルが相互に深く関連していることが明らかとなり、この2つの分野の交流による研究が盛んになってきている。組合せ幾何的モデルでは、分散計算問題の可解性を単体的複体モデルにおける高次元の連結性に帰着して議論するが、一定の条件の下で同様の議論を単体的複体モデルと同型なKripkeモデル上で認識論理を用いて行うことができる。特にGoubaultらは、障害論理式、すなわち分散並列システムに対応するKripkeモデルでは成り立つが実現したい分散並列計算に対応するKripkeモデルでは成り立たないような認識論理式をひとつ発見することによって、分散計算問題の不可解性を立証できることを示した。しかしながら、認識論理を用いる方法は基礎的な適用例が少し明らかになったばかりであり、計算モデルの精密化や適用範囲を拡張するための研究が進行しているところである。本年度は、前年度から継続の、並列分散システム中のプロセスが何度でも情報を交換できる複ラウンド計算モデルに対して認識論理の拡張である認識μ計算を用いてk集合合意問題の不可解性を示す研究を完成させ、2022年初夏にパリで開催された研究集会で発表した。その内容をまとめた論文を現在国際誌に投稿中である。さらに、分散同期メッセージ通信プロトコルによって分散合意問題が不可解であることを障害論理式を用いて示した。(大学院生2名との共同研究) この不可解性自体はすでに組合せ幾何的モデルで知られた結果であったが、認識論理の枠組みでは示されていなかった。本研究において、Goubaultらが示した分散同期メッセージ通信の単体的複体モデルに適合したKripkeモデルに対して、障害論理式を適用するのに必要な動的認識モデルの構成に必要な積更新モデルの構成方法を与えることによってこれを達成した。

近年来，已经揭示了分布式并联计算的几何几何模型和动态识别逻辑的Kripke模型相互关联，并且通过这两个领域之间的交流进行研究变得越来越流行。在组合几何模型中，基于单个复杂模型中连通性的较高维度讨论了分布式计算问题的可溶性，但是在某些条件下，可以使用在Kripke模型上使用识别逻辑进行类似的参数，而Kripke模型上的识别逻辑与单个复杂模型是同型的。特别是Goubault等。已经表明，可以通过发现错误的逻辑公式来证明分布式计算问题的遥不可及的性能，即在Kripke模型中有效的识别逻辑公式，该公式与分布式并行系统相对应，但在Kripke模型中不存在，但与他们想要实现的分布式平行计算相对应。但是，仅澄清了使用识别逻辑的方法的基本应用，目前正在进行研究以完善和扩大计算模型应用范围。今年，我们完成了一项研究，显示了使用识别μ计算（识别逻辑扩展的扩展）到一个多轮计算模型的差异性问题，该计算允许并行分布式系统中的流程一遍又一遍地交换信息，该信息已在上一年中持续了一年，并在2022年初在Paris举行的研究会议上进行了一项杂志。此外，由于使用故障逻辑的分布式同步消息协议，分布式共识问题是隐秘的。（与两名研究生的合作研究）这种莫名其妙的性能本身已经在组合几何模型中已经知道，但是在认知逻辑的框架中未显示。在这项研究中，这是通过提供一种构建产品更新模型的方法来实现的，以构建将故障逻辑方程应用于Kripke模型所需的动态识别模型，该模型适用于Goobault等人提供的分布式同步消息通信的单标准复杂模型。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

On the Power of Epistemic Logic for Defining Obstructions to Distributed Agreement Tasks

论认知逻辑在定义分布式协议任务障碍方面的力量

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Susumu Nishimura
通讯作者：
Susumu Nishimura

認識論理による分散タスク不可解性とその証明能力について

论分布式任务认知逻辑的不可理解性及其证明能力

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Okumura Keisuke;Defago Xavier;西村進
通讯作者：
西村進

Partial Product Updates for Agents of Detectable Failure and Logical Obstruction to Task Solvability

针对可检测故障和任务可解决性逻辑障碍的代理的部分产品更新

DOI：
发表时间：
2023
期刊：
arXiv.org
影响因子：
0
作者：
Daisuke Nakai;Masaki Muramatsu;Susumu Nishimura
通讯作者：
Susumu Nishimura

動的認識論理を用いた分散計算タスクの不可解性証明について

利用动态认知逻辑证明分布式计算任务的不可理解性

DOI：
发表时间：
2020
期刊：
影响因子：
0
作者：
Okumura Keisuke;Machida Manao;Defago Xavier;Tamura Yasumasa;S. Kitaev and A. Saito;西村進
通讯作者：
西村進

arXiv 論文(共著)

arXiv 论文（合着）

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

西村進其他文献

分散即時スナップショットの数え上げ組み合わせ論

计算分布式即时快照的组合

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
Yong Jiao;Eyuri Wakakuwa;Tomohiro Ogawa;Hiroshi Nagaoka;Hiroshi Nagaoka;Tomohiro Ogawa;Susumu Nishimura;西村進;西村進;西村進
通讯作者：
西村進

単体的複体の連続変形による分散タスクの実現可能性判定アルゴリズム

使用单纯复形的连续变形的分布式任务的可行性确定算法

DOI：
发表时间：
2017
期刊：
影响因子：
0
作者：
Yong Jiao;Eyuri Wakakuwa;Tomohiro Ogawa;Hiroshi Nagaoka;Hiroshi Nagaoka;Tomohiro Ogawa;Susumu Nishimura;西村進;西村進;西村進;西村進;西村進
通讯作者：
西村進

Schlegel図と分散プロトコル最適化

施莱格尔图和分布式协议优化

DOI：
发表时间：
2017
期刊：
影响因子：
0
作者：
Yong Jiao;Eyuri Wakakuwa;Tomohiro Ogawa;Hiroshi Nagaoka;Hiroshi Nagaoka;Tomohiro Ogawa;Susumu Nishimura;西村進;西村進;西村進;西村進
通讯作者：
西村進