Sebastian Daum
email: sdaum@cs.uni-freiburg.de

Fabian Kuhn
email: kuhn@cs.uni-freiburg.de

Tight Bounds for MIS in Multichannel Radio Networks

 in two ways. Mainly, we get rid of the polyloglog n factor in the running time and we thus obtain an asymptotically optimal multichannel radio network MIS algorithm. In addition, our new analysis allows to generalize the class of graphs from those with polynomially bounded local independence to graphs where the local independence is bounded by an arbitrary function of the neighborhood radius.

Introduction

In recent years there has been an increased interest in algorithms for shared spectrum networks [START_REF] Sherman | IEEE Standards Supporting Cognitive Radio and Networks, Dynamic Spectrum Access, and Coexistence[END_REF]. Nowadays, most modern wireless communication networks feature a multitude of communication frequencies [1, 2, 5]1 -and we can certainly expect this trend to continue.

In the light of this development, in the present paper, we settle the question of determining the optimal asymptotic time complexity of computing a maximal independent set (MIS) in the multichannel variant of the classic radio network model first introduced in [START_REF] Bar-Yehuda | On the Time-Complexity of Broadcast in Multi-Hop Radio Networks: An Exponential Gap Between Determinism and Randomization[END_REF][START_REF] Chlamtac | On Broadcasting in Radio Networks-Problem Analysis and Protocol Design[END_REF]. The task of constructing an MIS is one of the best studied problems in the area of large-scale wireless networks. On the one hand this is due to the fact that MIS (together with coloring problems) is one of the key problems to study the problem of symmetry breaking in large, decentralized systems. On the other hand an MIS provides a simple local clustering of the graph, which can be used as a building block for computing more enhanced organization structures in these networks such as, e.g., a communication backbone based on a connected dominating set [START_REF] Censor-Hillel | Structuring Unreliable Radio Networks[END_REF][START_REF] Ephremides | A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling[END_REF][START_REF] Wan | Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks[END_REF]. This is specifically relevant in the context of wireless mobile ad hoc networks or sensor networks, in which devices cannot rely on already existing infrastructure to organize themselves-devices need to compute a meaningful structure by themselves to coordinate their interactions.

Related Work. In [START_REF] Alon | A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem[END_REF][START_REF] Luby | A Simple Parallel Algorithm for the Maximal Independent Set Problem[END_REF] Alon et al. and Luby presented a simple and efficient randomized parallel algorithm to compute and MIS of a general graph. It is straightforward to a standard distributed message passing model and as a consequence, the algorithm soon became an archetype for many distributed MIS algorithms also in other-usually more limiting-settings. The model we assume here is an extension to the radio network model, for which an MIS algorithm with runtime O(log 2 n) has been presented in [START_REF] Moscibroda | Maximal independent sets in radio networks[END_REF] for the class of unit disk graphs (UDGs). This algorithm has been proven to be asymptotically optimal [11] even for more basic version of the problem known as the wake-up problem in single-hop radio networks. While the UDG restriction is well-known and popular, a more general variant known as growth-bounded graphs or bounded independence graphs that contains UDGs has also become the focus of quite some research, e.g., [START_REF] Kuhn | Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs[END_REF][START_REF] Schmid | Algorithmic models for sensor networks[END_REF][START_REF] Schneider | A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs[END_REF]. In particular, in [START_REF] Schneider | A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs[END_REF] it is shown that an MIS and many related structures can be compute in (asymptotically optimal) O(log * n) rounds in such graphs.

Much of the early algorithmic research on multichannel radio networks has focused on networks with faults assuming a malicious adversary that can jam up to t of the F available channels [10, 14-18, 20, 28, 29]. In addition, for fault-free networks, in [START_REF] Newport | Radio Network Lower Bounds Made Easy[END_REF] a series of lower bound proofs have been provided, which show that Ω(log 2 n/F +log n) rounds are needed to solve any problem which requires communication. In [START_REF] Daum | Leader Election in Shared Spectrum Networks[END_REF] a new technique (called heralding) to deal with congestion in multichannel radio networks has been established to solve leader election in single-hop networks in time asymptotically matching the lower bound of [START_REF] Newport | Radio Network Lower Bounds Made Easy[END_REF]. This technique has been extended in [START_REF] Daum | Efficient Symmetry Breaking in Multi-Channel Radio Networks[END_REF] and [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] to solve the problems of computing an approximate minimum dominating set and an MIS, respectively. Our research here is based on this work and in particular on the MIS algorithm of [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF]. Contributions. In radio network models, in almost all cases a restriction to the underlying graph model is being assumed. One of the most general ones are so-called α-bounded independence graphs, where α(r) is a function that limits the size of a maximum independent set in any r-neighborhood of the given graph. The MIS algorithm from [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] solves the MIS problem in time O(log 2 n/F + log n(log log n) d ) in such graphs for which α is bounded by polynomial of degree d. Here we get rid of the polyloglog factor and thus show how to close the gap to the lower bound from [START_REF] Newport | Radio Network Lower Bounds Made Easy[END_REF]. At the same time, we remove any restriction on the function α. We do so by adjusting the algorithm from [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF]-and though the change in the algorithm is relatively small, it leads to a significantly more involved analysis.

