Алгоритм избрания лидера для ориентированного гиперкуба

Question

Я застрял с некоторыми проблемами, где я должен разработать алгоритм лидера для ориентированного гиперкуба. Это должно быть сделано с использованием турнира с рядом раундов, равных измерению D гиперкуба. На каждом этапе D с 1 <= D <D двух кандидатских лидеров соседних D-мерных гиперкубов должны соревноваться с одним кандидатом руководителя (D + 1) -мерного гиперкуба, который является объединением их соответствующих гиперкубов.

Answer 1

Прошло много времени, так как я изучал распределенные системы, но я надеюсь, что это немного поможет :)

Эта проблема: Лидерные выборы в сети с гиперкуб Только. В этой топологии каждый узел имеет ровно D соседи (где d - размер гиперкуба). Так как гиперкуб ориентирован, Узлы знают, какие из их ссылок соответствует каждому измерению. Кроме того, я предполагаю, что все узлы помечены каким-то уникальным идентификатором, как типично с такими проблемами.

Если я хорошо понимаю рекомендации вашего решения, алгоритм кажется простым: узел имеет именно d состояния. В каждом состоянии 1 <= D <= d общается со своим соседом вдоль оси D. Эта связь состоит из отправки его удостоверения личности наилучшего кандидата, оно знает (когда d = 1 это просто его собственный идентификатор), и сравнивая его с идентификатором, полученным со стороны свертчика. Теперь узел знает лучшее удостоверение личности подсуба по порядку D (определяется осями 1,2 ..., d) оно относится к. Таким образом, на шаге D все узлы знают о глобальном лучшем, и алгоритм завершается консенсусом.

Например, предположим следующую топологию (D = 2) и значения ID:

   (1)    (2)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (3)

Идентификаторы в скобках указывают на лучшие идентификаторы, известные каждому узлу.

Первая итерация (D = 1) работает вдоль горизонтальной оси и завершается следующим образом:

   (2)    (2)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (4)

Вторая (и последняя) итерация (D = 2) работает вдоль вертикальной оси и завершается следующим образом:

   (4)    (4)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (4)

Узел № 4 был выбран, как требуется (самый высокий идентификатор).

Сложность подсчета сообщений

Для каждого края в гиперкубе у нас именно 2 сообщения (одна на каждом направлении). Поскольку формула для количества ребер в гиперкубе измерения d представляет собой E = D * 2 ^ (D-1), у нас именно м = d * 2 ^ d сообщений. Чтобы вычислить сложность как функцию n (количество узлов), напомним, что n = 2 ^ d, поэтому m = n * log n.