Матричные часы

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

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

• Каждый процесс хранит вектор векторов (матрицу) целых чисел;
• При передаче сообщения передается вся имеющаяся матрица;
• В случае любого события, 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] для любого х.