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.

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

项目成果

Asynchronous pattern formation by anonymous oblivious mobile robots

匿名无意识移动机器人的异步模式形成

• 发表时间: 2012
• 作者: Nao Fujinaga

Asynchronous pattern formation by anonymous oblivious mobile robots

匿名无意识移动机器人的异步模式形成

• 发表时间: 2012
• 作者: Nao Fujinaga

悪意あるユーザ存在下での自律復旧型ネットワーク

存在恶意用户时的自主恢复网络

• 发表时间: 2011
• 作者: 山内由紀子

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

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

• 发表时间: 2013
• 作者: Yukiko Yamauchi

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

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

• 发表时间: 2013
• 作者: 佐々木徹