CAP теорема

Материал из Викиконспекты
Перейти к: навигация, поиск

CAP-теорема — утверждение о том, что в распределённых системах нельзя одновременно добиться трёх свойств:

  • Consistency — на всех не отказавших узлах одинаковые (с точки зрения пользователя) данные
  • Availability — запросы ко всем не отказавшим узлам возвращают ответ
  • Partition tolerance — даже если связь в системе стала несвязной, то система продолжает работать

Формально мы это не формулировали и не доказывали. Оригинальная формулировка — Brewer's Conjecture (2000), а формализовано в работе Gilbert & Lynch (2004). Там есть много тонкостей с тем, что такое "не отказавший узел", "одинаковые данные", "разрыв связи", "система продолжает работать", "когда система всё-таки окончательно ломается и считается недоступной" и тому подобное.

Для общей эрудиции выглядят неплохо статьи[1][2]

Классификация алгоритмов

Distributed-cap.png