A study on fault tolerant distributed algorithms for time-bounded Byzantine faults

限时拜占庭故障容错分布式算法研究

• 批准号: 23700019
• 负责人: YAMAUCHI Yukiko
• 金额: $ 2.75万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23700019/
• 关键词: 分散アルゴリズム; ビザンチン故障; 一時故障; 自己安定アルゴリズム; 分散システム; ビザンチン故障耐性; 自己安定; 合意問題; 故障耐性; 乱択アルゴリズム; 自己安定性; ランダム性

Large-scale distributed systems require distributed algorithms that guarantee tolerance against faults at processes. We aim to propose a new fault model in between the transient fault model and the permanent Byzantine fault model, and extend existing design schemes for fault tolerant distributed algorithms, such as self-stabilization. We focused on the mobile Byzantine fault model, and we obtained distributed algorithms for the mobile Byzantine agreement problem. Additionally, we obtained results about design of self-stabilizing algorithms, such as probabilistically stabilizing algorithms with bounded expected stabilization time, memory complexity of the leader election problem in the population protocol model.

大规模分布式系统需要分布式算法来保证对进程故障的容忍度。我们的目标是在暂态故障模型和永久拜占庭故障模型之间提出一种新的故障模型，并扩展现有的容错分布式算法设计方案，如自稳定。研究了移动拜占庭故障模型，得到了移动拜占庭协议问题的分布式算法。此外，我们还获得了自稳定算法的设计结果，如期望稳定时间有界的概率稳定算法、群体协议模型中领导者选举问题的内存复杂度等。

项目成果

A survey on pattern formation by mobile robots: asynchrony, obliviousness, and visibility

移动机器人模式形成调查：异步性、遗忘性和可见性

• 发表时间: 2013
• 作者: Kazuhiko Komatsu;Takashi Soga;Ryusuke Egawa;Hiroyuki Takizawa;and Hiroaki Kobayashi;Yukiko Yamauchi
• 通讯作者: Yukiko Yamauchi

一般のネットワーク上の移動ビザンチン合意問題について

关于通用网络上的移动拜占庭共识问题

• 发表时间: 2013
• 作者: Kazuhiko Komatsu;Ryusuke Egawa;Hiroyuki Takizawa;and Hiroaki Kobayashi;佐々木徹
• 通讯作者: 佐々木徹

Transitivity in distributed systems using exchange property of matroid bases

利用拟阵基交换性质的分布式系统中的传递性

• 发表时间: 2012
• 作者: Tomohiro I;Takaaki Nishimoto;Shunsuke Inenaga;Hideo Bannai and Masayuki Takeda;山内由紀子
• 通讯作者: 山内由紀子

Design and communication complexity of self-stabilizing protocols resilient to Byzantine faults

适应拜占庭故障的自稳定协议的设计和通信复杂性

• 发表时间: 2011
• 作者: Shinpei Hayashi;Sirinut Thangthumachit;Motoshi Saeki;Yukiko Yamauchi
• 通讯作者: Yukiko Yamauchi

Mobile Byzantine Agreement on Arbitrary Network

任意网络上的移动拜占庭协议

• 发表时间: 2013
• 作者: Toru Sasaki;Yukiko Yamauchi;Shuji Kijima;and Masafumi Yamashita
• 通讯作者: and Masafumi Yamashita