ACM Comm 2018 02 Elements of the Theory of Dynamic Networks (Notes)

"The Next Phase in the Digital Revolution" CACM February 2018

Elements of the Theory of Dynamic Networks by Othon Michail and Paul G. Spirakis, p.72-81

Elements of the Theory of Dynamic Networks

"The challenge of computing in a highly dynamic environment."
Computer networks change with time. These days more rapidly than ever. At some point fixed networks will be rare and dynamic networks, changing by the hour or minute, will be the norm.
MutantOS is a highly dynamic and unpredictable software network.

Ideas

1. Computer networks started out static and predictable. Just keeping them running was a victory.
2. Changes in static networks were predictable and could be accomplished at pace.
3. "We are rapidly approaching the era of dynamicity and of the highly unpredictable. A great variety of modern networked systems are highly dynamic both in space and time."
4. "Theory will continue sitting at the center of progress in our science and its necessity toward our understanding of dynamic networks is already evident."
5. "Many traditional approaches and measures for static networks are not adequate for dynamic networks. There is already strong evidence that there is room for the development of a rich theory."
6. "Despite the considerable recent progress discussed in this article, we do not yet really know how to compute in highly dynamic environments."
7. The new networks are dynamic and highly unpredictable.
8. This means new network designs must be highly dynamic in space and time.
9. A self-organizing network is described in Figure 2.
10. Problems in organizing ad hoc networks.
    1. How many nodes are there?
    2. Over what time frame?
    3. How to keep the message count and size down?
    4. Use a leader to coordinate organization or not?
       1. Elect or appoint the leader?
    5. When to end the network?
    6. Are nodes rejected from the network?
    7. How many nodes in what quantity and kind are needed?
11. The network must last only long enough to get the job done.
12. Can centralized computational problems be solved is a highly dynamic environment? Yes. Do we know how? nope.
13. Current research focuses on a model for a select dynamic network state. Since there are infinitely many states, the solutions they offer never satisfy.

References

1. Turing's Proof on the Entscheidungs Problem[1]
2. \( \textbf{P} \text{ vs. } \textbf{NP}\)
3. \( \textbf{NP}\text{-completeness}\)
4. Four-color Problem[2]
5. The Traveling Salesman Problem[3]
6. Primality Testing[4]
7. Lamport's Causality[5]
8. The FLP Impossibility of Distributed Consensus[6]
9. Existing Thinking is in Three Parts
   1. Population Protocols
   2. Powerful Dynamic Distributed Systems
   3. Temporal Graphs
10. Automata Soup - Analog for a dynamic network where nothing is known with any certainty at any moment.
11. In a dynamic network electing a leader to speed up calculations can cost more than having one node assume leadership.
12. "Semilinearity[7] is the price that we pay for minimality[8]: an amorphous system of computational entities that have only constant memory and that cannot infer a bound on the time it takes to hear from all the other entities."
13. Anonymity, the fact that nodes in the original model do not have and cannot ever obtain unique identifiers (ids), simply because there is not enough room in their memory to store them. Another way, there are not enough resources of any kind to assign a globally unique identifier to each node.
14. Lotka-Volterra Equations[9]
15. Menger's Theorem[10] States the maximum number of node-disjoint \(s-z\) paths is equal to the minimum number of nodes whose removal separates node \(s\) from node \(z\).

Figures

Internal Links

Parent Article: Reading Notes