実験・実装 · 基礎から応用へ

出来事のDAGへ論理時計を付ける

三プロセスの模型で先祖集合とLamport番号を計算し、因果の向き、逆命題、壁時計の逆転をassertします。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 出来事の辺を入力として与える
  2. 依存が済んだ順で番号を計算する
  3. 先祖集合で片方向の性質をassertする
  4. 出力を手計算へ戻す
  5. プロセス名と入力順の役割を確かめる
  6. 独立な出来事を足す課題
  7. この記事をロゲイアに質問する理解を確かめる

出来事の辺を入力として与える

この実験はA、B、Cの七つの出来事へLamport番号を付け、因果的に前なら番号が小さいことを検査します。前提は論理時計のガイドです。Pythonで出来事のDAGを処理する決定的な模型で、実際のネットワークから因果関係を推定するプログラムではありません。入力には名前、プロセス、既知の依存、説明用の壁時計を入れます。リストの先に現れた全ての出来事を因果的な先祖にせず、プロセス順と明示した送受信の辺だけを使います。

aとcはA、b、d、eはB、fとgはCです。cからd、eからgがメッセージの送受信に対応します。同じプロセスでは直前の出来事も依存へ加えます。これでa→c→d→e→gという道ができ、b→dとf→gも入ります。bからcには道がありません。コードを動かす前に、この辺だけを紙へ描いてください。出力の番号に合わせて因果の辺を後から足すと、逆命題の反例を自分で消してしまいます。

依存が済んだ順で番号を計算する

コードをclocks.pyへ保存し、Python 3.12以降でpython clocks.pyとして実行します。標準ライブラリ以外は使いません。入力は依存する出来事が先に現れる順なので、処理時に全ての親の時計が既にあります。その条件をassertしてから、親の最大番号へ1を足します。親がない場合は0から1になります。受信の親には自分の前の出来事と相手の送信があるため、max(ローカル,メッセージ)+1と対応します。

この順序を並べ替えて、まだ定義していない送信を参照するとassertが失敗します。実システムでは受信したメッセージが送信番号を運ぶため、送信の全履歴を同じ辞書へ持つ必要はありません。模型は番号の性質を調べるため、全イベントの関係を入力に持っています。その違いを隠さないでください。循環する依存は正しい出来事の前後関係ではなく、このコードもそれを解くアルゴリズムではありません。入力の前提と計算手順を一緒に再現します。

先祖集合で片方向の性質をassertする

各出来事のancestorsは、直接の親と、その親の先祖の和集合です。全ての先祖aと子孫bについてclock[a]<clock[b]をassertします。直接の矢印だけでなく、aからgのような長い道でも性質が保たれることを検査します。さらにbの番号1とcの2を比較し、bがcの先祖ではないこともassertします。番号の大小があっても因果を逆に導けない反例です。同じ番号のaとbも、同時刻の証明ではありません。

壁時計ではcを101、受信dを90と置いています。論理番号はc=2、d=3なので送受信の順を守ります。壁時計の値はこの矛盾を作る説明用入力で、実際の時計同期の誤差を測った値ではありません。ログの表示順やホスト時刻から原因を決める前に、実際の送受信がどの辺を作るかへ戻ります。コードは両方の条件を別々にassertするので、片方だけ通って全てを正しいとする判定を避けられます。

python
events=[
 ('a','A',[],100),('b','B',[],95),('c','A',['a'],101),
 ('d','B',['b','c'],90),('e','B',['d'],91),
 ('f','C',[],80),('g','C',['f','e'],81)]
clock={};ancestors={};last={};wall={}
for name,process,dependencies,time in events:
    required=list(dependencies)
    if process in last and last[process] not in required:required.append(last[process])
    assert all(dep in clock for dep in required)
    clock[name]=max([clock[dep] for dep in required]+[0])+1
    ancestors[name]=set(required)
    for dep in required:ancestors[name]|=ancestors[dep]
    wall[name]=time;last[process]=name
assert all(clock[a]<clock[b] for b in ancestors for a in ancestors[b])
assert clock['c']<clock['d'] and wall['c']>wall['d']
assert clock['a']<clock['e'] and 'a' in ancestors['e']
assert clock['b']<clock['c'] and 'b' not in ancestors['c']
print('logical',clock,'noncausal pair b,c','wall order c,d reversed')

出力を手計算へ戻す

正常ならa=1、b=1、c=2、d=3、e=4、f=1、g=5が表示されます。dはBの前のb=1と受信c=2の大きい方へ1、gはCのf=1とe=4の大きい方へ1です。数字を丸暗記するのでなく、各親へ戻して計算してください。掲載コードはこの入力で正常終了しています。経過時間、通信の遅延、実ホストの時計のずれは測っていません。プロセス名は文字列で、三つのOSプロセスを起動した実験でもありません。

全順序が欲しい場合は番号と安定したプロセスIDの組を使えますが、模型のリスト順を物理世界の全出来事の順と呼びません。bとcをIDや番号で並べても、因果の辺が生まれるわけではありません。どの情報を保存すると、並行であることまで判断できるかという追加の問いには、このスカラー番号だけでは十分でない場合があります。ベクトル時計などの方式を調べる前に、この実験で失われる情報を反例から説明します。

プロセス名と入力順の役割を確かめる

プロセス名を付け替えても、同じローカル順と送受信の辺を保てば、因果辺に沿って番号が増える性質は同じです。ただし名前を同点の全順序へ使う表示なら、並行な二つの表示順が変わる場合があります。この変化は因果関係の誤りではなく、便宜上の規約の差です。どちらの順を比較したかを出力の説明へ残します。

また、aとbのリスト上の順だけを入れ替え、各依存が既知という条件を守れば、相互に独立な時計は変わらない場合があります。リストの通し番号とローカル時計を混同していないかを調べる追加例になります。逆にcより前へdを置けば、送信が未定義なので模型は拒否します。入力の並べ方の制約と、世界の因果的な順序を同じものとして扱わないでください。未知の依存を待ち、後から処理する機能を足すなら、未解決の集合と循環の扱いを別に設計します。

入力の前提に違反した失敗を、時計の性質の破れと呼びません。順序を変えた例は、処理前に参照できる親があるかを先に確かめ、因果辺を変えた例とは別に残します。模型の拒否も契約を確かめる結果の一つです。

独立な出来事を足す課題

課題はCのfの前に独立なローカル出来事を一つ加える場合です。解答ではCの新しい最初が1、fが2、gはmax(2,4)+1=5です。gの番号が変わらなくても、新しい因果の辺は増えています。番号だけから全ての履歴を復元できないことを確認します。逆にBのeをもう一回進めて5にしたなら、gは6になります。どの親が最大かを変える操作と、辺を増やす操作を分けて考えてください。

追加課題は、b<cなのでbをcの依存へ追加してよいかです。解答は、実際のローカル順または送受信の根拠がなければ追加してはいけない、です。数値が偶然同じ順だっただけでは因果の観測になりません。終了後のファイルやサーバーは作りません。イベント、直接の辺、先祖、論理番号、壁時計の五つを対応させ、どのassertが何を検査したかを説明できれば到達点です。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

サーバーの中で起きていること · STEP 16

学習コースから次を選ぶ