Preliminaries

Algorithm and analysis of this paper are based on [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] and on the complete version [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] of [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF]. In the paper, we try to be as self-contained as possible. However, due to lack of space, proofs are omitted and we focus on motivating and explaining the algorithms and the main ideas of the analysis. For a full, detailed version of the paper, we refer to [START_REF] Daum | Tight Bounds for MIS in Multichannel Radio Networks[END_REF]. Radio Network Model. We model the network as an n-node graph G = (V, E). We assume that n or a polynomial upper bound on n is known by all nodes. Nodes start out dormant and are awakened/activated by an adversary. While nodes do not have access to a global clock, communication is assumed to happen in synchronous time slots (rounds). The network comprises F communication channels. In each round each node can choose to operate on one channel, either by listening or broadcasting. A node that broadcasts does not receive any message in that round, and its signal reaches all neighbors that operate on the same channel. A node v listeing on some channel can decode an incoming message iff in the given round, exactly one of its neighbors broadcasts on the same channel. If two or more neighbors broadcast, their signals collide at v and v receives nothing, unable to detect this collision. A node can only operate on one channel in each round and therefore it does not learn anything about events on other channels. Notation. In our algorithm all nodes move between a finite set of states: W -waiting, D -decay, A -active, H -herald candidate, H -herald, L -leader candidate, L leader, M -MIS node, E -eliminated/dominated. We overload this notation to also indicate the set of nodes being in a certain state, e.g., A := {v ∈ V : v is in state A}. Since nodes change their states, in case of ambiguity, we write A r for the set of active nodes in round r. State changes always happen between rounds. We define V hf := A ∪ H ∪ L ∪ H ∪ L as the nodes in the so-called herald filter.

We use N (v) to denote the neighbors of v in G, while we use N k (v) to denote the set of nodes in distance at most k from v, including v itself. We also often write N S (u) or N k S (u) to abbreviate N (u)∩S or N k (u)∩S respectively, for some state S. For S ⊆ V we let N (S) := v∈S N (v). We call a node v alone or lonely, if N Vhf∪M (u) = ∅.

We say that an event A happens with high probability (w.h.p.), with decent probability, or with constant probability (w.c.p.), if it happens with probability at least 1 -n -c , 1 -log -c n, or Ω(1), respectively, where c is a constant that can be chosen arbitrarily large. By x y we denote that x > cy for a sufficiently large c > 1. Bounded Independence. In addition to the communication characteristics of the network, we require the network graph to be a bounded independence graph (BIG) [START_REF] Kuhn | Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs[END_REF][START_REF] Schmid | Algorithmic models for sensor networks[END_REF]. A graph G is called an α-bounded independence graph with independence function α : N → N, if for every node v. no independent set S of the subgraph of G induced by N d (v) exceeds cardinality α(d). Note that in particular, α does not depend on n and thus for every fixed d, α(d) is a constant. In [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF], α is required to be a polynomial, whereas in this paper, we put no restrictions on α. It can easily be verified that one can always upper bound the largest independent set of the subgraph induced by N d (v) by α(2) d and thus any independence function is always upper bounded by some exponential function. For simplicity we define a constant α := α(2) and we assume that all nodes know the value of α. Number of Channels. We assume that F = ω(1) as otherwise single channel algorithms achieve the same asymptotic time bounds. For F = ω(log n) we only actually use Θ(log n) channels since more channels do not lead to an additional asymptotic advantage. For ease of exposition we assume F = Ω(log log n) and refer to [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] for an explanation of how to adapt the algorithm for the case F = o(log log n). Maximal Independent Set. We say an algorithm computes an MIS in time T , if the following properties hold w.h.p. for each round r and node v (waking up in round r v ): (P1) v declares itself as either dominating (∈ M) or dominated (∈ E) before round r v + T and this decision is permanent.

(P2) If v is dominated in round r, then N (v) ∩ M r = ∅. (P3) If v is dominating in round r, then N (v) ∩ M r = ∅.
Detailed pseudo-code can be found in [START_REF] Daum | Tight Bounds for MIS in Multichannel Radio Networks[END_REF]. Here we only present pseudo-code for the core structure of our MIS algorithm (Algorithm 1).

Algorithm 1 HeraldMIS-core structure We first give a short summary of how the algorithm works including a summary of results or [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF]. The algorithm is divided into three stages, the decay filter (states W and D), the herald filter (states A, L , H , L and H), and decided nodes (states M and E). Nodes move forward within those stages-possibly omitting the herald filter-but never backwards. The decay filter is a powerful tool (which we use as a black box) that provides that over the full runtime of the algorithm the degree of the graph induced by nodes in the herald filter is bounded by O(log 3 n). In short, nodes first only listen for a while (W), then they start broadcasting on one out of Θ(F) random channels with probability 1/n (D), doubling this probability every O(log n/F) rounds. A node that broadcasts moves to the herald filter and a node that receives a message restarts in W. The decay filter is the same as in [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] and for a detailed description and analysis we refer to [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF]. Eliminated nodes (E) know that they have a neighbor in the MIS and stop their protocol. MIS nodes (M) try to inform their neighborhood (eliminating them), but they also actively disrupt protocols in the herald filter, causing them to fail. Apart from this, there is no influence between nodes being in different stages.

