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

Question

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

Answer 1

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

Проблема:Leader election в сети с hypercube tolopogy. В этой топологии каждый узел имеет ровно 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.