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

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

2 голосов
/ 15 мая 2010

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

1 Ответ

4 голосов
/ 16 мая 2010

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

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

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

Например, предположим следующую топологию (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.

...