Input: σ⊕, σ , ∆max, π , α, n, n D = Θ(F ), n A = Θ(log log n), n R = Θ(α(2)), τ W = Θ(log n), τ D = Θ(log n/F ), τ lonely = Θ(log 2 n/F + log n), τ rbg = Θ(log n) States: W-
The focus of this paper is almost exclusively on the herald filter. It helps for understanding the complex algorithm to only think of the graph that is induced by nodes in the herald filter and to recall that its maximum degree is polylogarithmic in n.

The herald filter is divided into three blocks, active state/herald protocol (A), handshake protocol (L and H ) and red-blue protocol (L and H). In the first block nodes try to make contact with surrounding nodes. If this does indeed happen, both nodes engage in a handshake, which is only successful, if none of the two nodes neighbors any MIS node or a node in the third block. If the handshake succeeds, both nodes start a series of coin flipping games, with the purpose of ensuring that no two nodes that have become leaders (L) simultaneously, can join the MIS. The blocks that differ from the algorithm description in [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] are the active state and the red-blue protocol, where the changes in the latter are made to compensate the changes in the more complicated active state.

There are two ways for a node v to join the MIS-either by waiting for a long time without hearing from any nearby node, or by successfully communicating with a node u during the active state, teaming up with it (as a leader-herald pair) and together passing through the handshake and the red-blue protocol. The farther a pair of nodes advances in these blocks, the closer its leader is to become an MIS node. We now recap and describe the behavior of a node v in the herald filter, i.e., v ∈ V hf , pointing out where changes to the original algorithm occur. Loneliness. v maintains a counter lonely. Whenever v hears from another node, it resets lonely to zero. If lonely ever exceeds τ lonely = Θ log2 n/F + log n , then v assumes that it is alone/lonely in the herald filter (i.e., N Vhf∪M (v) = ∅) and joins the MIS-w.h.p., this action is safe, i.e., should v not be alone, then the neighbors of v are far from becoming MIS nodes themselves and v has enough time to eliminate them. 2 Activity. Also, v maintains an activity value γ(v) ∈ γ min , 1/2 , where γ min , the initial value, is in Ω(1/ polylog n). The activity γ(v) solely governs the behavior of v in A, however all nodes in V hf maintain this value. Nodes outside V hf have zero activity. By default, In each round, γ(v) increases by a (small) constant factor σ ⊕ > 1 such that after Θ(log log n) rounds it reaches the maximum possible value 1/2. However, whenever v receives a message from a neighboring leader or herald, then v reduces γ(v) by a (large) constant factor σ σ ⊕ . This is a change to the original algorithm, where γ(v) could only increase. The reason for this change is the following. Leaders are nodes that likely become MIS nodes, and if they do then they eliminate their neighbors anyway. For safety reasons a leader l needs to wait for Θ(log n) rounds before it may join the MIS. During that time, if l's neighbors keep high activity values, progress might be hindered in a δ = O(log log n) neighborhood of l, which is why in [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] an α(δ ) = O(polyloglog n) speed loss had to be accepted and also why the algorithm of [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] only works for polynomially bounded interference graphs. By also reducing activity values, progress can be guaranteed even in a close neighborhood of a leader-herald pair and nodes can join the MIS in a much more pipelined fashion. At the same time, 'unjustified' activity value reductions only cause 'minor damage' that can be mitigated. Herald Protocol. A node v in the active state (A) participates in the herald protocol with probability γ(v) ∈ [γ min , 1/2], otherwise it tries to learn of nearby leaders, heralds or MIS nodes, by listening to one of constantly many report channels R 1 , ..., R n R , n R ≥ 3α 2 . If v participates in the herald protocol, then it chooses a channel A i from A 1 , ..., A n A with probability 2 -i . It then listens on A i with probability π ≤ 1/10 or broadcasts its ID otherwise. 3 If v listens, but receives nothing, nothing happens and v stays in A. Should v receive the message of another node u on A i , then in the next round it engages with u in the handshake protocol as a herald candidate (H ), in the hope of moving forward to the red-blue protocol together with u. Should v choose to broadcast, then it deterministically pursues the handshake as a leader candidate (L ), hoping that some other node u has heard its message and joins in for the handshake. Handshake and Red-Blue Protocol. For a detailed description and analysis we refer to [START_REF] Daum | Tight Bounds for MIS in Multichannel Radio Networks[END_REF] and [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF]. In short, a node h ∈ H that received a message in the herald protocol sends for two rounds on the handshake channel H, then listens twice, and sends again for two rounds. A node l ∈ L that was sending before acts reversely, i.e., it listens, sends and listens. Only if a node receives all expected messages it moves forward to the red-blue protocol, otherwise it returns to A. The handshake can only possibly be completed if a pair of exactly one broadcaster and one receiver participates.

