Bounded Timestamp

• 有限の値でTimestampを管理する手法
• タイムスタンプを用いるMutexアルゴリズムで使われる大事な機構
  • Lamport’s Bakery algorithmでは、ラベル(Timestamp)の値がオーバーフローすると詰んでしまうので、有限(Bounded)のタイムスタンプを使いたい
• 各プロセスは有限の範囲内でタイムスタンプを割り当てられる
• タイムスタンプ値は循環する
• 空間計算量: n個のプロセスに対してn個必要
• シーケンシャルなアルゴリズム。これの並行タイムスタンピングアルゴリズムもあるらしい。

アルゴリズム

先行グラフの作り方

• プロセス数$n$に対して、$T^n$を作れば良い
  • $T^1$: Single node
  • $T^2$: 2 happend-before 0 happend-before 1 happend-before 2
    • 2つのスレッドは常に隣接するノード上にトークンを持ち、エッジの方向はそれらの相対的な順序を示す
    • スレッドが2つしかないので、2つしかラベルがなく、これで問題がない
    • この3つのノードの中をぐるぐる回り続ければ良い
  • $T^k=T^2\circ T^{k-1}$:
    • 合成をするには、$T_2$のグラフの各ノードを、$T^{k-1}$で置換すればいい、ということ
    • $T^3$は、$T^2$の各ノードを$T^2$で置換したものである
• インデックス
  • $T^n$のすべてのノードを、$n-1$桁の3進数で表現できる
    • 上位の桁はサブグラフのIndexを表し、上位から$n-1$桁は末端グラフの中のノードを表す
  • $T^3$: 00, 01, 02, 10, 11, 12, 20,21, 22

ラベルづけ

• 同じサブグラフに2つのスレッドがいる場合、そのサブグラフをdominateしている別のサブグラフに入る

  • 同じサブグラフに1つのスレッドしかいない場合は、$T^2$と同様

• $T^3$の例を見ると、1つのサブグラフの中には2つしか入れない。その後に入ってきたやつは、必ずその後のサブグラフに入る

• なんか冗長すぎない? 多重なグラフを作らなくても、$T^2$のノード数を3からスレッド数+1に増やすだけでいい気がするんだけど…

参考

• The Art of Multiprocessor Programming (2章)
• Bounded time-stamps: https://link.springer.com/content/pdf/10.1007/BF02242708.pdf