Posts

気になったものの備忘録

オブジェクトを読み書きする並行プロセスの実行系列があるとき、操作がアトミックであるように観測でき、かつ、プロセスの実行を仮に直列化したときと同じ実行結果をえられる条件を示し、これを線形化可能性と呼んだ。 線形化可能性は、直列化可能性と同様に安全性の条件だが、直列化可能性にはないローカル性がある。 つまり、各オブジェクトが線形化可能かつそのとき限り、システム全体が線形化可能になる。 また、ローカル性だけでなく、ノンブロッキング性もあり、受信したリクエストの操作を保留しているオブジェクトは別オブジェクトの保留した操作の完了を待たずに自分の操作を実行できる。 ただし、そのためには、オブジェクトの任意の状態における操作の振る舞いが定義されていなければならない。

分散システムにおける通信は、あるシステムから送られると、システムより低いレイヤーのネットワークを通り、ほかのシステムに到達する。 論文の発表当時から、分散システムの信頼性にかかわる機能には、途中の低レイヤーではなく高レイヤーの終端におくべきものがあると知られていた。 表題の論文は、それらを列挙し、END-TO-END ARGUMENTSと名付け、原則として提示する。 例えば、データの完全性の保証、メッセージの重複対応、メッセージの到達の保証が原則にあてはまる。 これらの機能を低レイヤーにおくと、完全性を検証後の経路でメッセージが壊れた場合、送信元が重複メッセージをおくる場合、対向システムが受信したメッセージを処理できない場合に対処できない。 したがって、分散システム全体の信頼性をあげるのであれば、信頼性を上げる機能を低レイヤーではなく終端の高レイヤーにおくほうが効率がよい。

System Rは、1970年にE.F. Coddが発表したリレーショナルモデルを実装した初めてのリレーショナルデータベースである。 1981年に発表された表題の論文は、System Rの開発プロジェクトを3つのフェーズに分け、各フェーズの知見をまとめている。 Phase 0は、1974年から1975年にかけて、シングルユーザ向けにSQLサブセットと対話的なインターフェースを開発した期間にあたる。 Phase 1は、1976年から1977年の、Phase 0のコードを破棄し、マルチユーザに対応しSystem Rの機能を完全に実装するまでの期間にあたる。 Phase 2は、1978年から1979年にSan Jose Research Laboratoryなどでの実用にもとづく評価期間にあたる。

日本語用のbeamerスライドのデザインを作った。 飽きないように単純なデザインにした。 デモはこっち

Union Findを使うと通せる。すべての\(A_i\)と\(A_{N+1-i}\)が同じグループに所属するために必要なunionの回数を答えればいい。

各サーバーがネットワーク全体の情報を保持できない分散キャッシュネットワークにホットスポットを作らせないためのキャッシュプロトコルを開発した。 表題のconsistent hashingは、プロトコルの基礎になるハッシュ関数で、値域の違いに関数の写像が影響されにくい。 また、クライアントは一部のキャッシュサーバーにアクセスできればよく、クライアントごとにアクセス可能なキャッシュサーバーの集合は違ってよい。

ワーシャルフロイト法で全ての2頂点間の最短距離を求めた後、隣接する2頂点の辺のうち、2頂点の最短距離が辺の重みと異なる辺を数えれば通る。

\(K_q\)ごとに二部探索で答えを直接検索しても通すことができる。

AzureのクラウドストレージサービスであるWindows Azure Storage(WAS) は、2008年の11月から本番運用されている。 保存できるデータの形式には、単なるファイル(Blob)のほかにも、テーブルのレコードとキューのメッセージがある。 ハードウェアの故障に備えたローカルでのレプリケーションだけでなく、地理的に離れたデータセンタにもレプリケーションを分散し、災害復旧にも備えがある。