The red-blue protocol is a repetition of τ rbg /8 = Θ(log n) red-blue games of 8 rounds each. In odd rounds, both nodes l and h of the leader-herald pair send a blocking signal on H, preventing nearby handshakes to succeed. At the beginning of each game, the leader l randomly picks blue or red. If it picks red, it will sends a message on channel G in round 2 and it listens on G in round 4, for blue it acts symmetrically. In round 6, l sends the index k of the meeting channel for the next red-blue game on a previously decided meeting channel R k . 4 In round 8 it listens on R k . The herald h on the other hand sends a message in both rounds 2 and 4. It listens in round 6 to update the meeting channel and in round 8 it sends a message on R k .

By design of the handshake and the blocking signals of odd rounds in the red-blue protocol, a leader l can neighbor a leader or herald of a different pair only if that other node moved to the red-blue protocol simultaneously or with a 2-round shift. If l does have such a neighbor, at some point it will not hear its herald in round 2/4, when it listens. l then aborts the red-blue protocol, notifies h in round 6 and returns to A. The messages sent by l/h in round 6/8 also have the purpose of letting nearby listening active nodes reduce their activity values. An isolated pair on the other hand cannot be knocked out anymore 5 and after τ rbg = Θ(log n) rounds the pair can assume that w.h.p. there is no other conflicting pair nearby and the leader joins the MIS.

The handshake did not change and the red-blue protocol has been extended by 2 rounds-round 8 now gives heralds also the possibility to reach their neighbors. Summary of Changes. Compared to the algorithm in [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF], the following three things have changed. The loneliness support block of the algorithm in [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] is not executed anymore, except for maintaining the counter lonely. Also, the threshold τ lonely has been lowered to Θ log 2 n/F + log n to reflect the new runtime of the algorithm. The main change is that nodes reduce their activity γ if they hear from a nearby leader or herald. The change in the red-blue game is an addition of 2 rounds: the seventh round is just a copy of rounds 1, 3 and 5; the eighth round gives the herald of the pair a possibility to notify nearby active nodes in order to reduce their activity values-so far only leaders and MIS nodes were able to reach out to their neighbors.

Note that while the algorithm itself has barely changed, the analysis needed to be extended significantly in order to achieve the optimal runtime.

Analysis

Approach

To prove that Algorithm 1 indeed solves MIS in the given time bounds, we take the following approach. In [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] it was proven that the graph, induced by nodes that passed through the decay filter, has maximum degree ∆ max = O(log 3 n). A node u in the herald filter (u ∈ V hf ) enters the MIS either if it assumes to be alone, or if it manages to create and maintain a leader-herald bond with a neighboring node for τ rbg = Θ(log n) rounds. Once u ∈ V hf , it either enters the MIS due to assumed loneliness; or if u has a neighbor in V hf , then within radius δ := δ α = Θ(log log n) soon a leader-herald pair is created that maintains its bond for τ rbg rounds. 6 So far this is the same as in [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF]. There, however, a stagnation of up to τ rbg rounds might follow before the next isolated leaderherald pair or MIS node gets created in N δ (u). Considering that up to α(δ) nodes in N δ (u) can enter the MIS before u or one of its neighbors enters itself, the runtime of herald filter is O(τ rbg α(δ)), or O(log n polyloglog n) if α is polynomial.

In the present paper, by decreasing activity levels of nodes neighboring leaderherald pairs, the stagnation that can be caused by leaders on their way to join the MIS does not last for longer than O(log log n) rounds in expectation. This allows the creation of isolated leader-herald pairs in N δ (u) in a pipelined manner, reducing the expected runtime of the herald filter to O(α(δ) log log n) = O(α δ log log n). Unlike in [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF], here we also can choose δ as an arbitrarily small value in Θ(log log n) without increasing the runtime by more than constant factors. Choosing δ < log log n/ log α and a Chernoff argument bounds the runtime of the herald filter by O(log n) with high probability.

In more detail, let u be a node that enters the herald filter in round t u . For the sake of contradiction assume that u is not decided by time t u + τ runtime . If u stays lonely, it enters the MIS eventually in τ lonely τ runtime rounds. Note that for u to move from being non-lonely to lonely, some node in N 2 (u) must have entered the MIS shortly before that and eliminated all neighbors that u had in V hf . This can happen at most α 2 times and thus the time u spends lonely is at most α 2 τ lonely τ runtime . Hence, assume that u is not lonely, i.e., has a neighbor u , and that no node in N 2 (u) joins the MIS. We show that then most of the time both u and u have a high activity value γ.

