Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks
share
This paper provides a surprisingly simple method for obtaining fast (constant amortized time) deterministic distributed algorithms for a highly-dynamic setting, in which arbitrarily many edge changes may occur in each round. Among the implications of our results are deterministic algorithms that maintain solutions to many problems, including (degree+1)-coloring, maximal matching, maximal independent set and the seemingly unrelated problem of a 2-approximation for minimum weight vertex cover (2-MWVC). These significantly improve upon prior work in various aspects, such as having O(1) amortized round complexity, using message of logarithmic size only, handling arbitrarily many concurrent topology changes, being deterministic, having correctness guarantees for intermediate rounds, and more. The core of our work is in defining a subclass of locally-checkable labelings which we call locally-fixable labelings (LFLs). Very roughly speaking, these are labelings that allow a node to fix its neighborhood based solely on their old labels. We present a simple algorithm for LFLs with small labels, which handles multiple edge insertions/deletions while keeping the amortized round complexity at a small constant. We then extend it, for specific tasks, to handle the insertion and deletion of nodes. Moreover, we show that the same approach can also fix labeling with large labels, given that they can be made to behave as small labels.
READ FULL TEXT