Логические часы Лампорта — различия между версиями
| Строка 1: | Строка 1: | ||
[[Категория: Параллельное программирование]] | [[Категория: Параллельное программирование]] | ||
| − | '''Логическими часами Лампорта''' называется | + | '''Логическими часами Лампорта''' называется функция из множества событий распределенного вычисления (внутреннее событие, событие отправки сообщения и событие приема сообщения) в множество неотрицательных целых чисел. |
Часы Лампорта присваивают каждому событию единственное число, монотонно увеличивая счётчик каждого процесса согласно следующим правилам: | Часы Лампорта присваивают каждому событию единственное число, монотонно увеличивая счётчик каждого процесса согласно следующим правилам: | ||
* счётчик увеличивается перед каждым внутренним событием процесса; | * счётчик увеличивается перед каждым внутренним событием процесса; | ||
| − | * при отправке сообщения значение счётчика прикрепляется к сообщению; | + | * при отправке сообщения значение счётчика увеличивается и прикрепляется к сообщению; |
* при получении сообщения значение счётчика процесса-получателя выставляется в максимум текущего и полученного значения и увеличивается на 1. | * при получении сообщения значение счётчика процесса-получателя выставляется в максимум текущего и полученного значения и увеличивается на 1. | ||
Версия 15:12, 23 февраля 2018
Логическими часами Лампорта называется функция из множества событий распределенного вычисления (внутреннее событие, событие отправки сообщения и событие приема сообщения) в множество неотрицательных целых чисел.
Часы Лампорта присваивают каждому событию единственное число, монотонно увеличивая счётчик каждого процесса согласно следующим правилам:
- счётчик увеличивается перед каждым внутренним событием процесса;
- при отправке сообщения значение счётчика увеличивается и прикрепляется к сообщению;
- при получении сообщения значение счётчика процесса-получателя выставляется в максимум текущего и полученного значения и увеличивается на 1.
Значением вышеупомянутой целочисленной функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что логическое время события не уникально (уникально только в рамках своего потока).
Оказывается, что если в распределенной системе ввести частичный порядок предшествования на событиях, то имеет место следующее утверждение:
- Если a предшествует b, то логическое время часов Лампорта события a меньше логического времени события b (обратное, вообще говоря, не верно).