The following argumentation motivates this. For a node u to decrease γ(u), it must neighbor a pair. Let us call isolated pairs (in which the leader does not neighbor another leader or herald) good pairs and the others bad pairs. Conditioning on the event of a pair being created, there is a constant probability that it is a good pair. This can be considered progress, as it guarantees one of two things: Within O(log n) rounds either the leader of the good pair itself enters the MIS or a neighbor of this pair does. In the opposite case of bad pairs being created, in expectation these remain bad pairs only for a constant number of rounds. Moreover, w.h.p., there are no more than O(log n) rounds in total in which bad pairs exist in N 3 (u) after t u , also causing at most O(log n) rounds of u and u having an activity value below 1/2. Adjusting parameters we get that for some τ progress = O(τ lonely ) and an arbitrarily small constant ε, for (1 -ε)τ progress rounds in [t u , t u + τ progress ] the activity values of both u and u are 1/2. Furthermore, all pairs, good and bad, inform their neighbors. By the definition of good pairs, the leaders of these form an independent set. With our choice of δ thus at most O( √ log n) good pairs exist in N δ (u). We argue that the activity values of nodes neighboring a pair that participated in the red-blue protocol for Ω(log log n) rounds (which almost surely holds for good pairs), are below γ low := Θ(1/ polylog n) with some decent probability (i.e., 1 -log Ω(1) n). The total number of nodes in N δ (u) becoming part of a good pair in [t u , t u + τ progress ] is O( √ log n) and hence the total amount of nodes neighboring good pairs in that time is O( √ log n∆ max ). A union bound and a Chernoff bound provide that the total amount of rounds in which any node v in N δ (u) neighboring a good pair has an γ(v) > γ low is less than ετ progress .

Together with the previous claim we get that in (1 -2ε)τ progress rounds in [t u , t u + τ progress ] both conditions are true: γ(u) = γ(u ) = 1/2 and all good pairs in N δ (u) "silenced" their neighbors-i.e., all their neighbors have activity below γ low . Let us call a round with this property promising for u. Without going into detail, we can show that now within distance δ there exists a node w with the property of being so-called η-fat, i.e., w's neighborhood is at least roughly as active as that of any of its neighbors'. Fatness implies that w.c.p. two nodes l and h in N 1 (w) become a good leader-herald pair. As said before, such a pair reduces the activity values of its neighbors rather quickly, which causes the property of η-fatness to move away from w to another node in N δ (u) and we can repeat the argument. If a bad pair is created, then η-fatness might shortly fade, but is restored quickly, so we can almost omit this case. Again using Chernoff tail bounds, we show that at some point u itself becomes η-fat and now the creation of an MIS node in N 2 (u) is inevitably.

We summarize again. Once an MIS node or good pair arises in constant distance from u, we are done. In an Ω(log 2 n/F + log n) interval, u is mostly in a promising state. W.c.p. every O(1) rounds a node in N δ (u) becomes part of a good pair or joins the MIS. In expectation, within Θ(log log n) rounds MIS nodes eliminate their neighbors and good pairs silence theirs. After any of those events happen, we measure the time until u is in a promising state again. Using Chernoff over O( √ log n) such random variables results in needing at most O(log n) time, thus, by then u must be covered.

Guarantees from the Decay Filter

Due to lack of space we refer to [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] and [START_REF] Daum | Tight Bounds for MIS in Multichannel Radio Networks[END_REF] for a more detailed description of what the decay filter accomplishes. 7 But we informally state the two main results. For each node v the decay filter guarantees that over the runtime of Θ(log 2 n/F + log n) rounds, (1) v or one of its neighbors enters the herald filter, but (2) no more than

∆ max = O(log 3 n) nodes in N 1 (v) do.
From now on we only look at the graph G induced by V := V hf ∪ M, induced by non-eliminated nodes that made it past the decay filter. All notations are tied to this subgraph, though we omit this in our notations, i.e., N (u) means the neighborhood of u in G . Instead, if we need to consider nodes from the states W and D, then we explicitly say so and show this e.g. by writing N G (u).

Definitions for the Herald Filter

Practically all parameters (including the above mentioned ∆ max ) depend in one way or another on the bound on independence, i.e., on α, but in most cases those dependencies are captured in the hidden constants of those asymptotic bounds.

For our analysis of a node u that enters the herald filter, we observe a specific δ = Θ(log log n) neighborhood N δ (u) of u. We set

δ := δ α := log log n 2 log α = Θ(log log n), (1)
i.e., α δ = (2 log α )

log log n 2 log α = √ log n.
The choice of δ guarantees that any independent set in a δ-neighborhood is of size at most √ log n. Our main goal is to show quick progress in N δ (u). Progress is clearly achieved if an MIS node arises, but due to the way a node can become an MIS node, we also consider the creation of an isolated leader-herald pair progress (more precisely, the leader of the pair needs to be isolated from other nodes in L or H), as the leader will eventually join the MIS (or be knocked out permanently by a newly created MIS node).

Definition 1. (Good Pair, Bad Pair) Consider a leader-herald pair (l, h) in round r. We say (l, h) is a good pair in round r if none of the neighbors of l (other than h) is (1) in state L or [START_REF] Alliance | Zigbee specification[END_REF] in state H or ( 3) is a herald candidate in round 5 or 6 of its respective handshake. Otherwise we say that (l, h) is a bad pair.

