Блог

Существует ли протокол логического синхронизации (например, временные метки Лампорта или векторные часы), который обеспечивает полный порядок событий в распределенной системе без простого произвольного разрыва связей? Если это невозможно, есть ли доказательства?

Нет, такого алгоритма не существует, и есть доказательство, см., например, теорему 2.21 в G. Tel, Введение в распределенные алгоритмы, 2-е изд. Грубо говоря, теорема утверждает, что при наличии причинного порядка событий фактическое вычисление может выполняться любым способом, который совместим с причинным порядком.