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

Question

Я застрял с некоторой проблемой, когда я должен разработать алгоритм выбора лидера для ориентированного гиперкуба. Это должно быть сделано с использованием турнира с числом раундов, равным измерению D гиперкуба. На каждом этапе d с 1 <= d

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), мы имеем точно M=D*2^D сообщений. Чтобы вычислить сложность как функцию от N (количество узлов), напомним, что N = 2^D, поэтому M=N*log N.