Алгоритм Скина

Материал из Викиконспекты
Перейти к: навигация, поиск

Алгоритм Скина[1] для организации общего порядка сообщений. Лучше, чем Алгоритм Лампорта, потому что для multicast сообщений общается только с получателями, а не со всеми процессами системы.

Используются логические часы Лампорта. Ниже алгоритм расписан чуть подробнее, чем в Garg и на лекции, но вроде всё ещё верно.

  1. Инициатор отправляет сообщение и своё время (предварительное время сообщения) всем получателям
  2. При приеме сообщения процесс запоминает сообщение со времени и отправляет свое время инициатору
  3. Когда инициатору вернулись все сообщения, он выбирает максимальное время из них и снова отправляет сообщение со временем (уже финальное)
  4. Получатель обрабатывает сообщение, если оно помечено как финальное и имеет минимальное финальное время среди всех известных получателю сообщений (и финальных, и нефинальных; иначе может получиться, что финализация сообщений произойдёт в разном порядке у разных получателей и нарушится общий порядок)

Полный порядок задается финальными временными метками. Финальные метки нужны, чтобы как-то зависеть от времени получателей.

Доказательство на лекции и в Gaarg не приводилось.