Note that the definition of a good/bad pair is independent of possibly neighboring MIS nodes. MIS nodes existing already for 4 rounds prevent the creation of leaderherald pairs in their neighborhood completely. If on the other hand a new MIS node appears next to a leader-herald pair (which is w.h.p. only possible through the loneliness route), then we have progress in a close neighborhood. Also, note that only the leader of the pair must be 'isolated'. There are two reasons for this: (1) only leaders join the MIS (2) by protocol design the herald of a pair can only receive messages from MIS nodes or its own leader-not by other leaders (not even in round 6) nor other heralds. This is due to the fact that any neighboring heralds act completely synchronously and a leader neighboring a non-paired herald is ahead by precisely 2 rounds. 8 Note also that bad pairs can become good, but not vice versa. This is because all leaders and heralds prevent the creation of further leaders/heralds in their neighborhood. Definition 2. (Activity Mass) For a node u we define Γ (u) := v∈N 1 (u) γ(v). We call this the activity sum or activity mass of node u. Furthermore we let Γ

• (u) := Γ (u) -γ(u) = v∈N (u) γ(v).
In some cases we are only interested in the activity mass of active nodes and then we have

Γ A (u) := v∈N 1 A (u) γ(v) and Γ • A (u) is defined analogously. Also γ min := log -24 n = Θ(1/ polylog n), (2)
γ low := √ γ min = log -12 n. (3)
Definition 3. (Fatness) We call a node u η-fat for some value η ∈ (0, 1), if it holds that

Γ (u) ≥ η • max v∈N (u) {Γ (v)}.
In simple words, in terms of activity mass, u is (at least) in the same 'league' as its neighboring nodes. Using this we choose a specific fatness parameter η < 1:

η = η α := α -8 ≤ α -2 log ∆max log log n (4)
The choice of η assures that a chain of activity sums

(Γ (v i )) i≥1 of nodes v i on a path v 1 , v 2 , v 3 , . . . with Γ (v i ) ≥ η -1 Γ (v i-1 ) and Γ (v 1 ) ≥ 2 has length at most δ, because (η -1 ) δ = (α -8 ) -log log n 2 log α ≥ (2 log α ) 2 log ∆max log log n log log n 2 log α = ∆ max γ(u)≤1/2 > max u∈Vhf Γ (u). (5)
The algorithm needs to know a few more parameters. σ ⊕ and σ govern the changes in a node's activity level. The former is a small constant, greater than, but close to 1. In most rounds a node u increases γ(u) by σ ⊕ . σ is a much larger factor used for decreasing activity, large enough to undo many previous increments, but still in O(1).

σ ⊕ := 2 6/(1000 m) > 1 (6) σ := σ 20 m ⊕ = 2 12/100 > 1 (7)
m is a large enough constant that depends on n R , but assuming that n R ≥ 3α 2 , m ≥ 2 16 n R suffices. Since γ min = log -24 n, 167 m log log n = Θ(log log n) consecutive increments raise a node's activity value to 1/2. Analogously, Θ(log log n) decrements decrease it to its minimal value γ min . Also two time thresholds τ rbg = Θ(log n) and τ lonely = Θ(log 2 n/F + log n) are needed by the algorithm. τ rbg is the number of rounds a node spends in the red-blue protocol, and it is a multiple of 8. If a node u ∈ V hf does not receive a single message for τ lonely consecutive rounds, while being in the herald filter, a u deduces that it is alone or all its neighbors got eliminated, and joins the MIS. In our analysis we use further time thresholds τ notification = Θ(log n), τ progress = Θ(log 2 n/F + log n) and τ runtime = Θ(log 2 n/F + log n), for which the following inequality chain holds:

τ runtime τ lonely τ progress τ rbg τ notification
τ notification is the maximum time needed for an MIS node to notify, w.h.p., all its neighbors. If a node u is not lonely, then, w.h.p., significant progress is achieved in less than τ progress rounds; more precisely, an MIS node is created in N O(1) (u). W.h.p., τ runtime is the maximum time a node spends in the herald filter before it gets decided.

Candidate Election-Nodes in States A (and L )

In this section we want to establish a few facts about how nodes can transit from state A to state L or H , respectively. Note that nodes can switch between states A and L without communication, but to get towards any of the three states H , L and H, communication is mandatory. For some node u, constant k, round r and an index i ∈ {1, . . . , n A } we can show that with probability 1 -Ω(α k π ) no node in N k A (u) receives anything on any herald election channel A i . If we condition on certain events tied to index i, like knowing (by peeking at random bits of some nodes) that some nodes do not operate on A i , do operate on A i , do operate and broadcast or listen on A i , then the statement does still hold true for all other channels. I.e., regardless of conditioning on aforementioned events, with probability 1 -Ω(π ) no node in N k A (u) receives anything on any channel A j = A i . Thus, by choosing π small, we can decrease the chances of herald creation.

For lack of space we refer to [START_REF] Daum | Tight Bounds for MIS in Multichannel Radio Networks[END_REF] for a proper lemma statement. Under certain conditions the creation of herald candidates can be lower bounded. However, for our algorithm to work, we not only need to prove that they are created, but that this happens in solitude, i.e., in a close neighborhood no other herald candidates are created. The next lemma-an adaption of Lemma 8.8 from [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF]-ensures this.

