Dynamic Networks of Finite State Machines

Based on this notion of confinement, we propose a new metric for measuring the dynamic changes recovery performance in distributed network algorithms operating under the Stone Age model (Emek and Wattenhofer, PODC 2013), where the class of dynamic topology changes we consider includes inserting/deleting an edge, deleting a node together with its incident edges, and inserting a new isolated node. Our main technical contribution is a distributed algorithm for maximal independent set (MIS) in synchronous networks subject to these topology changes that performs well in terms of the aforementioned new metric. Specifically, our algorithm guarantees that nodes which do not experience a topology change in their immediate vicinity are not affected and that all surviving nodes (including the affected ones) perform \(\mathcal {O}((C + 1) \log ^{2} n)\) computationally-meaningful steps, where C is the number of topology changes; in other words, each surviving node performs \(\mathcal {O}(\log ^{2} n)\) steps when amortized over the number of topology changes. This is accompanied by a simple example demonstrating that the linear dependency on C cannot be avoided.