あるデータ構造がwait-freeであり、データ構造への操作が有限回のステップで完了するのであれば、ほかの並行プロセスの処理速度によらず、任意のプロセスによるその操作は必ず完了する。 表題のsynchronizationは、wait-freeなデータ構造から別のwait-freeなデータ構造を実装する意味であり、実装の可能性を議論するためにコンセンサス数が導入される。 あるデータ構造のコンセンサス数は、単純な含意形成問題を解くときに参加できるプロセス数の最大値である。 たとえば、read / writeレジスタには1, test & swapは2, compare & swapには無限のコンセンサス数が割りあてられる。 プロセス数を定義した上で、あるコンセンサス数のデータ構造を、それより小さいコンセンサス数のデータ構造では実装できないことを示した。
XenのハイパーバイザーにOSのライブマグレーションを統合し、約60msのダウンタイムでのOSのライブマイグレーションを実現した。 手法の焦点は、短いダウンタイムや移行時間で、移行元と移行先のメモリの状態を同等にできるかにある。 ネットワークアドレスや物理デバイスの移行は扱わない。 移行元と移行先は同じローカルネットワークにあり、マイグレーションによるIPアドレスのホストの移動を主にARP replyで通知でき、NASにデータを保存することを前提にし、ネットワークや物理デバイスの移行を考えなくてよいものとしている。
ANSI SQL-92規格は、トランザクション分離レベルを、Dirty Read, Non-Repeatable Reads, Phantomが発生する可能性で定義する。 トランザクション分離レベルを禁止する現象で定義する理由は、ロックなどの実装手段で定義すると規格が実装に依存するからだと考えられている。 表題の論文は、規格の現象による定義があいまいであり、3つの異常が起きなくても望まない結果になる実行があることを例示した。 また、規格のトランザクション分離レベルが、商用データベースで採用されているトランザクション分離レベルにあてはまらない問題もある。 禁止する現象にDirty Writeをくわえ、厳しく実行列を禁止するように現象の定義を解釈した上で自然言語から形式的な記述に変えることを提唱した。 さらに、規格がデータの版が単一であることを前提としていることを指摘した上で、多版型のトランザクションであるSnaphot Isolationを提案した。
データウェアハウスの概要と発表時期の97年の関連技術を解説した論文で、 データウェアハウスの理論を提唱したInmonにならい、データウェアハウスを目的指向(subject-oriented)で、統合され、時刻を横断する組織の意思決定に資する永続的なデータとらえている。 関連技術を、ETL処理、データ保存方法、保存したデータによる分析の3つに分けて整理する。 データベースの設計手法では、Kimballの提唱したスタースキーマ、その応用のスノーフレークスキーマ, 事実の星座(fact constellations)、インデックスについてビットマップインデックスを解説する。
Bayouは、モバイルコンピューティングむけに95年に発表されたストレージで、弱い一貫性とレプリケーションがある。 発表当時の不安定なモバイルネットワーク環境でもクライアントがストレージにアクセスできるように、一貫性を犠牲にしてクライアントにどんなレプリケーションへの読み書きも認める。 Bayouは、アプリケーションの知識を借りてデータの整合性を復元するアプローチを開拓したストレージとして知られ、書き込み時に開発者が実装した不整合を検知する処理を実行する。 不整合を検知したら、同じく開発者によって実装された不整合を解消する処理を実行する。 ただし、書き込みのログをほかのレプリケーションに伝搬することでデータを同期するため、どんなレプリケーションでも不整合の検知と解消の処理が同一の結果になるように、これらの処理は決定的でなければならない。
分散システムの通信をpublish/subscribeモデルにするとシステム間の結合を疎にできる。 タイトルと同名の2003年に発表された論文は、publish/subscribeのサーベイであり、publish/subscribeモデルを空間、時間、同期の3種の結合度を下げる技術ととらえ、ほかの通信技術と比較する。 次に、先行研究のpublish/subscribeモデルを、購読するイベントの宣言手段によって、topic-based, content-based, type-basedに分類する。 最後に、メッセージブローカを使うかどうかなどpublish/subscribeモデルの設計や実装の利点や欠点を整理する。
DryadはMicrosoftで開発された分散コンピューティングエンジンであり、MapReduceに近い。 処理を点、処理結果を受け渡す通信経路を辺とするDAGで、分散処理を定義する。 通信経路にはファイル、TCP, FIFOを使え、実行環境は1台のマルチコアのコンピュータから数千台のコンピュータまでスケールできる。 MapReduceは入力と出力が一つでなければならないが、DryadはDAGであれば入力と出力が複数あってもかまわない。
Chubbyは、助言ロックをかけられるファイルを作れる低容量のストレージであり、分散システム向けのロックサービスとしてはたらく。 処理性能よりも高可用性と信頼性を重視し、ロックを保持する期間は数時間から数日にわたる長いものを想定する。 ロックされたファイルで実行環境の情報を共有でき、例えばリーダーの選出にも使える。 Chubbyは既存のアルゴリズムを集積であり、表題の論文は、新しいアルゴリズムよりも、Chubbyの設計や想定していた使用方法や実際の使われ方の解説に重点をおく。 Chubbyはロックサービスとして作られたが、ネームサーバとして最もよく使われる。 数千規模の互いに依存するプロセスがあり、プロセスが落ちたら新しいプロセスに置き換えるとする。 このとき、ネームサーバにDNSをつかうと、DNSは時間で失効するキャッシュ方式なので、TTLを短くし、落ちたプロセスにリクエストが届かないようにすると、DNSへの負荷が増える。 一方、Chubbyのキャッシュは時間ではなくファイルに変更されたときに無効になるので、Chubbyをネームサーバに使うことで、名前解決の負荷を減らすことができる。
86年の10月に生じたインターネットの輻輳の反省から、4BSDに7つのTCPの輻輳制御のアルゴリズムが導入された。 うち5つは、送信したパケットが到達や消失でネットワークからなくなるまでウィンドウサイズ以上の新しいパケットを送らない原則を守るためにある。 この原則をconservation of packets principleという。
トランザクションを並行実行するときに、直列実行した場合と同じ実行結果をえるには、各トランザクションがロックを解放後に新しいロックを獲得してはならないことを示した。 その場合もデッドロックがおきうるが、それは並列実行を終了するためにはいつロックをかければよいかという議論である。 ここでは、並列実行が終了した場合に直列実行と同じ結果になる一貫性を保証できるロックの順序を問う。