3.4 時計サービス

プロセス間の相互作用に関する時空間モデル（time-space model）では､イベントは各プロセスに固有の時計による時刻と共に記録される。

時計サービスの分類：

l 時刻（time）
相対的な発生時刻の計測

l タイマー（timer）
絶対的な時間間隔の計測

時計サービスの用途：

l イベントの発生時刻

l イベントの所要時間

l イベントの発生順序

時計サービスの例：

l ファイルの最終更新時刻

l クライアントがサーバーへ特権的にアクセスすべき時間の長さ

l データオブジェクトに対する更新の順序

時計によって表現される時間の性質（同一プロセス内）：

l 一様かつ単調な増加

l イベントの発生順序を曖昧さなく決定可能

別々の計算機上にある時計の認識は異なる。

⇒ 時間について大域的な合意を取る必要がある。

大域的な合意が必要な例：

l 分散GC

l 毎晩のファイルのバック・アップ計画

l 受信メッセージの失効の確認

この節の内容：

l 分散システムにおける時計の基本概念

Ø 物理時計

² 時刻と間隔についての実時間計測の近似

Ø 論理時計

² イベントの順序を定める仕組み（分散システムでは重要）

3.4.1 物理時計

物理時計の用途：

l ハードウェア

Ø 同期、スケジュール

l ソフトウェア

Ø 実時間を模倣、時間間隔の計測

l ソフトウェア動作の追跡
（ハードウェア割り込みを利用したソフトウェア・タイマーによる）

分散システム上で同期されている物理時計の用途：

l プロトコルにおける例外処理のためのタイム・アウト

Ø あるプロセスが設定した期限を別の計算機上にあるプロセスが検査する

l secureなinternet越しの通信のためのタイムスタンプ

Ø 不正に複製されたメッセージを検知してplay back攻撃を避ける

Ø アクセス制御の際に特権の有効期間を定める。

分散システムにおける時計の特徴：

l 各時計は独自の調子で進む

l 時刻の報告のための通信の遅れ

⇒ 大局的かつ絶対的な物理時間は得られない

⇒ 大局的な近似（全ての計算機の合意）で妥協

大局的かつ近似的な時計の課題と処方：

l 全ての計算機を合意させる。
⇒ 時間同期アルゴリズム（clock synchronization algorithm）

l 実時間に可能な限り近づける。
⇒ 世界時の供給源（universal time resource）

本文図3.8「分散時計サービスのアーキテクチャ」：

分散時計サービス（Distributed Time Service [DTS]）

l 時計サーバー（Time Sever [TS]）：

Ø 世界時の供給源にアクセスして遅れのない時間情報を維持している。

Ø サーバー同士は相互に時間情報を交換して整合性を高めることができる。

l 時計窓口係（Time clerk [TC]）：

Ø 各クライアント計算機に1つづつある。

Ø クライアントから依頼に応じて1つ以上のTSに連絡を取る。

分散時計サービス実装上の問題：

l 時間を報告する際の遅れの補償

l 時間情報の供給源間にある不一致の修正

遅れの補償

分散時計サービスにおける3種類のアクセス：

l 時計サーバーから標準時間の供給源へ

l クライアントから時計サーバーへ

l 時計サーバー間相互

計算機が利用できる協定世界時（Universal Time Coordinated [UTC]）の供給源は幾つかある。

米商務省国立標準・技術院（National Institute of Standard and Technology[NIST]）は1msの精度でUTCにアクセスする幾つかの手段を提供している：

l Automated Computer Time Service[ACTS]・・・ダイアルアップで受けられるサービス（あまり頻繁でないアクセス向け。ソフトウェアの活動追跡に利用するには遅すぎる。）

l [WWV]・・・定期的にUTC信号を発信する短波放送（ACTSより頻繁なアクセス向け。発信局との距離と伝達時間が分かれば遅れも計算できるはずだが、短波の場合大気の影響があるのでそれは疑わしい。）

その他の手段：

l Global Positioning System[GPS]・・・（GPS衛星は低高度の軌道で位置が安定しておらず、遅れを計算するには複数の衛星を監視している必要があり､そのための設備と関連する計算は高くつく。）

l 位置が安定していて地上局からの距離が一定な静止衛星からのUTC信号も利用できるが、遅れは大きい（約125ｍｓ）。

l 多くのケーブルTVにもUTC信号が乗っている。

以上のUTC供給源には賛否あるが、幸いなことに、１つのTSが適宜精確に現在のUTCを伝達できるならば全てのTSがこれらの供給源にアクセスする必要はない。

