commit ea89631a6f0280767bdf94ae6c59389304a106cf
parent f812d8b97a155e262fe3236c0d2d931fa20a7564
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Mon, 6 Feb 2017 12:54:46 +0300
Sync p3.
Diffstat:
2 files changed, 19 insertions(+), 9 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -2402,15 +2402,15 @@ cite:tel2000introduction Тель определяет их как алгори
включение и выключение отдельных узлов не влияет на работу алгоритма.
Подход к динамическому выбору главного узла, исследованный в данной работе, не
-использует волновые алгоритмы, а значит не требует опроса кворума узлов для
-выбора лидера. Вместо этого каждый узел кластера составляет список других узлов
-подсети, в которой он находится, и простым алгоритмом преобразует список в
-/древовидную иерархию/ с заданным значением ветвления (максимальным
-количеством подчиненных вершин). Затем узел определяет уровень иерархии, на
-котором он находится и пытается соединиться с вышестоящими узлами, чтобы стать
-их подчиненным. Сначала он проверяет близко расположенные к нему узлы, а потом
-все остальные узлы вплоть до вершины иерархии. Если вышестоящих узлов нет или с
-ними невозможно соединиться, то этот узел становится главным.
+использует волновые алгоритмы, а значит не требует опроса всех узлов кластера
+для выбора лидера. Вместо этого каждый узел кластера нумерует все узлы подсети,
+в которой он находится, и преобразует список в /древовидную иерархию/ с заданным
+максимальным значением ветвления (максимальным количеством подчиненных вершин).
+Затем узел определяет свой уровень иерархии и пытается соединиться с
+вышестоящими узлами, чтобы стать их подчиненным. Сначала он проверяет близко
+расположенные к нему узлы, а потом все остальные узлы вплоть до вершины
+иерархии. Если вышестоящих узлов нет или с ними невозможно соединиться, то узел
+сам становится главой иерархии.
Древовидная иерархия узлов подсети определяет отношение строгого порядка на
множестве всех узлов кластера. С технической точки зрения любая функция может
diff --git a/phd-diss.org b/phd-diss.org
@@ -2255,6 +2255,16 @@ algorithm. For a distributed system this means that wave algorithms work for
computer clusters with dynamically changing number of nodes, and the algorithm
is unaffected by some nodes going on-line and off-line.
+The approach in the following work does not use wave algorithms, and hence does
+not require communicating with each node of the cluster to determine a leader.
+Instead, each node enumerates all nodes in the network it is part of, and
+converts this list to a /tree hierarchy/ with a user-defined maximal fan-out
+value (maximal number of subordinate nodes). Then the node determines its
+hierarchy level and tries to communicate with nodes from higher levels to become
+their subordinate. First, it checks the closest ones and then goes all the way
+to the top. If there is no top-level nodes or the node cannot connect to them,
+then the node itself becomes the principal of the hierarchy.
+
*** Fail over algorithm
**** Introduction.
Fault tolerance of data processing pipelines is one of the top concerns in
