CAP定理

CAP定理はブリュワーの定理とも呼ばれ、分散コンピュータシステムのマシン間の情報複製に関する定理。ウェブサービスを想定して作られた定理。
定義.
ノード間のデータ複製において、同時に次の3つの保証を提供することはできない。
この定理によると、分散システムはこの3つの保証のうち、同時に2つの保証を満たすことはできるが、同時に全てを満たすことはできない。単一障害点があれば、ネットワーク分断が発生した際にシステムがバラバラに分裂しても、そこを基準に一貫した応答ができる(分断耐性+一貫性)が、可用性が成立しなくなる。
個別例.
一貫性＋可用性.
一般的な関係データベース、LDAP、NFS などは一貫性と可用性しか成立しない。2相コミットはこれに該当。ネットワーク分断が発生した際は、片方を切り捨てる。Amazon Relational Database Service の Multi-AZ 配備も該当。
可用性＋分断耐性.
可用性＋分断耐性のケースでも、一定時間以内に一貫性を成立させるシステム（結果整合性; eventually consistent）は構築可能である。Amazon SimpleDB や Apache Cassandra などがこの方式を採用している。DNS や HTTP キャッシュなども該当。3種の中ではこの方式が最も障害に強い。
一貫性＋分断耐性.
Apache HBase などが採用している。HBase の場合、単一障害点がある上、ネットワーク分断に対して整合性をとる仕組みが不完全であるため、可用性が犠牲となっている。
歴史.
この定理は、インクトミの創業者でもあり、カリフォルニア大学バークレー校の計算機科学の教授でもあるエリック・ブリュワーが2000年の Symposium on Principles of Distributed Computing (PODC) で提案（数学的な用語では予想）したのが始まりである。
2002年にMITのSeth Gilbertとナンシー・リンチがブリュワーの予想の厳密な証明を提出し、定理として確立した。