Что решают матричные часы, а векторные - нет?
Я понимаю потребность в векторных часах с точки зрения скалярных логических часов, которые не могут предоставить достаточно информации, чтобы сказать, например, существует ли конфликт обновлений в обновлении хранилища значений ключей.
Но я не уверен, какая проблема все еще не решена с помощью векторных часов, а затем решена с помощью более громоздких матричных часов?
2 ответа
В среде возможной согласованности все сообщения, когда-либо созданные системой, должны храниться до тех пор, пока каждый узел не получит сообщение (== возможная согласованность). Но вы не хотите хранить сообщения вечно, поэтому у вас должен быть способ определить, какие сообщения были получены всеми узлами и могут быть удалены, поэтому вы используете матричные часы.
Матричные часы представляют собой список векторных часов, поэтому вы знаете текущее состояние каждого узла в системе. Исходя из этого, вы можете узнать, какой пэр уже получил какие сообщения. Когда вы обмениваетесь сообщениями с другим узлом в системе, вы сравниваете часы матрицы и всегда помните самые высокие значения для каждого узла. После этого вы можете удалить сообщения, которые были отправлены ранее, потому что узел уже должен был их получить.
Это очень краткое описание протокола TSAE (антиэнтропийная метка времени). Вы можете узнать больше об этом в диссертационном проекте Ричарда Эндрю Голдинга (Richard Andrew Golding) с 1992 года ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.7385&rep=rep1&type=pdf групповом общении и членстве в группе с плохой согласованностью. pdf) начиная с главы 5.
Различия между часами Лампорта (скалярными логическими часами, в вашем термине), векторными часами и матричными часами заключаются в том, что они представляют разные уровни знаний.
Для векторных часов $vt_i[1 \ldots n]$ на сайте $ i $ запись $vt_i[k]$ представляет знания, которые сайт $S_i$ имеет о сайте $S_k$. Знание имеет вид "$i$ знает $ k $, что $\ldots$".
Для матричных часов $mt_i[1 \ldots n, 1 \ldots n]$ на сайте $S_i$, запись $mt_i[k,l]$ представляет знание, которое сайт $S_i$ о знании $ S_k $ о сайт $S_l$. Знание здесь в форме "$i$ знает, что $ k $ знает, что $ l $, что $\ldots$".
Интуитивно, мы можем делать больше вещей с большим количеством знаний.
Следующее описание в основном цитируется из [1]:
Векторные и матричные часы широко используются в асинхронных распределенных системах передачи сообщений.
Некоторыми примерами областей, в которых используются векторные часы, являются контрольные точки, каузальная память, поддержание согласованности реплицированных файлов, глобальный снимок, глобальное приближение времени, обнаружение завершения, ограниченная многозаписная конструкция общих переменных, взаимное исключение и отладка (обнаружение предикатов).
Некоторые примерные области, в которых используются матричные часы, разрабатывают отказоустойчивые протоколы и протоколы распределенных баз данных, включая протоколы для отбрасывания устаревшей информации в распределенных базах данных, а также протоколы для решения проблем реплицированного журнала и реплицированного словаря.
Для матричных часов мы заметили, что $min_k(mt_i[k,i]) \ge t$ означает, что сайт $S_i$ знает, что каждый другой сайт $ k $ знает свое продвижение до своего локального времени $t$.
Именно это свойство позволяет сайту больше не отправлять информацию с местным временем $\le t$ или отбрасывать устаревшую информацию.
[1] Параллельное знание и абстракции логических часов Ajay D. Kshemkalyani 2000