Матричные часы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 1 промежуточная версия 1 участника)
(нет различий)

Текущая версия на 19:06, 4 сентября 2022

Матричные часы – это обобщение векторных часов.

В отличие от векторных часов:

  • Каждый процесс хранит вектор векторов (матрицу) целых чисел;
  • При передаче сообщения передается вся имеющаяся матрица;
  • В случае любого события, i-ый поток увеличивает на единицу свою компоненту матрицы, т.е M[i][i];
  • При приеме сообщения для всех строк, кроме строки, соответствующей номеру получившего потока (myId), берется покомпонентный максимум. А для M[myId][j] берется максимум из M[myId][j] и W[srcId][j], где W - матрица, которая пришла, srcId - номер потока, от которого пришла матрица W.

Используя матричные часы, мы можем оценить нижнюю границу того, что знает другой поток.

Кроме этого, матричные часы обладают всеми свойствами векторных часов, например, s -> t <=> s.M[s.p, x] < t.M[t.p, x] для любого х.