legokichi

要約: 『Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services』

概要

• 著者: Seth Gilbert、Nancy Lynch、発行年: 2002
• いわゆる"CAP定理"の話:
  • 「分散環境では 一貫性(Consistency) と 可用性(Availability) と 分断耐性(Partition tolerance) の三つを同時に達成することはできない」
• その不可能性の証明と、その制限を非同期環境および部分的同期環境でどう緩和するか、が述べられている

legokichi

第四部 ハイレベル通信抽象

第四部の内容:

• メッセージの非同期送受信に基づく分散システムに、ハイレベルな通信抽象を付与する
• 12章:
  • メッセージ配送順序が特定の性質を満たすようにするための抽象群を扱う
  • 因果メッセージ配送、が一番重要
• 13章:
• ランデブー通信抽象、および、論理的に即時な通信、を扱う

legokichi

第八章 非同期分散チェックポイント

• 非同期分散システム上でのチェックポイントを扱う章
• 最初に以下を提示:
  • ローカル及びグローバルチェックポイントの概念
  • 同じ一貫グローバルチェックポイントに属するローカルチェックポイント群のための必要条件と十分条件を述べた定理
• 次に、ローカルチェックポイントによって拡張された分散計算に関連する 以下の二つの一貫性条件を考える (後者の方が強い):
  • 1. Zサイクルフリーダム: 任意のローカルチェックポイントが、一貫グローバルチェックポイントに属することを保証する
• 2. ロールバック依存追跡性: 一貫グローバルチェックポイントが、オンザフライで各ローカルチェックポイントに紐付け可能なことを示す

legokichi

第二部 分散システムでの論理時間とグローバル状態

第二部は四章からなり、以下の内容を扱っている:

• 分散計算の、イベント/ローカル状態/グローバル状態、の概念
• それらに関連した論理時間について
• => __信頼可能な__分散システム上での非同期分散計算の性質を考察する上で基礎となる概念

六章:

• プロセスのイベント群の部分順序によって、分散計算を表現する方法

legokichi

第五章 ネットワークを航行するモバイルオブジェクト

概要:

• モバイルオブジェクト:
  • ユーザプロセスのリクエストに応じて、プロセスからプロセスへと移動する
• この章では、モバイルオブジェクトがネットワークを航行するためのアルゴリズム、を扱う:
  • 性質の異なる三つの分散アルゴリズムを取り上げる
  • 全てのアルゴリズムは、以下を保証する:
• 整合性: オブジェクトは同時に複数プロセスに存在しない

legokichi

第一部 分散グラフアルゴリズム

第一部は分散グラフアルゴリズムを扱う:

• 分散システムをグラフと見立てる
  • 頂点はプロセス(ノード)に対応
  • 辺は通信チャンネルに対応

五章構成:

• 一章: 基礎定義とネットワーク探索

legokichi

第四章 リーダー選出アルゴリズム

抜粋

• リーダー選出問題を扱った章
• リーダー選出:
  • 分散システムを構成するプロセス群中から一つを選ぶ
  • 通常、選ばれたプロセスは、調整/制御を目的とし、特別な役割を果たすことが要求される
• リーダー選出は分散システムの対称性を崩す

legokichi

前付

序文

分散コンピューティングとは何か？

1970年代後半に生まれた:

• 研究者/実践者が物理分散システムに固有の性質に取り組み始めた

legokichi

第30章 並行、分散、クライアント／サーバ、インターネット

注意:

• かなり大雑把にまとめたので細部は間違っているかもしれません
• 結構しっかりと書かれているので並列処理周りに興味がある人はちゃんと読んでみても損はないと思います

前置きと主張

legokichi

18 トランザクショナルメモリ

18.1 導入

これまでの章で取り上げたデータ構造はロックやCAS等の同期プリミティブを使っている:

• 現在の種類
• これらを使って効率的なデータ構造を実装することは可能
• ただし欠点も多い