非同期ロボットネットワークにおける最適なビザンチン耐性収束
Optimal Byzantine Resilient Convergence in Asynchronous Robot Networks
3f+1台のロボットネットワークで最大f台のビザンチン故障に耐え、非同期CORDAモデルで動作する初の決定的アルゴリズムを提案した。1次元空間を移動する無記憶ロボットに対し、有界スケジューリング仮定下で半同期ATOMモデルの下限に一致する。
著者: Zohir Bouzid, Maria Potop-Butucaru, Sébastien Tixeuil
分類: cs.DC, cs.RO
原文アブストラクト
We propose the first deterministic algorithm that tolerates up to $f$ byzantine faults in $3f+1$-sized networks and performs in the asynchronous CORDA model. Our solution matches the previously established lower bound for the semi-synchronous ATOM model on the number of tolerated Byzantine robots. Our algorithm works under bounded scheduling assumptions for oblivious robots moving in a uni-dimensional space.
