commit e611e66d2253bb6598cee09d07ee12028fe19fad
parent db56d797a1bedd3b3ec7390bf35a4e75d23d9d87
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Thu, 23 Mar 2017 16:48:18 +0300
Discuss linear hierarchy transformation.
Diffstat:
1 file changed, 19 insertions(+), 4 deletions(-)
diff --git a/src/body.tex b/src/body.tex
@@ -366,6 +366,25 @@ linear search complexity is more efficient than maps and sets, because the
number of elements in them is small, and linear search takes less time than
fixed time hash-based lookup.
+Transmitting IP addresses of previous nodes is an optimisation over mapping to
+only linear hierarchies, that is hierarchies where only one subordinate is
+allowed at any given time point. For a hierarchy consisting of a principal
+kernel with multiple subordinates there is unique mapping that transforms it to
+linear hierarchy: the principal creates and sends to the pipeline only the
+first subordinate, after that the first subordinate creates and sends the
+second subordinate to the pipeline and so on. This approach is inefficient
+because creation of subordinates is sequential and each subordinate is created
+after sending the previous one to a cluster node. Moreover, each subordinate
+carries a copy of its parent to be able to proceed programme execution when the
+parent fails. Instead of transforming initial hierarchy to a linear one, one
+can copy IP addresses of all previously created subordinates along with the
+next subordinate. The number of copies may be adjusted in the programme or a
+configuration file. When principal kernel fails each subordinate determines
+alive subordinate kernel starting from the first address in the list. If such
+kernel is not found, execution proceeds on the current node. The sequence of IP
+addresses in the list implicitly forms linear hierarchy, which makes this
+optimisation equivalent to the transformation.
+
% Brainstorming results (various random thoughts).
There are two scenarios of failures. Failure of more than one node at a time
@@ -389,7 +408,3 @@ reconfigurable topology and to reduce the number of simultaneous connections.
This topology reduces the number of simultaneous connections, thus preventing
network overload. This topology is used to distribute the load from the current
node to its neighbours by simply iterating over all directly connected daemons.
-
-Transmitting IP addresses of previous nodes is an optimisation over mapping to
-only linear hierarchies, that is hierarchies where only one subordinate is
-allowed at any given point of time.