クライアント－TS間、TS相互間で起こるUTC伝達の遅れは上記の単なる伝達遅れとは別の問題。（信号伝達の遅れに加えてネットワーク通信に起因する遅れもある。ネットワーク通信に伴う遅れは不規則で信号伝達遅れよりも数段大きい。）

伝達遅れの補償：

1. Ts：送信時刻、Tr：受信時刻､tp： TSでの処理時間（tpは前もってわかる）とすると往復遅れ（round trip delay）は(Tr-Ts-tp)

2. 往復遅れの半分を加算して、TSからクライアントに返されたUTCを補正できる。（往路と復路で遅れが対称であると仮定。）

時計の合わせ方：

l ローカルな時計がUTCより進んでいる場合は進み方を遅らせることによって対処し、巻き戻さない。（単調増加するという前提を守る。）

l ローカルな時計がUTCより遅れている場合は直接合わせても問題は少ないが、できれば進み方を早めることで対処する。（例えばタイム・アウトを待っているプロセスがタイム・アウトの発生と勘違いしないように。）

上記のような問い合わせ－回答に基づくpullモデル（受動的なTS）に対してTSからのブロードキャストに基づくpushモデル（能動的なTS）もある。（pullとpushはどちらもTS相互間についても適用可能）

Pushモデルの得失：

l 高い整合性を維持できる。（時間情報が定期的に発信されているので）

l クライアント側ではネットワークによる伝達遅れを推定する方法が簡潔でない。
⇒ ネットワーク遅れが小さく事前に推定しやすいマルチ・キャスト・ハードウェアがある場合に向く。

（ネットワークが混雑しているときは特に）遅れが精確に推定できないとTS間の不一致を生む。

改善策（pushでもpullでも）：

l TSは相互に各々のUTCを修正し合える。

l クライアントは複数のTSから情報を得て不一致を修正できる。

不一致の修正

TSが相互にUTCを修正し合うには（pushでもpullでも）：

1. 他のTSとUTCを定期的に交換する。

2. 幾つかのUTCを収集する。

3. 前もって定めた判定基準を利用して自身のUTCを修正する。

⇒ 合意が形成される

l ＜判定基準その1＞簡単な基準：
新しいUTCの値として収集したUTCの中間値か平均値を取る。平均値を計算する場合､疑わしい大きさ、小ささの値は棄却できる。
（最大値、最小値、中間値、平均値が考えられるが､整合させるためである場合は中間値か平均値が望ましい。）

l ＜判定基準その2＞TSが保持するUTCにある僅かな不確かさを考慮に入れた基準：
TSは区間UTC±⊿Iを報告し（⊿Iは不正確さの統計的な指標または信頼区間）、図3．9のように他のUTC区間と重なりがないUTC区間は除いた上で､重なっている区間を算出しその中央値を新しいUTCとする。

TSが互いに整合していたとしても、クライアントが受け取るUTCには予測不能なネットワーク遅れに起因する不一致があるが、これは複数のTSと連絡を取ってTS同士の場合と同じ戦略で修正すれば緩和できる。

3.4.2 論理時計

l 物理時計は実時間の近似を提供して有用だが、非常に近接したイベントの順序を厳密に決定するのには向かない。
（UTCの精度を上げてもUTCの区間内でイベントが重なればイベントの順序を区別できない。）

l 加えて､分散システムでは共通の物理時計を高精度に維持することは容易でない。

一方､多くのアプリケーションは、イベントの実時刻で同期やスケジュールされる必要はなく、イベントの実行順序だけに関係する。
⇒ イベントの順序を決定するだけの論理時計が利用できる。

Lamportの論理時計

各プロセスPiが論理時計Ciを持つ。

論理時計の同期のためイベント間のhappens-before関係→を代数的に定義：

l 関係→は推移的

l 関係→は反反射的

⇒ 推移的に関係をつけられないイベント同士は並行。このようなイベントについてはイベントの順序関係は定義されない（部分順序）。

例・・・図3.10：

l a, e, cとa, e, hは→関係で推移的に順序付けられる。

l b, eとf, hはそれぞれ並行。

全イベントの全順序化：
＜手段＞関係→で結ばれない（無関係な）イベント同士が論理的には同時でないことを保証すれば全順序化できる。
（無関係なイベントに全順序をつけることはプロセスの正しい実行順序には無関係。）

＜利点＞イベントの正しい順序を適切に表現できる。
（多くの並行制御アルゴリズムは論理時計に基づくイベントの全順序という属性を利用している。）

以上に基づいて以下のように論理時間を定義：

1. a→bはイベントaがbより前に起こることを意味し、a→bならばC(a) < C(b)。
（上記は一つのプロセス内でなら問題なく定義できる。ここで論理時計はイベントが発生するたびに必ず進み、戻ることはない。）