1. Let t be a round in which for a node u ∈ A the following holds: there is no herald candidate in N 2 (u), all nodes v ∈ N 2 (u) that neighbor a herald or leader, have γ(v) ≤ γ low , all nodes in N 2 (u) neighboring MIS nodes are eliminated, -Γ (u) ≥ 1, If in addition it holds that either (a) Γ (u) < 5α, u is 1 5α -fat and γ(u) = 1 2 , or (b) Γ (u) ≥ 5α and u is η-fat, then by the end of round t ∈ [t, t + 7], with probability Ω(π ) either a node in N 2 (u) joins the MIS or a good pair (l, h)

∈ (L ∩ N 1 (u)) × (H ∩ N 1 (u)) is created.
Let us start with an intuition of this Lemma. The basic intention is to show that if u is η-fat, then w.c.p. in constant many rounds a good leader-herald pair with both endpoints in N 1 (u) arises-for this u itself does not have to have a high γ value, i.e., u does not need to be a likely part of the pair. The lemma lists many requirements. We show that shortly after a node v moves to the herald filter, in distance δ = O(log log n) most of the time there exists a node u that satisfies these conditions. We also show that if an isolated pair is created in N 1 (u), those requirements are again satisfied O(polyloglog n) rounds later (in expectation) by another node u in this δ-neighborhood of v.

We want to point out that in the neighborhood of a fat node u with Γ (u) at least one, w.c.p. "good things" happen (i.e., the creation of MIS nodes or good leader-herald pairs) within constant many rounds, even if there are herald candidates nearby or even if some nodes neighboring bad leaders/heralds have high γ values. In other words, the first two requirements could be omitted. Instead we use other results to show that from those relaxed conditions one can get to the tighter ones listed here w.c.p. in constant many rounds. We argue in Subsection 4.5, that every time an isolated pair is created, the algorithm achieves progress, as it guarantees the creation of an MIS node nearbyeven if this event is delayed by O(log n) rounds.

Therefore, Lemma 1 "promises" progress in the proximity of a fat node. However, we have no such statement for areas without fat nodes. Indeed an excessive creation of bad pairs in such areas can even cause problems for our argumentation. The next result, which is a key result within the whole analysis, implies that if a pair is created at all, then w.c.p. this pair is good. This allows us to proof later in Lemma 4 that nodes in the herald filter are practically always very active in the candidate election process-unless they already neighbor an MIS node or a good pair. Lemma 2. Let r be a round in which node u is in state A and N A (u) = ∅. Let B u be the event that at the end of round r, u moves to state H due to receiving a message from some node v ∈ N A (u) on some channel Aλ. Further, let D u ⊆ B u be the event that B u holds and in addition no other node v ∈ N 3 (v) \ {u} receives any message on channel Aλ in round r. It holds that

P(B u ) = O π γ(u) Γ • A (u) Γ • A (u) > 2 O (π γ(u)Γ • A (u)) Γ • A (u) ≤ 2 , (8)
P(D u ) = Ω π γ(u) Γ • A (u) Γ • A (u) > 2 Ω (π γ(u)Γ • A (u)) Γ • A (u) ≤ 2 . (9)
A simple corollary is-using the remarks in the beginning of Subsection 4.4-that if u gets a message from v and there are no leaders or heralds nearby, then w.c.p. u and v form a good leader-herald pair after 6 rounds.

Handshake

& Red-Blue Protocol-States L , H , L, H
We next very shortly recap and summarize the effects of the so-called Handshake and Red-Blue Game, but for detailed information please see [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF][START_REF] Daum | Tight Bounds for MIS in Multichannel Radio Networks[END_REF]. Foremost, the handshake cannot be passed by two nodes l and h, if l also reached another herald h . But the handshake also guarantees, that if two leader-herald pairs neighbor each other during the red-blue protocol, i.e., one node from one pair neighbors a node of another pair, then both pairs conducted the handshake at the same time (or with an offset of 2 rounds).

The red-blue protocol grants that if a good pair (l, h) is executing the protocol, then a new MIS node arises nearby within τ rbg = Θ(log n) rounds (usually the leader l). On the other hand, any bad pair remains bad for only O(1) rounds in expectation (note that good pairs can never turn bad).

Joining the MIS-Nodes in States M and E

Property 1 (P). The set M is an independent set at all times. This intuitive assumption is needed for some of the upcoming statements; it is clearly true at the beginning of the algorithm, when M = ∅. Lemma 7 shows that if (P) is violated, then w.h.p. a contradiction occurs. The next lemma makes sure that nodes in N (M) soon learn of their coverage. Lemma 3. Assume (P) holds. Let v be a node that enters state M at time t. Let w be a node in N G (v) that is awake at time t ≥ t and, if w ∈ L ∪ H, that it is at most in round 9 10 τ rbg of its corresponding red-blue protocol. Then by time t + τ notification = t + O(log n), w.h.p., w is in state E. 9 4.7 Progress and Runtime Lemma 8.13 of [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] shows that once a good leader-herald pair (l, h) is created, its leader (or another node in N 2 (l)) joins the MIS within O(log n) rounds. Also, within close proximity of fat nodes (which exist in any δ-neighborhood of nodes in V hf ) w.c.p. such solitary pairs are created every O(1) rounds. In the algorithm of [START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] it might happen that after a good pair (l, h) is created N δ (u), the only fat node in N δ (u) is close to (l, h). A good pair blocks the creation of other pairs around, so progress might be stalled until l joins the MIS, eliminating its neighbors (and therefore their activity) and finally, forcing the local condition of fatness to move to a different area of the graph.

