Synchronization in Anonymous Networks Under Continuous Dynamics

This thesis develops a synchronizer for non-synchronous dynamic networks under minimal assumptions. Our model allows continuous topological changes without any guarantee of eventual global or partial stabilization and assumes that nodes are anonymous. The resulting construction, named the Continuous-Dynamics Synchronizer or κ-Synchronizer, reflects two key characteristics: the network remains continuously dynamic throughout execution, and computations are performed locally relative to each node’s current set of at most ∆ neighbors, where ∆ denotes the maximum degree observed. By limiting dependencies to immediate neighbors and tolerating arbitrary edge changes, the κ-Synchronizer provides a robust mechanism for achieving synchronization in highly dynamic distributed systems. This deterministic synchronizer is the first to enable nodes to simulate a dynamic network synchronous algorithm for executions in a semi-synchronous dynamic environment under a weakly-fair node activation scheduler, despite the absence of a global clock, node identifiers, persistent connectivity or any assumptions about the edge dynamics (in both the synchronous and semi-synchronous environments). The κ-Synchronizer operates with memory overhead at the nodes that is linear on the maximum node degree and logarithmic on the runtime of the underlying synchronous algorithm being simulated.
Beyond the construction of the synchronizer, the thesis establishes fundamental impossibility results for communication models in dynamic environments. It is shown that neither the classic pull model nor the classic push model is sufficient to implement a synchronizer under arbitrary edge dynamics. These results identify inherent limitations of conventional communication models and motivate the need for more structured atomic synchronization mechanisms in adversarially dynamic networks.