Я изучаю книгу Нэнси Линч по распределенным алгоритмам. Одна из проблем заключается в следующем:
Рассмотрите возможность изменения алгоритма HS, чтобы процессы отправляли токены только в одном направлении, а не в обоих.
(a) Покажите, что наиболее простая модификация алгоритма в тексте не приводит к O (n log n) сложности связи. Какова верхняя граница сложности общения?
(b) Добавьте немного большей хитрости к алгоритму, чтобы восстановить границу сложности O (n log n).
Алгоритм HS, на который он ссылается, - это обычный Хиршберг-Синклер алгоритм.
Моя проблема в том, что я не понимаю, как слишком модифицировать алгоритм для однонаправленных колец, также я не понимаю, я думаю, что алгоритмы HS имеют смысл в обоих направлениях! кто-нибудь может мне помочь решить проблему?