Here we changed the algorithm to take care of this potential stagnancy issue. We want the attribute of fatness to move away from a good pair long before the leader joins the MIS. More precisely, a node not neighboring good pairs should become fat within o(log n) rounds. For this we require good pairs to reduce the activity levels of their neighborhoods. However, a leader-herald pair does not know whether it forms a good pair or a bad one before the τ rbg = Θ(log n) red-blue games are over. The idea to deal with this difficulty is the following. Good pairs manage in expectation within O(log log n) rounds to reduce their neighborhood's activity far enough such that most of the time those nodes can be considered inactive. Bad pairs, however, last for only a constant number of rounds in expectation, and are created rarely enough 10 for affected nodes to recover their lost activity quickly. In other words, the longer a node is a leader, the more likely it is indeed a good one.

Careful analysis allows to transform these observations into high probability results. In the following γ(u, t) denotes the activity level of node u in round t. Also, let ε be a constant smaller than one-about 0.1 is sufficiently small for the proofs. Next we upper bound the number of rounds in which any neighbors of good pairs within distance δ from u manage to exceed the activity threshold γ low . Definition 4. For a node u and a round r let I(u, r) be the event that all nodes x ∈ N δ (u), which neighbor an MIS node, are in state E, and all nodes x ∈ N δ (u), which neighbor a good herald h or good leader l, h, l ∈ (H ∪ L) \ N (M), have γ(x) ≤ γ low = √ γ min = log -12 n and are neither bad leaders nor bad heralds.

Lemma 5. Assume that (P) holds. Further, let r be a round in which node u is in the herald filter and set J := [r + 1, r + τ progress ]. Then, w.h.p., one of the following holds:

-Within τ progress = O(log n) rounds, there is an MIS node in N 1 (u), or -| {r ∈ J : I(u, r)holds} | ≥ (1 -ε)τ progress .

Lemma 6. Assume that (P) holds. Let t u be a round in which a node u / ∈ N 1 (M) has a neighbor u / ∈ N 1 (M) in the herald filter. Then, w.h.p., within τ progress = O(log 2 n/F + log n) rounds a node in N 1 ({u, u }) joins the MIS. Lemma 7. W.h.p., property (P) is not violated throughout the runtime of the algorithm. Now we have everything at hand to prove Theorem 1.

Proof Sketch (of Theorem 1). As stated earlier, the runtime of the decay filter is within O log 2 n/F + log n , i.e., for every node u in the decay filter, by that time one node v ∈ N 1 G (u) enters the herald filter. We also know that over the course of O(log 2 n) rounds the maximum degree of the graph G induced by all nodes in the herald filter is at most O(log 3 n).

Let thus u be a node that enters the herald filter. If it stays lonely for τ lonely = Θ log 2 n/F +log n rounds, then u joins the MIS and we are done. Hence assume that u does hear from a neighboring node u in the herald filter before τ lonely rounds have passed. We can now apply Lemma 6 to get an MIS node v created within τ progress = O log 2 n/F + log n rounds. It either neighbors u, in which case within τ notification = O(log n) rounds u is decided w.h.p., or it neighbors u , which is also then eliminated in τ notification rounds. That way u can become lonely again. However, since an MIS node has been created in N 2 (u), this can happen at most α 2 times. Thus, at most τ runtime = 2α 2 τ lonely rounds after u entered the herald filter, u is decided.

Lemma 4 .

 4 Let t be a time at which a node u / ∈ N 1 (M) is in the herald filter. Then, w.h.p., one of following holds: (a) Withinτ progress = O(log 2 n/F + log n) rounds, u ∈ N 1 (M), or (b) | {t ∈ [t + 1, t + τ progress ] : γ(u, t ) = 1/2} | ≥ (1 -ε)τ progress .

For example, the IEEE 802.11 WLAN standard provides a channel spectrum of up to

(partially overlapping) channels and Bluetooth specifies 79 usable channels.

In[START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] there existed some component called loneliness support block, operating on its own set of channels S1, ..., Sn S ; this block and its channels have been removed.

We want to note that π is a constant parameter that we can choose arbitrarily.

The very first meeting channel is fixed by l during the handshake.

except by an MIS node, but that already implies progress

"Soon" indeed means in O(1) rounds in expectation, as long as F = Ω(log log n).

The underlying algorithm has been first used and analyzed in[11], in a slightly more restrictive graph model and in[START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] it was shown that it also works in BIGs.

Cf. Lemma 8.10 in[START_REF] Daum | Maximal Independent Sets in Multichannel Radio Networks[END_REF] and the actions of heralds/leaders in rounds 6/8 of a red-blue game.