2. プロセスPi、Pjがそれぞれsend、receiveするときCi(send) < Cj(receive)
（プロセスはsend、receiveの対を通じてのみ相互作用を及ぼし、sendが完了しない限りreceiveは完了しないから）。

3. ＜全順序化するための規則＞
全てのイベントについて、a≠bならばC(a) ≠C(b)

整数値による論理時計の実装：

1. 同一プロセス内のイベントについて、発生ごとにクロックへ任意の正数を加算することで容易に実現できる。

2. sendの際に論理時計の時刻をタイム・スタンプTSi　=　Ci(send)としてメッセージにつけて送り､受信側ではタイム・スタンプに幾らか正定数dを加えたものと、メッセージ受信時における自身の論理時計の時刻Cj(_receive)という両者のうち大きい物max(TSi+d, Cj(_receive))を新たに論理時計の時刻Cj(receive)とすることで実現できる。

3. プロセスid（プロセスごとに固有）と論理時計の値を結合すれば実現できる。

3.4.3 ベクトル型論理時計

（整数値による）論理時計で順序付けられたイベントが実際にもその順序である保証はない。（逆順にはならないが、並行している場合はあり得る。）

ベクトル型論理時計：

l n個のプロセッサのi番目のプロセッサのベクトル型時計VCiは
VCi=[TS1, TS2, ・・・, TSi, ・・・, TSn],

l TSi=Ci(a)は前節で定義した論理時計

l TSk （k≠i）はシステム内で交換されたメッセージのタイム・スタンプに基づく各プロセッサPkの論理時計の最良推定値。

動作：

1. 初期値はベクトルの全要素の値が0

2. 基礎となる論理時計Ciは規則1に従う。

3. TSk （k≠i）は以下のように修正された規則2に従う。
sendの際にメッセージmに論理時計ベクトルをタイム・スタンプVCi(m)としてつけて送り､受信側ではreceiveの際、TSｋ(m)タイム・スタンプと、メッセージ受信時に保持している時刻の推定値TSｋ(send)という両者のうち大きい物max(TSｋ(m), TSｋ(send))を新たに論理時計の時刻TSｋ(receive)としてから、TSi=Ci(a)に正定数を加算することで実現できる。
（この修正で、メッセージが行き来するごとにTSｋが各プロセッサへ伝播する）

ベクトル型論理時計の正しさ：
VCi(a)<VCj(b) ⇔ 1≦k≦nについてTSk(a)≦TSk(b)かつTSj(a)<TSj(b)

l プロセスPiで起こったイベントaとプロセスPjで起こったイベントbについてa→bならばVCi(a)<VCj(b)
（send-receiveならばこれは上記3より成り立ち、同一プロセス内ならば上記2より成り立つ。）

l 無関係なイベント同士の場合VCi(a)<VCj(b) は成り立たない。
（当然Piは自身のTSi=Ci(a)について他より良い推定値を持っていてその値は他のプロセッサのTSi以上である。）

l 同様にしてVCi(b)<VCj(a)が成り立つのはb→aの場合だけ。

以上より2つのイベントについてベクトル型論理時計を比べれば関係→が推移的に成り立っているかどうかがわかる。

例・・・図3.11：

l VC1(a)=[1, 0, 0]<VC2(e)=[2, 3, 0]<VC3(h)=[2, 4, 3]は→関係で推移的に順序付けられる。

l 並行なb, fにはVC1(b)=[3, 0, 0]<VC2(f)=[2, 6, 0]もVC1(b)=[3, 0, 0]>VC2(f)=[2, 6, 0]も成り立たない。

3.4.4 行列型論理時計

ベクトル型論理時計は行列型論理時計に拡張できる。

l 第i行MCi[ i, 1, …, n ]はi番目のプロセッサPi自身のベクトル時計。

l 第j行MCi[ j, 1, …, n ]はi番目のプロセッサPiが持つプロセッサPjのベクトル時計の推定値。

更新規則：

l 同一プロセス内イベント：
ローカルなクロックの更新：
MCi[ i, i ] = MCi[ i, i ]+d

l メッセージ送信時：
プロセスPiからプロセスPjへメッセージを送る際にはMCi[k ,l ]をそっくり丸ごとタイムスタンプTSi[k, l ]として送り、受け取った側は自身のベクトル時計を更新（関係→による順序を維持）
MCj[j, l ] = max(MCj[j, l ], TSi[j, l ])
つづいて行列全体を更新（他のプロセッサから伝播してきた知識）
MCj[k, l ] = max(MCj[k, l ], TSi[k, l ])

12章では行列型時計をGCの複製管理に利用。