Bandle

• State Machine Replicationのアルゴリズム。Asynchronous State Machine Replication。Crash-fault torelant。
• EuroSys 2024

概要

• RaftなどのState Machine ReplicationアルゴリズムはPartially synchronous system
  • リーダー等の選出のタイミングの仮定に依存しており、パフォーマンスボトルネックが見られる。
    • Safety Property (Strong Consistencyなど)は保証されても、Liveness, Availabilityはメッセージ伝送の最大遅延時間の仮定が崩れると達成されない
      • たしかにね(kekeho)
  • フェイルオーバーアルゴリズムも複雑。
• BandleはLeaderless SMR, Asynchronous State Machine Replication。
  • FLP Impossibilityの通り非同期でSafety, Availabilityを両立するのはできないので、乱択アルゴリズムに頼る
• Ben-Or’s randomized consensus algorithmライクなFlashBAコンセンサスアルゴリズムを採用

参考

• https://dl.acm.org/doi/10.1145/3627703.3650091