Nibbling Under a Random-Bit Budget

Coloring a graph in a distributed network is the canonical symmetry-breaking task: every node must pick a label different from all its neighbors, using only local communication. Two toolkits dominate. The first, iterative partial coloring (the "nibble"), colors only a small random fraction of the still-uncolored elements per round, permanently keeping the conflict-free choices and discarding collisions, so that the remaining problem stays statistically well-behaved until it is small enough to finish off. The second, distributed symmetry breaking, studies how a network of completely identical, anonymous processors — no identifiers, no MAC addresses — can nevertheless reach an asymmetric configuration, which is provably impossible deterministically. Randomness is the only symmetry breaker such a network has, and in bandwidth-limited and wireless settings random bits are not free: they are the same currency as communication itself.

Yet the entire nibble literature treats randomness as an inexhaustible well. Every round, every uncolored element draws a fresh tentative color uniformly from a palette of size $\Theta(\Delta)$ (the maximum degree), costing $\Theta(\log \Delta)$ fresh random bits per node per round, over $\Theta(\log n)$ rounds — a total of $\Theta(\log \Delta \cdot \log n)$ bits per node. Nobody, to my knowledge, has asked the obvious quantitative question: how much of this entropy is actually load-bearing? This proposal conjectures that very little is, precisely because the nibble's defining feature — colliding tentative choices are simply purged and retried — makes it structurally tolerant of imperfect randomness, unlike naive parallel recoloring which provably collapses. We will build and analyze a pseudorandom nibble: the same cautious, fractional-commitment coloring loop, driven by weak (limited-independence) random sources, and characterize the three-way tradeoff between the per-node random-bit budget, the degree threshold at which the invariant holds, and the round complexity.

Core Claim

The classical nibble of Near-Optimal, Distributed Edge Colouring via the Nibble Method needs $\Theta(\log \Delta)$ fresh bits per node per round. We claim the per-round entropy can be cut to a short seed of $s = O(k \log \Delta)$ bits expanded by a $k$-wise independent hash family, with $k$ a small parameter (constant or polylogarithmic), while preserving the quasi-random invariant up to a constant-factor slowdown in rounds:

$$\underbrace{\Theta(\log \Delta \cdot \log n)}_{\text{classical total bits per node}} \;\longrightarrow\; O(k \log \Delta), \qquad T = O(\log n) \text{ for } \Delta = \Omega(k \log^{1+\delta} n).$$

The intuition is that the martingale analysis of the nibble needs concentration of aggregate quantities (palette shrinkage, degree decay) around their means, and $k$-wise independence with small $k$ suffices for coarse concentration of sums of many weakly-correlated indicator variables; individual violations cost extra rounds, not incorrectness, because conflicts are discarded. Whether this intuition survives a real Freedman-style analysis with bounded independence is exactly the scientific bet, and we design the program so that a negative answer still yields a published-quality characterization of the tradeoff curve.

Background and What Is Missing

Three lines of work set the stage. The distributed nibble itself is due to Near-Optimal, Distributed Edge Colouring via the Nibble Method, which proves that $(1+\lambda)\Delta$ edge coloring takes $O(\log n)$ rounds when $\Delta = \Omega(\log^{1+\delta} n)$; its robustness across settings — online under random arrivals in Online Edge Coloring Algorithms via the Nibble Method and dynamic in Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time — motivates our belief that the paradigm has unexplored slack, but none of these works meters randomness at all.

The randomness-metering literature exists but only for other problems. What Is the Minimum Number of Random Bits Required for Computability and Efficiency in Anonymous Networks? shows leader election on general graphs needs just one random bit per node (its TokenID algorithm) with a matching $\Omega(n)$-bit lower bound for cliques; however, its time and message complexities are large polynomials in $n$, and it assigns identifiers rather than coloring. That paper supplies our motivating setting and the technique of entropy recycling across rounds; it does not touch partial coloring, quasi-random invariants, or polylogarithmic time.

