論理時計
logical clock
message 送信側
code:ruby
@time += 1
receiver.message(@time)
code:erlang
send(receiver, time + 1)
sender(time + 1)
message 受信側
code:ruby
def message(sender_time)
end
code:erlang
receive do
sender_time ->
new_time = max(time, sender_time) + 1
end
分散システムにおいてあるイベントが別のイベントよりも時閒的に先行するといふ槪念について考察し、これがイベントの半順序 (poset)關係を定義することを示す。さらに、イベントを全順序附け可能な論理クロックシステムを同期させるための分散アルゴリズムを提案する。この全順序附けの應用例として、同期問題を解決するための手法を具體例とともに解說する。最後に、このアルゴリズムを物理クロックの同期に適用した場合について詳細に檢討し、クロックが同期からどの程度ずれ得るかについての理論的限界値を導出する。 happened-before 關係$ a\to b
或る同一の process 內で、event$ aが起き、その後に event$ bが起きたならば$ a\to b
或る同一の message を、或る process が送った event が$ a、或る異なるかもしれない process が受け取った event が$ bならば$ a\to b
推移律 :$ a\to bかつ$ a\to cならば$ a\to c 關係$ a\to^* b
或る system 內で起こる全ての event の集合を$ \cal Sとする
關係$ a\to bは$ \cal S內での關係
その system と因果關係のある、その system の內外の全ての event の集合を$ \underline{\cal S}とする
$ \underline{\cal S}內での happened-before 關係を$ a\to^* bと書く
時計$ C\lang a\rang
event から數値への函數
process$ i內で event を數値に對應される時計を$ C_i\lang a\rangと書く
$ C\lang a\rangは global な時計
clock 條件
$ a\to bならば$ C\lang a\rang<C\lang b\rang
强い clock 條件
$ a\to^* bならば$ C\lang a\rang<C\lang b\rang
vector clock
{node_id => timestamp}
node 每の論理時刻を記錄した時計をもつ。message を送る際に、自分の時計の自分の時刻だけを increment し、時計の全體を相手に送る。message を受け取ったら一緖に受け取った時計を自分の時計と倂合 (最大値) し、自分の時刻だけを更に increment する
發展
Plausible Clocks
Chain Clocks
Interval Tree Clocks
Bloom Clocks
version vector
node 每の論理時刻を記錄した時計をもつ。message を送る際に、時計の全體を相手に送る。message を受け取ったら一緖に受け取った時計を自分の時計と倂合 (最大値) し、自分の時刻だけを更に increment する
發展
Hash Histories
Concise Version Vectors
Version Stamps
Interval Tree Clocks
Bounded Version Vectors
Dotted Version Vectors