The problem
On the path A–B–C, choose B alone or choose A and C together. Either choice has no linked chosen pair, and every unchosen node has a chosen neighbor. Can every network make these choices in logarithmically many neighbor-to-neighbor communication rounds, without randomness?[1]
Can processors connected by a network agree on a nonconflicting choice that reaches every node through a neighbor, in logarithmically many rounds without randomness? On A–B–C, {B} and {A,C} both qualify. The first has fewer chosen nodes, showing that maximal independent set means no further vertex can be added, not that the set is largest.
The deterministic LOCAL target is worst-case synchronous rounds for every n-node simple graph and every assignment of distinct identifiers from a polynomial-size range. Nodes know n; each outputs its own membership. Messages may be arbitrarily large and local computation unlimited, but in one round information crosses only one edge.[1]
Scope
All finite simple undirected n-node graphs in the classical synchronous LOCAL model: distinct polynomial-range node identifiers, unbounded messages and local computation, and knowledge of n.
What remains open
General deterministic methods exist but have slower guarantees than logarithmically many rounds. Randomized algorithms can meet that round scale; faster methods under graph restrictions do not supply the deterministic guarantee for every graph.[1] [2]
General deterministic algorithms improve the round bound but do not reach the requested logarithmic guarantee. Randomized logarithmic-round results and faster results for restricted graph families do not remove that gap. Even unlimited message size does not let information cross many edges in a single round.[1] [2]
Why it matters
The chosen nodes provide a nonconflicting set that reaches every other node through a neighbor. A central procedure can choose them one by one, but network processors have to coordinate from messages that travel locally. This makes the task a basic test of how much global organization can be built from nearby information.[1]
The membership conditions are local: adjacent chosen nodes conflict, and every unchosen node must have a chosen neighbor. Producing a compatible choice across the whole graph nevertheless requires coordination. After rounds, a node can learn only about nodes at distance at most , even with unlimited messages. MIS connects these nearby correctness conditions with the global organization needed to construct them. Network decompositions provide one way to organize that work; the deterministic target tests how much communication is needed without random choices, for every graph and legal identifier assignment.[1]
Definitions
3 terms
maximal independent set
A vertex set with no edge inside it, to which no other vertex can be added without creating such an edge. Equivalently, every unselected vertex has a selected neighbor. Maximal need not mean largest.[1]
LOCAL
A synchronous distributed model with one processor per graph vertex and communication along graph edges. Message sizes and local computation are unrestricted, but each round moves information only one edge farther.[1]
deterministic
Using no random choices. For a fixed graph, identifier assignment and initial information, the processors’ actions are fixed by the algorithm.[1]
Sources
- Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
Notes on Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
FOCS 2024 paper defines LOCAL and proves improved deterministic MIS rounds.
- Faster Distributed Δ-Coloring via a Reduction to MIS
Notes on Faster Distributed Δ-Coloring via a Reduction to MIS
Published SODA 2026 paper retains the general MIS gap and links improvements to distributed coloring.