データ処理サービスは、処理の正確さ、遅延、システムの複雑さの間にトレードオフを抱える。 ストリーミング処理サービスの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の回数を答えればいい。
各サーバーがネットワーク全体の情報を保持しない分散キャッシュネットワークにホットスポットを生まないためのキャッシュプロトコルを開発した。 表題のconsistent hashingは、プロトコルの基礎になるハッシュ関数で、関数の写像が値域の違いに影響されにくい。 この影響しにくさは、クライアントから見えるアクティブなサーバが入れ替わる可能性に対して機能する。 また、クライアントは一部のキャッシュサーバーにアクセスできればよく、クライアントごとにアクセス可能なキャッシュサーバーの集合は違ってよい。