Изменения

'''Алгоритм СкринаСкина''' полного <ref>https://doi.org/10.1109/TSE.1983.236608</ref> для организации [[Общий порядок сообщений|общего порядка сообщений]]. Лучше, чем [[Алгоритм Лампорта]], потому что для multicast сообщений общается только с получателями, а не со всеми процессами системы. Используются [[Логические часы Лампорта|логические часы Лампорта]].Ниже алгоритм расписан чуть подробнее, чем в Garg и на лекции, но вроде всё ещё верно. У каждого процесса есть очередь принятых необработанных multicast сообщений.Каждое сообщение имеет временну́ю метку и флаг — финализирована ли метка. # Инициатор отправляет сообщение и своё время(''предварительное время сообщения'') всем получателям# При приеме сообщения процесс помечает запоминает сообщение со временем в очередь (как недоставленное нефинализированное) и отправляет свое время инициатору# Когда инициатору вернулись все сообщенияподтверждения, он выбирает максимальное время из них и снова отправляет сообщение (уже финальную версию)со финализированным временем# При приеме финального сообщения Получатель может обработать сообщение, если оно помечается помечено как доставленное финальное и доставляется получателю, если оно имеет минимальное время среди всех известных получателю сообщений (и финальных, и нефинальных; иначе может получиться, что финализация сообщений произойдёт в разном порядке у разных получателей и нарушится общий порядок) Полный порядок задается финальными временными метками. Финальные метки нужны, чтобы как-то зависеть от времени получателей.Доказательство на лекции и в очереди Gaarg не приводилось. Итого $3(k-1)$ сообщенийна каждый multicast на $k$ процессов (не обсуждалось на лекции, но вроде так).