# 分散相互排他 ## 定義 中央の調停者を置かず、複数のプロセスが単一の資源を排他的に使う順序をプロセス同士で決める問題である。Lamport は論理クロックによる全順序を使い、各プロセスがローカルな要求キューを持つ 5 規則で解いた。要件は、解放後に次へ渡す、要求順に許可する、解放が行われるなら全要求がいずれ許可される、の 3 つである。 ## 主な特徴 - 中央のスケジューラが到着順に許可する方式は、メッセージ到着順が要求順と食い違いうるので要件を破る。 - 許可の条件は、自分の要求がキュー内で全順序の最小であることと、他の全プロセスから後の時刻印のメッセージを受けたことである。 - 全プロセスの参加を要するため、1 プロセスの障害で全体が止まる。 ## 横断的知見 (初出 ingest のため、複数ソースの突き合わせによる知見はまだない。) ## 未解決の問い - 障害耐性のある分散ロック(リース)とどう接続するか。 ## 関連 - 概念: [[レプリケートされた状態機械]] / [[分散ロックとリース]] / [[ID生成器と論理クロック]] / [[happens-before関係]] - 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]](「全順序と相互排他」節)