# レプリケートされた状態機械 ## 定義 同期の仕様を状態機械(コマンド集合、状態集合、遷移関数)で書き、各プロセスが全プロセスのコマンドを同じ順序で独立に実行して同一の状態を保つ方式である。順序の合意が本質であり、Lamport は論理クロックによる全順序をその順序に使った。コマンドは、より小さい時刻印の全コマンドを知った時点で実行できる。 ## 主な特徴 - 中央調停者も中央記憶も要らない。 - Lamport の原論文の形は全プロセスの参加を要し、1 プロセスの障害で全体が止まる。障害耐性は別の課題として残される。 - 分散相互排他は特殊例であり、状態は待ち要求のキューである。 ## 横断的知見 (初出 ingest のため、複数ソースの突き合わせによる知見はまだない。) ## 未解決の問い - 障害耐性のある形(多数決による順序合意)との関係を、合意プロトコルのソースで確かめたい。 ## 関連 - 概念: [[状態機械]] / [[分散相互排他]] / [[分散合意プロトコル]] / [[ID生成器と論理クロック]] - source: [[@1978__CACM__Time Clocks and the Ordering of Events in a Distributed System]] ## 出典 - [[@1978__CACM__Time Clocks and the Ordering of Events in a Distributed System]](「状態機械への一般化」節)