The problem of maintaining a maximal independent set (MIS) in a dynamic graph has received growing attention in recent years. In STOC'18, Assadi et al. presented a distributed algorithm for maintaining an MIS with O(1) ( amortized) round complexity and O(m^{3/4\left(\log^2 n}\right) \left(\right)  ]  Assadi et al. is deterministic; to the best of our knowledge, the state-of-the-art distributed algorithm for this problem with a message complexity of o  (m^{3/4}) incurs a round complexity of \Omega(m^{1/3 (m^{2/3) and an amortized round complexityof }%DIFDELCMD < \tilde{O}(1) %%% under fully dynamic edge updates in the CONGEST model, where%DIFDELCMD < \tilde{O}%%% (\cdot) suppresses polylogarithmic factors. 
The field of dynamic graph algorithms aims at achieving a thorough understanding of real-world networks whose topology evolves with time. Traditionally, the focus has been on the classic sequential, centralized setting where the main quality measure of an algorithm is its update time, i.e. the time needed to restore the solution after each update. While real-life networks are very often distributed across multiple machines, the fundamental question of finding efficient dynamic, distributed graph algorithms received little attention to date. The goal in this setting is to optimize both the round and message complexities incurred per update step, ideally achieving a message complexity that matches the centralized update time in O(1) ( perhaps amortized) rounds. Toward initiating a systematic study of dynamic, distributed algorithms, we study some of the most central symmetry-breaking problems: maximal independent set (MIS), maximal matching/(approx-) maximum cardinality matching (MM/MCM), and (\Delta + 1)-vertex coloring. This paper focuses on dynamic, distributed algorithms that are deterministic, and in particular -- robust against an adaptive adversary. Most of our focus is on the MIS algorithm, which achieves O\left(m^{2/3\log^2 n}\right) amortized messages in O\left(\log^2 n\right) amortized rounds in the Congest model. Notably, the amortized message complexity of our algorithm matches the amortized update time of the best-known deterministic centralized MIS algorithm by Gupta and Khan SOSA'21] up to a polylog n factor. The previous best deterministic distributed MIS algorithm, by Assadi et al. STOC'18 , uses O (m^{3/4}) ) and an amortized round complexityof }%DIFDELCMD < \tilde{O}(1) %%% %DIFDELCMD < \tilde{O}%%% amortized messages in O(1) amortized rounds, i.e., we achieve a polynomial improvement in the message complexity by a polylog n increase to the round complexity; moreover, the algorithm of Assadi et al. makes an implicit assumption that the ...
R
problem of maintaining a maximal independent set (MIS) in a dynamic graph has received growing attention in recent years. In STOC'18, Assadi et al. presented a distributed algorithm for maintaining an MIS with
field of dynamic graph algorithms aims at achieving a thorough understanding of real-world networks whose topology evolves with time. Traditionally, the focus has been on the classic sequential, centralized setting where the main quality measure of an algorithm is its update time, i.e. the time needed to restore the solution after each update. While real-life networks are very often distributed across multiple machines, the fundamental question of finding efficient dynamic, distributed graph algorithms received little attention to date. The goal in this setting is to optimize both the round and message complexities incurred per update step, ideally achieving a message complexity that matches the centralized update time in
R
amortized) round complexity and O(m^{3/4
perhaps amortized) rounds. Toward initiating a systematic study of dynamic, distributed algorithms, we study some of the most central symmetry-breaking problems: maximal independent set (MIS), maximal matching/(approx-) maximum cardinality matching (MM/MCM), and (\Delta + 1)-vertex coloring. This paper focuses on dynamic, distributed algorithms that are deterministic, and in particular -- robust against an adaptive adversary. Most of our focus is on the MIS algorithm, which achieves O
A
m^{2/3
A
amortized messages in O
A
\log^2 n
A
amortized rounds in the Congest model. Notably, the amortized message complexity of our algorithm matches the amortized update time of the best-known deterministic centralized MIS algorithm by Gupta and Khan
A
SOSA'21
A
up to a polylog n factor. The previous best deterministic distributed MIS algorithm, by
R
is deterministic; to the best of our knowledge, the state-of-the-art distributed algorithm for this problem with a message complexity of o
STOC'18
A
, uses O
D
incurs a round complexity of \Omega(m^{1/3
D
(m^{2/3
D
under fully dynamic edge updates in the CONGEST model, where
R
(\cdot) suppresses polylogarithmic factors.
amortized messages in O(1) amortized rounds, i.e., we achieve a polynomial improvement in the message complexity by a polylog n increase to the round complexity; moreover, the algorithm of Assadi et al. makes an implicit assumption that the
A
...