- [[Randomized Consensus Algorithm]] - [[Asynchronous Network]]で動作する[[Binary agreement]]を提案 - ランダム性を使って[[FLP Impossibility]]を回避 - 証明が与えられていない。証明した論文は[[The correctness proof of Ben-Or’s randomized consensus algorithm]]（2012年） # 書誌情報 - **タイトル**: Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols - **著者**: [[Michael Ben-Or]] - **出版年**: 1983 - **ジャーナル・カンファレンス**: [[PODC]]'83 - **Abstract**: Recently, Fischer, Lynch and Paterson proved that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We exhibit here a probabilistic solution for this problem, which guarantees that as long as a majority of the processes continues to operate, a decision will be made (Theorem 1). Our solution is completely asynchronous and is rather strong: As in, it is guaranteed to work with probability 1 even against an adversary scheduler who knows all about the system. ## 論文PDF ![[800221.806707.pdf]]