Source-linked AI summary
Beeping a Maximal Independent Set
Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
TL;DR
The paper studies MIS construction when nodes lack topology and network-size information and an adversary chooses wake-up times. The paper proves a local-convergence lower bound and analyzes MIS algorithms under four relaxed models: a size bound, wake-on-beep, sender-side collision detection, or synchronous clocks. With no graph information and adversarial wake-up, finding an MIS requires at least Ω( p n/ log n) rounds; four relaxed models yield MIS algorithms in O(log3 n) or O(log2 n) time.
Problem
The paper studies MIS construction when nodes lack topology and network-size information and an adversary chooses wake-up times.
Source: §1 · p. 2Method
The paper proves a local-convergence lower bound and analyzes MIS algorithms under four relaxed models: a size bound, wake-on-beep, sender-side collision detection, or synchronous clocks.
Source: §1 · p. 2Results
With no graph information and adversarial wake-up, finding an MIS requires at least Ω( p n/ log n) rounds; four relaxed models yield MIS algorithms in O(log3 n) or O(log2 n) time.
Source: §1 · p. 2Takeaways & Limitations
The upper-bound algorithms eventually compute a stable MIS with probability one, and the probability none has been computed by time t decreases exponentially in t.
Source: §1 · p. 2Without additional network information and with adversarial wake-up, local convergence requires at least polynomial time, even in a more powerful radio-network model.
Source: §4 · p. 4
Abstract
from arXiv · showhide
We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in O(log^3 n) time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in O(log^3 n) time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in O(log^2 n) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in O(log^2 n) time.
1 Introduction
The paper studies maximal independent set (MIS) construction in an anonymous beeping network and shows that adversarial wake-up creates a lower bound on local convergence. It then presents four model relaxations that permit polylogarithmic-time MIS algorithms.
1 Introduction
- MIS is a maximal set of pairwise non-neighboring nodes, with applications including wireless backbones, routing, clustering, and spanning-tree construction.These applications are especially relevant to radio sensor networks.Source: §1 · p. 1
- The beeping model lets nodes transmit a beep or listen for whether any neighbor beeps, using carrier sensing rather than message exchange.The paper notes that carrier sensing can use less energy and reach farther than regular message transmission.Source: §1 · pp. 1–2
- The paper also connects beep-based communication to biological signaling, where neighboring cells sense secreted proteins.The authors extend algorithms for this model, which is also used to describe biological processes.Source: §1 · p. 2
- Without topology information and with adversarial wake-up, local convergence to an MIS cannot be achieved in sub-polynomial time.The lower bound also holds in a more powerful radio network model with collision detection and arbitrary message sizes.Source: §1 · p. 2
- Four weaker models permit polylogarithmic-time MIS construction: a known polynomial size bound, wake-on-beep, wake-on-beep with sender-side collision detection, or synchronous clocks.Their stated running times are O(log^3 n), O(log^3 n), O(log^2 n), and O(log^2 n), respectively.Source: §1 · p. 2
2 Related Work
Prior MIS algorithms often rely on message passing, topology assumptions, or known network-size bounds. This paper situates its general-graph beeping approach among work on radio networks and carrier sensing.
2 Related Work
- Luby’s randomized MIS algorithm runs in O(log n) time in a standard message-passing model, while bounded-independence graphs admit O(log*n) rounds.The bounded-independence result covers unit disk and other geometric graphs.Source: §2 · p. 2
- Earlier radio-network MIS algorithms achieved O(log^9 n / log log n) and then O(log^2 n) time, but assumed geometric graphs and a known network-size upper bound.They also allow messages whose size depends on the network size.Source: §2 · pp. 2–3
- Carrier-sensing work includes an O(log n)-time MIS algorithm for bounded-independence graphs, assuming receiver-side collision detection, graph-growth knowledge, a network-size bound, and unique identifiers.Other cited work uses carrier sensing for coordination and for approximating a minimum dominating set in an SINR model.Source: §2 · p. 3
3 Model
The model is a synchronous graph of processes that initially sleep and wake under adversarial control. Participating nodes communicate only by beeping or listening, and the paper defines stability and MIS convergence for its algorithms.
3 Model
- The network is an arbitrary graph G = (V, E), where edges connect processes that can hear one another; d_G(u) is a node’s degree and d_max is the maximum degree.The neighborhood of u is denoted N_G(u).Source: §3 · p. 3
- All processes initially sleep, and an adversary chooses when each process wakes; G_t contains the processes participating in round t..Source: §3 · p. 3
- In each round, a participating process beeps or listens; a listener distinguishes silence from one or more beeps among participating neighbors.A beep conveys less information than a conventional one-bit message, which can distinguish no message, 1, and 0.Source: §3 · p. 3
- An MIS is an independent set to which no outside vertex can be added while preserving independence.Thus every vertex outside the set has a neighbor inside it.Source: §3 · p. 3
- A node is stable when it is in the MIS with inactive neighbors, or has a stable MIS neighbor; once stable, it stays stable.The algorithms eventually make all nodes stable with probability one, and the MIS-state nodes then describe an MIS.Source: §3 · p. 3
- The paper distinguishes computing a stable MIS after a period without new wakeups from locally converging, where each node irrevocably decides within a bounded time regardless of wakeups.The former requires high-probability correctness after T rounds and eventual correctness with probability one.Source: §3 · pp. 3–4
4 Lower Bound for Uniform Algorithms
Without graph information, adversarial wake-up prevents local MIS convergence in sub-polynomial time, even in a stronger message-broadcast model with collision detection. The section also shows that algorithms cannot safely terminate in every execution, motivating indefinite operation until a stable MIS is reached.
4 Lower Bound for Uniform Algorithms
- If nodes hearing only silence or collisions must decide within a bounded number of rounds, the adversary can arrange indistinguishable experiences that prevent a correct MIS decision.The proof first establishes that, for either fixed feedback pattern, a node either stays silent forever or beeps after a constant number of rounds with positive probability.Source: §4 · p. 4
- The lower bound requires polynomial time for local MIS convergence without a priori graph information, and applies even to local message broadcast with collision detection and arbitrary message sizes.The authors attribute the limitation to collisions and the requirement to decide before all nodes have woken up; they note it extends to minimal dominating set and coloring.Source: §4 · p. 4
- In Case 1, interconnected cliques let the adversary make the U-cliques hear collisions while preserving identical states, so some clique risks having either no MIS member or multiple members.The construction uses more U-cliques than C-cliques; after at most k−1 participation rounds, nodes in a U-clique have the same state.Source: §4 · pp. 4–5
- In Case 2, cliques U_j hear collisions for their first q rounds, making early decisions fail with high probability through either an uncovered clique or adjacent MIS members.The proof constructs the collision sequence inductively, then considers U_j for j in {q, …, k−2q}.Source: §4 · pp. 5–6
4.1 Termination Lower Bound
- The paper’s algorithms therefore run indefinitely for safety while eventually converging to a stable MIS; sender-side collision detection is an exception that permits termination after O(log^2 n) rounds.The stated termination exception is the algorithm in Section 6.Source: §4.1 · pp. 6–7
- A node cannot distinguish isolation from having one neighbor with certainty at any finite time, so no MIS algorithm can terminate correctly in every execution.On disjoint neighboring pairs, this uncertainty also yields an expected convergence time of at least log n/e.Source: §4.1 · p. 6
5 Using an Upper Bound on n
With a known upper bound N on network size, nodes can locally converge to an MIS in O(log^2 N log n) rounds; a polynomial bound yields O(log^3 n) rounds. The algorithm’s safety and convergence arguments establish a stable MIS, with additional guarantees for self-stabilization and crashes.
5 Using an Upper Bound on n
- The algorithm listens for c log^2 N rounds after waking or restarting, then competes through log N phases with increasing beep probabilities before claiming MIS status.A heard beep triggers a restart; a node that completes the phases beeps half the time and listens half the time in its MIS state.Source: §5 · p. 7
- O(log^2 N log n) rounds suffice for local convergence when nodes know an upper bound N on network size; polynomial N gives O(log^3 n) rounds.The theorem gives the O(log^2 N log n) bound, and the section states its polynomial-bound consequence.Source: §5 · p. 7
- Under adversarial crashes, Algorithm 1 still computes an MIS in O(log^2 N log n) rounds, but cannot locally converge to one.An inactive node whose only MIS neighbor crashes cannot always immediately join the MIS.Source: §5 · p. 7
- Neighboring nodes do not both join the MIS with high probability; if they do, almost surely one eventually becomes inactive.The algorithm is also described as self-stabilizing, and its guarantees are unaffected by arbitrary initial states and internal variables.Source: §5 · p. 7
- With high probability, each node is in the MIS or has an MIS neighbor after O(log^2 N log n) rounds.The proof uses an event every O(log^2 N) rounds and a constant probability of joining or becoming covered at each event; Lemma 5.2 states the resulting bound.Source: §5 · pp. 8–9
6 Wake-on-Beep and Sender-Side Collision Detection
With wake-on-beep and sender-side collision detection, the algorithm locally converges to an MIS in O(log^2 n) rounds without network-topology knowledge. Its analysis establishes safety and bounds convergence by repeated edge deletion.
6 Wake-on-Beep and Sender-Side Collision Detection
- Wake-up beeps propagate through the network, while three-round exchanges accommodate neighboring nodes waking up one round apart.A node joins the MIS after beeping without hearing a neighbor beep across the first exchange; it signals neighbors to terminate in the second.Source: §6 · p. 10
- Messages received in an exchange come from processes using the same probability, preserving the coherence needed by the safety proof.The proof extends this property to the second exchange; the safety proof relies on exchange coherence.Source: §6 · pp. 10–11
- At least half of graph edges are good, enabling the analysis to show that a phase deletes an expected constant fraction of edges.For a good node, the proof bounds expected deleted incident edges by Ω(d_v), then sums over good nodes.Source: §6 · p. 11
- O(log^2 n) rounds suffice for local MIS convergence with wake-on-beep and sender-side collision detection.The guarantee requires no knowledge of network topology, including its size.Source: §6 · pp. 10–11
- Each phase deletes a constant fraction of remaining edges with at least constant probability, yielding O(log n) successful phases.The proof combines this with O(log n) steps per later phase and fewer than O(log^2 n) steps before the phase counter reaches log n.Source: §6 · p. 11
7 Wake-on-Beep Without Sender-Side Collision Detection
The wake-on-beep algorithm removes sender-side collision detection while retaining local MIS convergence in O(log^3 n) rounds. It adds competition exchanges to resolve conflicts and preserves stability, though it cannot safely terminate.
7 Wake-on-Beep Without Sender-Side Collision Detection
- The algorithm adds competition exchanges proportional to the phase counter to resolve conflicts without sender-side collision detection.Active candidates continue participating; nodes that detect an MIS neighbor become inactive until a full exchange set passes without a beep.Source: §7 · pp. 11–12
- After reaching x ≥ log n, conflict resolution and subsequent MIS selection take O(log^3 n) rounds overall.The analysis uses O(log n) phases, each with O(log n) steps and O(log n) rounds per competition.Source: §7 · p. 12
- For x ≥ log n, a node in conflict remains in conflict after cx competition exchanges with probability at most 1/n^(c/3).Each exchange resolves a given conflict with probability at least 1/4, so the chance it persists through c log n exchanges is at most (3/4)^(c log n).Source: §7 · p. 12
- O(log^3 n) rounds suffice for local MIS convergence in the wake-on-beep model without sender-side collision detection.The algorithm cannot safely terminate at any point, though a computed MIS remains stable forever.Source: §7 · pp. 12–13
8 Synchronized Clocks
Synchronized clocks enable an MIS algorithm with O(log^2 n) rounds, without requiring a known network-size bound or synchronized starts. The algorithm synchronizes local priority comparisons and increases its priority-size estimate when ties or competing neighbors indicate it is too small.
8 Synchronized Clocks
- The algorithm simulates Luby’s permutation algorithm using random O(log n)-size priorities compared bit by bit with beeps.Nodes join when they have the highest priority among neighbors, and neighbors of an MIS node become inactive.Source: §8 · p. 13
- A Restart-Bit synchronizes priority comparisons and doubles the local estimate k when nodes detect a mismatch or insufficient priority size.The algorithm uses beep-triplets for restart, MIS signaling, and competition.Source: §8 · p. 13
- Synchronous clocks let Algorithm 4 solve MIS in O(log^2 n) rounds.The algorithm removes the need for an upper bound on n and a synchronized start.Source: §8 · p. 13
- With high probability, k remains O(log n) throughout execution.The analysis rules out a first node reaching an oversized k by bounding the probability of repeated competition without losing.Source: §8 · pp. 13–14
- A stable node emerges when its O(log n) neighborhood is well-behaved for Ω(log^2 n) rounds, and the MIS-bit preserves that stability.The locality argument relates the algorithm’s behavior to Luby’s algorithm; the resulting bound is O(log^2 n).Source: §8 · p. 14