分散合意アルゴリズムにおけるリーダーを含む全ノード参加型の選挙によるビザンチン故障耐性とクラスター内の合意

分散合意アルゴリズムでのByzantine fault tolerance の達成は，各ノードとの密な通信によって実現される．PBFT(Practical Byzantine Fault Tolerance) アルゴリズムは実用的ではあるが，合意形成時の通信コストはO(N 2) であり，ノードが増加するごとにその通信コストは大幅に増加する．そこで，選挙形式の合意形成を行うアルゴリズムを提案する．このアルゴリズムは，クラスター内の各ノードをleader もしくはfollower の２つの役割に分ける. そして，leader を含めた全ノード参加型の多数決による選挙を行う. この合意選挙は,leader からマルチキャストで送信されたデータを受信したfollower がランダムのタイムアウトをトリガーに, 自身がleader から受信したデータを他ノードに送信することにより開始される. 他のfollower からの選挙開始と共にデータを受信したfollower は自身がleader から受信したデータと一致するか比較を行う.leader はクライアントから受け取ったデータと一致するかを比較を行う. 一致した場合はその選挙に応答する. その応答がleader を含む過半数のノードから送信されたことを確認できた場合, 選挙は成功であり, クラスター内の定足数ノードに複製されたことになる. その後,leader がコミットの許可を出す. この選挙形式の合意形成手法を採用することにより,PBFT のような各ノード間の密な通信を行わずに各ノードの受信状況を把握できる. 結果として, 合意形成に至るまでの通信回数を大幅に削減できる. このアルゴリズムをKubernetes 環境でコンテナに実装し，合意形成にかかる通信コスト(通信回数) を評価する．本提案アルゴリズムの合意形成に要する通信回数の平均値とPBFT の通信回数を算出して比較した結果,PBFT の約76 ％以下のコストに削減することが期待できた. ...