Выбор лидера в асинхронном неориентированном дереве - PullRequest
Новая
       23

Выбор лидера в асинхронном неориентированном дереве

0 голосов
/ 06 января 2020

У меня есть асинхронное сетевое неориентированное дерево (V, E) с n = | V | процессы. Единственное, что я знаю для своей сети, - это то, что все процессы имеют уникальные идентификаторы (UID), они знают количество своих соседей, но не знают диаметр и размер сети. Я попытался построить алгоритм выбора лидера в такой сети следующим образом: 

  A convergecast of <leader> messages is initiated starting from the 
  leaves of the tree. 

  Each leaf node is initially enabled to send a <leader> message to 
  its unique neighbor. Any node that receives <leader> messages from 
  all but one of its neighbors is enabled to send an <leader> message 
  to its remaining neighbor.

  In the end,
    1. Some particular process receives <leader> messages along all
    of its channels before it has sent out an <leader> message
     the process at which the <leader> messages converge elects
    itself as the leader.

    2. <leader> messages are sent on some particular edge in both
    directions.
    the process with the largest pid among the processes that are
    adjacent to this edge elects itself as the leader.

Верна ли моя идея и завершается ли приведенный выше алгоритм, когда все процессы знают лидера?

1 Ответ

0 голосов
/ 11 января 2020

Ваш алгоритм верен, но имеет следующие ограничения:

  1. Узлы только теперь их следующий лидер, но не глобальный лидер. Я не знаю, является ли ваша цель, чтобы каждый узел знал глобального лидера или своего личного лидера .
  2. Глобальный лидер - это не обязательно процесс с наибольшим pid или узел root вашего дерева. Пример: допустим цепочку из 5 узлов со вторым узлом как root. Этот граф представляет собой дерево с первым и пятым узлами в виде листьев. Дайте узлу root самый большой pid. Ваш алгоритм выбирает третий узел цепочки в качестве глобального лидера.
  3. Ваш алгоритм на практике не детерминирован c: предположим, сбалансированное дерево. Предположим, что один из сотрудников отправляет сообщение лидера с задержкой (это может случиться на практике) Выбор глобального лидера зависит от задержки.
  4. Ваш алгоритм работает только для деревьев.

Я не знаю, являются ли эти ограничения проблемой для вас. Поскольку у меня недостаточно репутации, чтобы комментировать ваш вопрос, я также не могу спросить.

Правильность вашего алгоритма доказывается математической индукцией.

  1. Базовый случай : Дерево с одним узлом Очевидно, ваш алгоритм верен.

  2. Шаг индукции: добавьте узел в дерево. Существует два случая:

    a) Новый узел подключен к узлу, который ранее не был листом.

    b) Новый узел подключен к узлу, который ранее был листом.

    Нетрудно доказать, что выходные данные алгоритма верны в обоих случаях. Таким образом, алгоритм корректен для всех деревьев.

...