分散システムの各プロセスにおける送受信の半順序関係をすべてのプロセスで起きた送受信の全順序関係に拡張するアルゴリズムを提案し、アルゴリズムを同期処理に応用できることを例示した。 分散システムではプロセスの時刻が同期しているとはかぎらない。 各プロセスで起きたメッセージの送受信をプロセスでの時刻順に並べられても、その計測時刻を信じて全プロセスで起きたイベントを正しく発生順に並べることはできない。
アルゴリズムは、プロセスごとに論理的なクロックをもたせる。 クロックは、メッセージを送信するときに時を進める。 メッセージを送信するプロセスは、送信時刻をメッセージにふくめる。 受信したプロセスは現在の時刻とメッセージにある送信元の時刻より先の時刻に時を進める。 以上の手続きで、異なるプロセス間の送受信であっても送信時刻が受信時刻より必ず前になり、全プロセスの送受信イベントに全順序関係を定義できる。
データ処理サービスは、処理の正確さ、遅延、システムの複雑さの間にトレードオフを抱える。 ストリーミング処理サービスのStorm, Samza, Pulsarは、(論文が発表された2015年時点では)メッセージ配信がexactly-onceではなく欠損や重複する。 MapReduceやSparkなどのバッチ処理サービスは、バッチ処理の単位までデータが集まらなければバッチ実行できない。 Lambda architectureは、システムの複雑化を許容し、2つのアーキテクチャを使い分けることで、処理の正確さと遅延のバランスをとる。
プランニングポーカーのように、ソフトウェア開発の工数を見積もる手法の前提には、プロジェクトに一定期間在籍する専門家がいることがある。 しかし、OSS開発はその限りではなく、見積りの対象になるイシューの数は多い。 各イシューの見積りに5分から10分時間をかけるなら、Linux Kernelのバックログを見積りきるのに半年がかかる。
ビザンチン将軍問題は、故障したコンポーネントがほかのコンポーネントに誤ったメッセージを送りうるとき、コンポーネント間でメッセージを交換した結果、すべてのコンポーネントが一つの正しいメッセージを合意する問題をあつかう。 アルゴリズムは、署名付きメッセージを使うものと使わないものの2つがある。 署名付きメッセージを使うと、受信したメッセージが改ざんされたかをコンポーネントが判断できる。 署名を使わない場合、3分の2より多くのコンポーネントが正常でなければシステム全体が正しい1つのメッセージについて合意にできないことを示した。
Browsemapsは、LinkedInのアイテムベースで水平型の協調フィルタリングである。 Browsemapは、LinkedInの画面上にある推薦するコンテンツを並べたコンポーネントを意味する。 ここでの水平型は特徴の種類の違いによらず異なるエンティティを統一的に扱えることであり、実際に、人、仕事、会社など複数のエンティティをBrowsemapsでユーザに推薦している。
オブジェクトを読み書きする並行プロセスの実行系列があるとき、読み書き操作がアトミックであるように観測でき、かつ、プロセスの実行を仮に直列化したときと同じ実行結果をえられる条件を示し、これを線形化可能性とよんだ。 線形化可能性は、直列化可能性と同様に安全性の条件だが、直列化可能性にはないローカル性がある。 いいかえると、各オブジェクトが線形化可能かつそのとき限り、システム全体が線形化可能になる。 また、ローカル性だけでなく、ノンブロッキング性もあり、操作がオブジェクトの任意の状態において定義されていれば、受信したリクエストの操作を保留しているオブジェクトは別オブジェクトの保留した操作の完了を待たずに自分の操作を進行できる。
分散システムのあるシステムから発せられた通信は、システムより低いレイヤーのネットワークを通り、ほかのシステムに到達する。 論文の発表当時から、分散システムの信頼性にかかわる機能には、途中の低レイヤーではなく高レイヤーの終端におくべきものがあると知られていた。 表題の論文は、それらを列挙し、END-TO-END ARGUMENTSと名付け、原則として提示する。 例えば、データの完全性の保証、メッセージの重複対応、メッセージが到達したことの保証が原則にあてはまる。 これらの機能を途中の低レイヤーにおくと、検証後の経路でメッセージが壊れた場合、送信元が重複メッセージをおくる場合、対向システムが受信したメッセージを処理できない場合に対処できない。 分散システム全体の信頼性をあげるのであれば、信頼性を上げる機能を低レイヤーではなく終端の高レイヤーにおくほうが効率がよい。
System Rは、1970年に発表されたリレーショナルモデルを実装した初めてのリレーショナルデータベースである。 1981年に発表された表題の論文は、System Rの開発プロジェクトを3つのフェーズに分け各フェーズごとにえられた知見をまとめている。 Phase 0は、74年から75年にかけて、シングルユーザ向けにSQLサブセットと対話的なインターフェースを開発した期間にあたる。 Phase 1は、76年から77年の、Phase 0のコードを破棄し、マルチユーザに対応しSystem Rの機能を完全に実装するまでの期間である。 Phase 2は、78年から79年にSan Jose Research Laboratoryなどでの実用にもとづく評価期間にあたる。
日本語用のbeamerスライドのデザインを作った。 飽きないように単純なデザインにした。 デモはこっち
Union Findを使うと通せる。すべての\(A_i\)と\(A_{N+1-i}\)が同じグループに所属するために必要なunionの回数を答えればいい。