Finally, shattering-based symmetry breaking constrains the design space. The Locality of Distributed Symmetry Breaking shatters the graph into small components and finishes them with deterministic algorithms, which is why the whole two-phase architecture presupposes unique identifiers — and why it cannot run in anonymous networks, where deterministic symmetry breaking is impossible (Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus, On the Feasibility of Distributed Constraint Satisfaction). Distributed (Δ +1)-Coloring in Sublogarithmic Rounds pushed coloring to $O(\sqrt{\log \Delta}) + 2^{O(\sqrt{\log \log n})}$ rounds in the LOCAL model but likewise consumes unbounded randomness. One existing result gives encouraging evidence for our conjecture: Palette Sparsification Beyond (Δ+1) Vertex Coloring shows that restricting each vertex's random palette to a tiny sampled subset preserves colorability — entropy per choice can be slashed without breaking the method. And Distributed Symmetry Breaking on Power Graphs via Sparsification shows $k$-wise independent hashing is usable inside CONGEST-scale distributed algorithms, though for deterministic ruling sets on power graphs rather than for coloring or for randomness accounting.

Research Program

The program has three parts. First, algorithm design: a nibble variant where each node draws a one-time seed of $s$ bits, and in every round its tentative color is a hash of (seed, round index, palette state) from a shared $k$-wise independent family; the conflict-purging loop is unchanged. Seeds may be locally derived, so no identifiers or global coordination are needed, which is what makes the scheme anonymous-network-compatible. Phase II, once degrees drop below the nibble's working threshold, is a randomized conflict-resolution cleanup in the spirit of the coin-flip withdrawal of Self-stabilization and Byzantine Tolerance for Maximal Independent Set — deliberately randomized rather than deterministic, because in anonymous networks only randomized completion is possible at all.

Second, analysis: redo the Freedman-style martingale accounting of Dubhashi et al. under $k$-wise independence, tracking how the degree threshold inflates with $k$ and how per-round invariant violations convert into extra rounds rather than failure. The honest risk is that full independence turns out necessary for the martingale to close; in that case the deliverable becomes a lower-bound-style separation — that the nibble's randomness cannot be compressed below $\omega(\log \Delta)$-strength independence without exiting polylogarithmic rounds — which is itself an unclaimed result.

Third, an empirical study of whether the quasi-random invariant survives weak randomness in practice, on graphs far below and above the theoretical threshold, since the theory is asymptotic and real instances sit in exactly the regime ($\Delta$ = tens to thousands) where it says nothing.

Proposed Experiments

We will build a synchronous round-based simulator implementing the nibble with pluggable randomness sources (true uniform, $k$-wise independent for swept $k \in \{2, 4, \dots\}$). Graph families: random $\Delta$-regular graphs with $\Delta$ swept from 5 to $n^{0.9}$ to map the empirical degree threshold; complete graphs $K_n$, the worst case for uncoordinated parallelism; the COLOR benchmark collection (Mycielski, Queen, jean, homer) and the citation graphs Cora, Citeseer, and Pubmed as used in Rethinking Graph Neural Networks for Graph Coloring; and that paper's Layout dataset of 35,158 circuit-layout graphs under a 3-coloring constraint as an extreme low-palette stress test. Metrics: rounds to a conflict-free coloring, colors consumed, random bits consumed per node, and the empirical variance of the palette-to-degree ratio (the quasi-random invariant measured directly, which is the novel instrumentation here). For wall-clock context on Layout we cite the only reported numbers in our corpus: the Graph Discrimination Network of Rethinking Graph Neural Networks for Graph Coloring reports a solved ratio of 0.982 and a runtime of 5.84 seconds, versus 82,301 seconds for Tabucol and 133,285 seconds for HybridEA; our distributed round counts are a different axis, and no reported result found on Lacuna for empirical round counts of any distributed nibble algorithm, so our simulator measurements will be the first data points of that kind.

Baselines

