CAP теорема

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

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

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

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