Причинно-следственное упорядочение, логические часы, репликация конечного автомата: различия между версиями

Алгоритм требует, чтобы каждый процесс поддерживал собственную очередь запросов, и гарантирует, что очереди запросов разных процессов всегда остаются согласованными. Вначале все очереди запросов содержат по одному сообщению <math>(T_0, p_0, request) \;</math>, где <math>p_0 \;</math> – процесс, который содержит ресурс, а временная метка <math>T_0 \;</math> меньше исходного значения каждого экземпляра часов. Затем алгоритм работает следующим образом.

1. Когда процесс <math>p_i \;</math> запрашивает ресурс, он отправляет сообщение с запросом <math>(T_m, p_i, request) \;</math> всем остальным процессам и помещает его в свою очередь запросов.

2. Когда процесс <math>p_j \;</math> получает сообщение <math>(T_m, p_i, request) \;</math>, он помещает его в свою очередь запросов и направляет уведомление <math>(T_{m'}, p_j, ack) \;</math> процессу <math>p_i \;</math>.

3. Когда процесс <math>p_i \;</math> освобождает ресурс, он удаляет все экземпляры сообщений <math>( - , p_i, request) \;</math> из своей очереди и отправляет сообщение об освобождении ресурса <math>(T_{m'}, p_i, release) \;</math> всем остальным процессам.

4. Когда процесс <math>p_j \;</math> получает сообщение об освобождении ресурса от процесса <math>p_i \;</math>, он удаляет все экземпляры сообщений <math>(T_m, p_i, request) \;</math> из своей очереди и отправляет процессу <math>p_i \;</math> уведомление, снабженное временной меткой.

5. Сообщения в очереди отсортированы согласно отношению полного упорядочения <math>\Rightarrow</math> из определения 4. Процесс <math>p_i \;</math> может использовать ресурс в случае, когда: (а) сообщение <math>(T_m, p_i, request) \;</math> оказывается первым в очереди, и (б) процесс <math>p_i \;</math> получил от всех остальных процессов сообщения с временными метками, большими, чем <math>T_m \;</math> (или равными ей – от любого процесса <math>p_j \;</math>, где <math>p_i \prec p_j \;</math>).