The do-nothing reference point is uncoordinated parallel recoloring: every conflicted node picks a fresh uniform color each round with no fractional-commitment discipline. An Optimal Decentralized (Δ+ 1)-Coloring Algorithm proves the sequential version of this is optimal ($O(n \log \Delta)$ steps) but the naive parallel version takes exponential time on complete graphs, so this baseline is expected to diverge on $K_n$; merely terminating in $O(\log n)$ rounds there beats it. The strongest existing competitor is the full-randomness distributed nibble of Near-Optimal, Distributed Edge Colouring via the Nibble Method, with the $O(\sqrt{\log \Delta}) + 2^{O(\sqrt{\sqrt{\log \log n}})}$-style vertex coloring of Distributed (Δ +1)-Coloring in Sublogarithmic Rounds as a second reference for $(\Delta+1)$ vertex coloring; both will run in the same simulator on the same graphs, with the same tuning budget (an $\epsilon$-fraction sweep per method, same round cap, same conflict-resolution rule), so the comparison isolates the randomness source. Beating them means staying within a constant factor of their rounds and colors while consuming at most $O(\log \Delta)$ total seed bits per node, and, secondarily, completing on instances below the degree threshold where the full nibble's measured invariant visibly degrades. The key ablation runs our exact algorithm twice, once with true uniform draws and once with $k$-wise independent draws at matched parameters; any gap in rounds or invariant variance is attributable solely to the pseudorandomness, which is the single ingredient the proposal stands on. As an architectural baseline we also run shattering-style two-phase coloring with a randomized (identifier-free) cleanup, to test whether our contribution is the randomness budget rather than anonymity per se.

Why not just…?

Why not just use full independence, since random bits are cheap? In the LOCAL model with unique identifiers, they are — and there our proposal would be pointless. But in the anonymous broadcast and CONGEST regimes that motivate the symmetry-breaking literature (What Is the Minimum Number of Random Bits Required for Computability and Efficiency in Anonymous Networks?, Distributed Symmetry Breaking on Power Graphs via Sparsification), bits are the communication currency and entropy generation has a real cost; a one-time $O(\log \Delta)$-bit seed that fits in a single CONGEST message is categorically cheaper than $\Theta(\log \Delta)$ fresh bits per round for $\Theta(\log n)$ rounds. The empirical sweep over $k$ will also settle whether the saving is real or an artifact of asymptotic theory: if rounds blow up unless $k = \Theta(\log n)$, the idea dies and we report the separation.

Why not just assign identifiers with one random bit per node and then run standard algorithms? This is the TokenID route of What Is the Minimum Number of Random Bits Required for Computability and Efficiency in Anonymous Networks?, and it is randomness-optimal; but the authors themselves state its time and message complexities are large polynomials in $n$, which destroys the $O(\log n)$-round regime the nibble lives in. Our target is simultaneous near-optimality in time and randomness, and our simulator will time both approaches head-to-head so the tradeoff is measured rather than asserted. If one only cares about randomness and tolerates polynomial time, TokenID genuinely wins, and we will say so plainly.

Why not just shatter the graph and finish the pieces with a randomized, identifier-free cleanup? This is the most serious alternative, because The Locality of Distributed Symmetry Breaking plus a randomized post-shattering phase plausibly already yields polylogarithmic-round coloring in anonymous networks with unbounded randomness. Our answer is that this solves the anonymity question but not the one we pose: it consumes the same unmetered $\Theta(\log \Delta)$ bits per round. We will implement it as an architectural baseline, and our contribution then reduces cleanly to the random-bit budget of whichever Phase I/Phase II primitive it uses — our pseudorandom nibble is exactly that primitive, so the two proposals compose rather than compete.

Why not just recolor everything in parallel each round? Because An Optimal Decentralized (Δ+ 1)-Coloring Algorithm proves the naive parallel version takes exponential time on complete graphs; our simulator will reproduce this divergence on $K_n$, which doubles as a sanity check on the implementation.

Why not just learn a coloring heuristic with a graph neural network? On the Layout benchmark, standard GNN architectures achieve a solved ratio of nearly 0 due to homophily bias, and the specialized GDN of Rethinking Graph Neural Networks for Graph Coloring needed a centralized ILP backend for zero-conflict solutions; these are centralized methods outside our distributed, per-node-compute setting, so they serve only as the wall-clock reference cited above.

Decisive Checks

The proposal succeeds if the analysis closes (round complexity preserved up to constants for $k = O(\mathrm{polylog})$ independence at a mildly inflated degree threshold) or fails informatively (a separation showing full independence is necessary). Empirically, the decisive measurement is the invariant-variance-vs-$k$ curve: if the palette-to-degree ratio stays concentrated for small $k$ on graphs far below the theoretical threshold, the pseudorandom nibble is real and the anonymous-network application follows; if concentration collapses sharply at small $k$, we will have mapped the true randomness requirement of the most widely reused randomized primitive in distributed graph algorithms — a number the field has never measured.