Dynamic Maximal Matching in Clique Networks

We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of n nodes is vertex-partitioned among k players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of edge insertions or deletions. We first show a lower bound of ω log k k2 log n rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of ω( k log n ) rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players. We also present a randomized algorithm that has an initialization time of O n k log n rounds, while achieving an update time that that is independent of n: In more detail, the update time is O k log k against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes O k log k rounds.