{'fraction_non_alphanumeric': 0.05058530963789652, 'fraction_numerical': 0.015557712136835083, 'mean_word_length': 3.876515823720793, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks

We address the problem of minimizing power consumption when performing reliable broadcast on a radio network under the following popular model. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message, all awake nodes within distance r receive the message. In the broadcast problem, some node wants to successfully send a message to all other nodes in the network even when up to a 1/2 fraction of the nodes within every neighborhood can be deleted by an adversary. The set of deleted nodes is carefully chosen by the adversary to foil our algorithm and moreover, the set of deleted nodes may change periodically. This models worst-case behavior due to mobile nodes, static nodes losing power or simply some points in the grid being unoccupied. A trivial solution requires each node in the network to be awake roughly 1/2 the time, and a trivial lower bound shows that each node must be awake for at least a 1/n fraction of the time. Our first result is an algorithm that requires each node to be awake for only a 1/sqrt(n) fraction of the time in expectation. Our algorithm achieves this while ensuring correctness with probability 1, and keeping optimal values for other resource costs such as latency and number of messages sent. We give a lower-bound that shows that this reduction in power consumption is asymptotically optimal when latency and number of messages sent must be optimal. If we can increase the latency and messages sent by only a log*n factor we give a Las Vegas algorithm that requires each node to be awake for only a (log*n)/n expected fraction of the time; we give a lower-bound showing that this second algorithm is near optimal. Finally, we show how to ensure energy-efficient broadcast in the presence of Byzantine faults.


Introduction
We consider the problem of broadcast of a message over a radio network. We use a model for radio networks that has been studied extensively in the distributed computing literature [15,3,4,5]. In particular, we assume each node is situated on a point in a (possibly infinite) two dimensional grid and whenever a node sends a message, all awake nodes within L ∞ distance r, for some fixed r, receive the message. If two nodes broadcast simultaneously, the messages interfere, so nodes in the neighborhoods of both senders receive no message. Thus, as in previous work, we assign a predetermined schedule of time slots to the nodes in a given neighborhood to avoid such message collision. We also assume that in any 2r + 1 by 2r + 1 square in the grid, up to t nodes may suffer faults. We consider the cases where these faults are either all fail-stop: the t nodes are all deleted from the network; or, much harder, Byzantine: the t nodes are taken over by an adversary and deviate from our protocol in an arbitrary manner. The goal is to design a protocol that allows for a single node to broadcast a message to all other nodes in the network, so that eventually all non-faulty nodes learn the correct message.
Power consumption is one of the most critical resource costs in radio and sensor networks, particularly since nodes are usually battery powered. The wireless network cards on board radio network devices offer a number of different modes with such typical states as off, sleeping, idle, receiving and sending [2,22] and the energy costs across these modes can vary significantly. The device is always listening for messages while in the idle state, thus maintaining the idle state is only slightly less costly then maintaining the receiving state. Remarkably, the cost of the idle, receiving and sending states are all roughly equivalent, and these costs are an order of magnitude larger than the cost of the sleep state 2 . Thus, to a first approximation, the amount of time spent in the sleep state gives an excellent estimate of the energy efficiency of a given algorithm [21]. Unfortunately, all past algorithms for the reliable broadcast problem essentially ignore energy efficiency by never allowing any node in the network to transition to the sleep state 3 .
In this paper, we directly address the problem of designing energy-efficient algorithms for broadcast. Crucial to our approach is the analysis of a new data streaming problem that we call the Bad Santa problem.

Bad Santa
A child is presented with n boxes, one after another. When given each box, the child must immediately decide whether or not to open it. If the child decides not to open a box, he is never allowed to revisit it. At least half the boxes have presents in them, but the decision as to which boxes have presents is made by an omniscient and adversarial Santa that wants the child to open as many empty boxes as possible. The poor child just wants to find a single present, while opening the smallest expected number of boxes. This is the Bad Santa problem. 2 The difference in energy consumption between the idle/send/receive states and the sleep state differs depending on the type of card and the communication standard being employed. For example, using the IEEE 802.11 standard with a 11 Mbps card, the ratios between power consumption of the idle/send/receive states and the sleep state are all more than 15 [9]. In [12], with a different setup employing TinyOS and a TR1000 transceiver, the measured ratios are over 1000. 3 When we speak of "reliable broadcast" we are referring to the model considered in [15,3,4,5]; the terminology has been used in the context of other sensor network models.
More formally, a sequence of n bits is streaming by and at least half of the n bits are 1. We can query any bit as it passes, but if we allow a bit to pass without querying it, it is lost. We must locate a 1. That is, we seek a Las Vegas algorithm with a hard guarantee of success and an minimum expected number of queries. We are interested in two variants of this problem. First the single round case described above. Second the multi-round case where there are multiple n-bit streams that we query consecutively. In each stream at least half the values are 1, but these values may be distributed differently in each stream. Here again we want to find how many expected queries are required until we find a 1.
The connection of this problem to energy efficiency in sensor networks is as follows. The value n is (2r + 1) 2 and the bits to be queried represent time steps at which a message may be sent. During some of these time steps, due to a fault in the processor that is scheduled to send in that time step, no message is sent. In this case, the bit queried in that time step is a 0. However, in at least half of the n time steps, the processor is not faulty and in this case, the bit queried will be a 1. The goal of the listening processor is to sleep as much as possible (query as few bits as possible) but still guarantee it will receive the message (query a 1).
We insist that the data streaming algorithm guarantee that a 1 be found since any probability of error would depend on n, which may be much smaller than the total number of nodes in the network. In particular, even a probability of error that is exponentially small in n might not be large enough to use a union bound to show that all nodes in the network receive the correct message with high probability.

Our Results
We present four major results in this paper that are summarized in the theorems below. Theorem 1 is given in Section 2; Theorem 2 in Section 2.1; Theorem 3 in Section ??; and Theorem 4 in Section 3.
Theorem 1. For the single round Bad Santa problem, the optimal expected number of queries is Θ( √ n) Theorem 2. For the k round Bad Santa problem, the optimal expected number of queries is O(log (k) (n/2) + k and Ω(log (2k) n). In particular, for k = log * n, we can ensure the expected number of queries is O(log * n) The following two theorems about energy-efficient broadcast are established by algorithms based on solutions to the Bad Santa problem. Theorem 3 essentially follows directly from Theorems 1 and 2. Theorem 4 requires a fingerprint of the message to first be broadcast through the network. This fingerprint must be sent without any nodes sleeping in order to ensure that all nodes receive the correct fingerprint despite the Byzantine faults. However, once the fingerprint is known by all nodes, the entire message can be sent through the network, in as energy-efficient a manner as in Theorem 3. For both theorems, and throughout the rest of this paper, we let n = (2r + 1) 2 . • For any k between 1 and log * n, the second algorithm requires all nodes to be awake only a O((log (k) n)/n) fraction of the time and has latency and bandwidth within a factor of k of optimal. In particular, each node sends out the message k times, and each node learns the correct message within O(knd) time steps where d is the L ∞ distance between the node and the originator of the message.
Theorem 4. Assume we have a network where strictly less than a 1/4 fraction of the nodes suffer Byzantine faults in any square of size 2r+1 by 2r+1. Further, assume that the message, m to be broadcast consists of |m| bits, and that the adversary controlling the Byzantine nodes would like to replace the message m with some other message m ′ . Then there exist two algorithms, both of which ensure that with probability at least 1 − 1 |m| log |m| , all non-faulty nodes receive the correct message m. Both algorithms require all nodes to be awake for every step during which a fingerprint of size log 2 |m| is initially broadcast to the network. However, after this, when the message m itself is broadcast, the algorithms have the following properties.
• The first algorithm requires all nodes to be awake only a 1/ √ n fraction of the time and has optimal latency and bandwidth.
• For any k between 1 and log * n, the second algorithm requires all nodes to be awake only a O((log (k) n)/n) fraction of the time and has latency and bandwidth within a factor of k of optimal.

Related Work
The reliable broadcast problem over a radio network arranged on a two-dimensional grid has been extensively studied [15,3,4,5]. The current state of the art on this problem is a clever algorithm that can ensure that a message is sent reliably to all non-faulty nodes provided that strictly less than a 1/4 fraction of the nodes in any (2r + 1) by (2r + 1) square of the grid suffer Byzantine faults [5]. Unfortunately, as mentioned previously, all previous algorithms proposed for this problem require each node in the network to be awake for every time step, and thus are not energy-efficient. Our algorithm from Theorem 4 makes use of the algorithm from [5] to broadcast the fingerprint of the message. Data streaming problems have been very popular in the last several years [11,13]. Generally, past work in this area focuses on computing statistics on the data using a small number of passes over the data stream. In [11], the authors treat their data stream as a directed multi-graph and investigate the space requirements of computing certain graph properties regarding node degree and connectedness. Munro and Paterson [16] consider the problem of selection and sorting with a limited number of passes over one-way read-only memory. Along similar lines, Guha and McGregor [19,20] examine the problem of computing statistics over data streams where the data objects are ordered either randomly or arbitrarily. Alon, Matias and Szegedy [1] examine the space complexity of approximating the frequency of moments with a single pass over a data stream. In all of these cases, and others [8,7], the models differ substantially from our proposed data streaming problem. Rather than computing statistics or selection problems, we are concerned with the guaranteed discovery of a particular value, and under our model expected query complexity takes priority over space complexity.

The Single Stream Problem
We consider the single stream problem first. A naive algorithm is to query n/2 + 1 bits uniformly at random. The expected cost for this algorithm is Θ(n) since the adversary will place the 1's at the end of the stream. The following is an improved algorithm.
Single Round Strategy

Perform
√ n queries uniformly at random from the first half of the queue. Stop immediately upon finding a 1.
2. Else, starting with the first bit in the second half of the stream, query each consecutive bit until a 1 is obtained.
. This implies that there are then (n/2) − i √ n 1s in the second half of the stream. By querying √ n slots uniformly at random in the first half of the stream, the probability that the algorithm fails to obtain a 1 in the first half is no more than: for an expected overall cost not exceeding: We find the maximum by taking the derivative: and setting it to zero while solving for i gives: Finally, plugging this into the expected cost function gives an expected cost of at most 3 2 √ n.
We now show that this bound is optimal within a constant factor.
Theorem 6. Ω( √ n) expected queries are necessary in the single round case.
Proof. We follow Yao's min-max method [23] to prove lower bounds on any randomized algorithm which errs with probability no greater than λ = 1/2Õ ( √ n) : We describe an input distribution and show that any deterministic algorithm which errs with tolerance (average error) less than 2λ = 1/2Õ ( √ n) on this input distribution requires Ω( √ n) queries on average for this distribution. By [23], this implies that the complexity of any randomized algorithm with error λ has cost 1/2Ω( = 2λ in the distribution, the algorithm errs with probability at least 2λ and there is a contradiction. We conclude that any algorithm erring with probability less than 2λ must either have x > √ n or queries greater than √ n − x bits of [n/2 + 1, n/2 + √ n]. Now, we show that any such deterministic algorithm incurs an average cost of Ω( √ n) on the CASE 1 strings in this distribution. If x ≥ √ n then for a constant fraction of strings in CASE 1, the algorithm will ask at least √ n queries in [1, n/2] without finding a 1. If x < √ n, then with constant probability the algorithm will incur a cost of x in [1, ..n/2] and go on to incur a cost of √ n − x in [n/2 + 1, n/2 + √ n] since all the values there are 0.
We have shown that the distributional complexity with error 2λ is Ω( √ n). It follows from [23] that the randomized complexity with error λ is Ω( √ n).

The Multiple Streams Problem
We define a (α, β)-strategy to be an algorithm which occurs over no more than α streams, each with at least a (possibly different) set of at least n/2 values of 1, and which incurs expected cost (number of queries) at most β. In the previous section, we demonstrated a (1, O( √ n))-strategy. We now consider the following protocol over (k + 1) streams.

Multi-Round Selection Strategy
For i = k to 1 • Perform lg (i) (n/2) queries uniformly at random over the entire stream. Stop if a 1 is obtained.
If no value of 1 has been found, use the single stream strategy on the final stream.
Proof. Correctness is clear because in the worst case, we use the correct one-round strategy in the final round. The expected cost is at most Proof. By the definition of the iterated logarithm: lg * n = 0 for n ≤ 1 1 + lg * (lg n) for n > 1 if k = lg * (n/2), we can plug this value into the last line of the proof for Theorem 7 which contains three terms of which only the first two depend on k. The first term is 1, by definition of lg * n, and the second is k for a total expected cost of 1 + lg * (n/2) + o(1).

Lower bound for multiple streams
First, we show the following lemma: Lemma 1. Ω(lg (i+2) n) expected queries are required for a randomized algorithm that errs with probability less than λ = (ln (i) n) −ǫ on one stream of length n. In particular, when i = 0, Ω(log log n) expected queries are required for a randomized algorithm with error less than 1/n ǫ , for any constant ǫ.
Proof. We apply Yao's min-max method [23] and consider the distribution in which with probability 1/3, one of the I 1 = [1, n/3], I 2 = [n/3 + 1, 2n/3], and I 3 = [2n/3 + 1, n] intervals is all 0's, and the other two each contain exactly n/4 1's with the 1's distributed uniformly at random. Let L denote the list of of queries of a deterministic algorithm, and let x i be the number of queries in L∩ I i . The probability that the algorithm fails to find a 1 in any interval I i is n/3−x i n/4 / n/3 n/4 > e −7x i /4 . Let I i and I j be the intervals which are not all 0's. Then the probability of failing to find a 1 in either I i and I j is > e −7(x i +x j )/4 . Hence the probability of not finding a 1 over all strings is > (1/3)e −7(x i +x j )/4 > 2λ if x 1 + x j < (3/7)ǫ lg (i+1)n . We conclude that a deterministic algorithm with average error less than 2λ can have at most one x i , i = 1, 2, 3 such that x i < (3/14)ǫ lg (i+1) n. Now we examine the cost of such an algorithm. Suppose x 1 ≥ (3ǫ/14)(ln (i+2) n then with probability 1/3 I 1 is all 0's and the cost incurred is x 1 , for an average cost of (ǫ/14)(ln (i+2) n. Now suppose x 1 < (3ǫ/14) ln (i+2) n. From above, we know x 2 > (3ǫ/14) ln (i+1) n. Then with probability 1/3, I 2 is all 0's and with probability > e −7x 1 /4 > (ln (i+1) n) −3ǫ/8 , the algorithm does not find a 1 in I 1 and incurs a cost of (3ǫ/14) lg (i+1) n in I 2 for an average cost of at least (ǫ/14)(ln (i+1) n) 1−3ǫ/8 . Hence the average cost of any such deterministic algorithm is at least min{(1/14)(ln (i+2) n, (ǫ/14)(lg (i+1) n) 1−3ǫ/8 } = Ω(ln (i+2) n). By Yao's min-max method [?], any randomized algorithm with error λ is bounded below by 1/2 the average cost of a deterministic algorithm with average error 2λ on any distribution. The lemma now follows.

Proof. The proof is by induction on the number of streams.
Base Case: Let k = 1. Either the algorithm finds a 1 in the first pass or the second pass. From Lemma ??, for any constant ǫ any algorithm which fails to find a 1 in the first pass with probability ≤ n −ǫ has expected cost Ω(log log n). If the algorithm fails to find a 1 in the first pass with probability at least n −ǫ then the expected cost to the algorithm is at least the probability it fails in the first pass times the expected cost of always finding a 1 in the second and final pass, which is n −ǫ * Ω( √ n). (The second factor is from Lemma ??. Choosing ǫ < 1/2, the expected cost is Ω(log log n).

Inductive
Step: Now assume the hypothesis is true for up to k > 1 streams. Assume we have k + 1 streams. Any randomized algorithm either fails to find a 1 in the first stream with probability less than (1/ ln (2k−2) ) ǫ n, in which case by Lemma 1, the expected cost of the algorithm when it processes the first stream is Ω(ln (2k) n) or the probability that it fails in the first pass is at least (1/ ln (2k−2) ) ǫ n. In that case, the expected cost deriving from queries of the second stream is at least (1/ ln (2k−2) ) ǫ n * Ω(ln (2k−2) n) where the second factor of this expression is the expected number of queries needed to find a 1 in k streams, as given by the induction hypothesis. The minimum expected cost of any randomized algorithm is the minimum of these two possibilities, which is Ω(ln (2k) n).
Node at distance r from q 00 00 00 11 11 11 00 00 00 11 11 p(x,y) Figure 1: A depiction of a corridor for r = 3. Together the nodes in regions E constitute S y,cor while the nodes in F and G constitute S x,cor . Node disjoint paths of the form (u i , q) originate from nodes u i in region A. Node disjoint paths of the form (u i , u ′ i , q) originate from nodes u i in region B and traverse through nodes in u ′ i in B ′ to reach node q. The yellow node lies at a distance r from q and has a location farthest from (0, 0) that lies in N (q) ∩ S cor . as the dealer, to all nodes in the lattice. The algorithms of [3,4] are optimal in the sense that they achieve reliable broadcast for t < (r/2)(2r + 1) while Koo [15] has shown that no algorithm can tolerate t ≥ (r/2)(2r + 1). Recent work by [5] extends these results to the setting where faulty nodes can spoof the addresses of correct nodes in the network and cause a bounded number of message collisions. Under the protocol described in [3,4], for a value m of |m| bits, the adversary can force a node to listen to (2t + 1)|m| ≥ r(2r + 1)|m| = Θ(r 2 |m|) bits before committing.
Here we maintain the original model for finite graphs with the added assumption that the adversary is computationally bounded. Under this scenario, it is possible to achieve a substantial power savings over the original protocols of [3,4], as we will now demonstrate. Let h be a secure hash function known to all nodes that takes an input m and outputs a fingerprint of size Θ(log 2 |m|) bits.
For the following analysis, we define a corridor of width 2r + 1 starting at the dealer located at point (0, 0) and ending at node p = (x, y). We sometimes denote a point q at grid location (x, y) as q(x, y). We define the set of nodes in the corridor to be S cor = S x,cor ∪ S y,cor Figure 1 illustrates a corridor for r = 3. We use the schedule suggested in [15]. Under this schedule, every node in N (x, y), the neighborhood of point (x, y), is allotted one time step to broadcast before the schedule repeats after (2r + 1) 2 time steps. We will refer to a full pass through the (2r + 1) 2 time steps of the schedule as a round. We need the following lemma which is an extension of implicit claims in [3] and the statement of [5] (Claim 1). If the dealer, d(0, 0), broadcasts m at time step t init , node p(x, y) is able to commit to m at least by time step t init + 2(2r + 1) 2 (|x| + |y| − r).

Lemma 2.
Proof. We are assuming the same schedule as in [15] and the same protocol as in [4]; however, we are restricting our view to those nodes in S cor . That is, nodes in S cor will only accept messages from other nodes in S cor and they will ignore all messages they receive from nodes outside the corridor. Clearly, this can only result in a slowdown in the propagation of the broadcast value; moreover, the rectilinear shape of the corridor can only slow down the rate of propagation in comparison to the original propagation described in [4]. An argument identical to that in [4] (Theorem 4) can be used to show each node q(x ′ , y ′ ) ∈ S cor will commit to the correct value by receiving messages along at least 2t + 1 node disjoint paths P i of the form (u i , q) and (u i , u ′ i , q) where u i , u ′ i are distinct nodes and lie in the corridor and u i ∈ N (x ′ , y ′ ); we do not repeat this argument.
We now consider the time required until p(x, y) can commit to m. Without loss of generality, assume that x, y ≥ 0 and that the broadcast first moves nodes in S y,cor and then along nodes in S x,cor . At t init , the dealer broadcasts m and all nodes in N (0, 0) commit to m. Consider a node q(a, r + 1) where −r ≤ a ≤ r. It takes at most one round for q to receive messages along paths of the form (u i , q). Concurrently, in this one round, nodes u i can transmit messages to nodes u ′ i along paths of the form (u i , u ′ i , q). At most an additional round is required to send from nodes u i to q. Therefore, at most two rounds are required before q can commit. Note that this holds for all nodes with coordinates (a, r + 1) for −r ≤ a ≤ r; this entire row can commit after at most two rounds. It follows that all nodes in S y,cor are committed to m after 2y rounds. An identical argument can be used to show that all nodes in S x,cor are committed to m after 2(x − r) rounds. Therefore, p commits after at most 2(x + y − r) rounds or, equivalently, 2(2r + 1) 2 (x + y − r) time steps; if x and y can take on negative values, this becomes 2(2r + 1) 2 (|x| + |y| − r).
2. Each node i in N (d) commits to h(m) and does a one-time local broadcast of commit(i, h(m), t init ).
The following protocol is followed by each node p including the nodes in the first two steps: 3. If node p receives commit(q, h(m), t init ) for the first time, it records this message and broadcasts heard(p, q, h(m), t init ).
4. If node p receives heard(q, w, h(m), t init ) for the first time, it records this message.
5. If at any point, p(x, y) holds t + 1 messages m 1 , m 2 , ... such that commit(a i , h(m), t init ) or m i = heard(a i , a i ′ , h(m), t init ) where for all i, a i , a i ′ ∈ N (q) for some node q and for all i, j, a i = a j , a i = a j ′ , p(x, y) sets f maj = h(m), does a one-time broadcast of commit(p, f maj , t init ).
6. For i = 0, ..., k rounds, p executes the following: (a) Let G p denote the set of all nodes that sent p the majority fingerprint f maj and the majority initial time value t init . Assume |G p | = n and, for ease of analysis, let us consider G p to be an ordered set where the nodes, denoted by {g 0 , ..., g n−1 }, are ordered from earliest to latest by broadcast order as dictated by the broadcast schedule. Node p picks slots to listen to according to the algorithm for the (k + 1, O(lg (k) (n/2) + k))-strategy. Let Q i denote the set of nodes corresponding to these chosen time slots.
(b) Node p listens during the time slot only when 1) node q(x ′ , y ′ ) ∈ Q i is scheduled to broadcast and 2) immediately following time step t init +2(2r +1) 2 (|x ′ |+|y ′ |+r)+1 (inclusive). In listening to node q, p will obtain a value m q . If h(m q ) = f maj , then p commits to m q , breaks the for-loop and proceeds directly to Step 7.
7. Node p(x, y) waits until the time step 1) when node p is scheduled to broadcast and 2) immediately following time step t init + 2(2r + 1) 2 (|x| + |y| + r) + 1 (inclusive) and then does a broadcast of commit(p, m q ). Node p broadcasts commit(p, m q ) for a second and final time on its next turn (in the next round).

The Necessity of Hard Guarantees
We now explicitly address the necessity of a hard guarantee in our reliable broadcast protocol. At first glance, it may appear that the hard requirement can be ignored. However, if a correct node fails to commit to a correct message, [3] proves that reliable broadcast is impossible 4 . Therefore, for reliable broadcast to be guaranteed with probability 1, we cannot tolerate any failures. In turn, to guarantee reliable broadcast with high probability, the probability of such a failure must be overwhelmingly small in the total size of the network, N . There are two ways in which a correct node could fail to obtain the correct message by the above protocol: 1. The adversary achieves a collision for the secure hash function.

2.
A good node does not query enough nodes in its neighborhood.
Let n = (2r + 1) 2 be the number of nodes in a single neighborhood. The first case is avoided by using a large enough fingerprint. In the second case, we can use a sampling algorithm to reduce the probability that a node fails to obtain the correct message. However, without a hard guarantee, the probability of such a failure is bounded in terms of n (the size of the neighborhood), not N . Realistically, we should expect r to be small in comparison to the total size of the network and, consequently, n ≪ N . Therefore, in this case, we cannot make the probability of such a failure small in terms of the total size of the network and so we require a hard guarantee on message receipt.

Correctness of the Bit-Reduction Algorithm
Now that we have illustrated the key design points of our algorithm, we prove its correctness.
Theorem 9. Let m denote the message sent from the dealer and let |m| be the number of bits in m. Let h be a secure hash function that maps to a fingerprint of size Θ(log 2 |m|). The reliable broadcast protocol with bit reduction has the following properties: • Reliable broadcast of m is achieved with probability of error that is superpolynomially small in |m| (i.e. less than O(1/|m| C log |m| ) for some constant C).
Proof. We begin by proving correctness. By assumption, h is a secure hash function and, therefore, given h(x), the probability that the adversary obtains a value x ′ such that h(x ′ ) = h(x) is 2 −Θ(log 2 |m|) = |m| −Θ(log |m|) . Therefore, it will take the adversary superpolynomial time in m to forge such an x ′ and so f maj will correspond to the correct value m. Steps 1-5 of the BR protocol, are no different than the broadcast presented in [4] where the values being transmitted are a fingerprint and an initial time value. Consequently, every correct node will be able to derive a majority fingerprint f maj and t init value from the messages it receives. By the security of h, h(m) = f maj with high probability and, by the correctness of the protocol in [4], the majority time value will be the true t init sent originally by the dealer. In Step 6a, if p receives m q = h(f maj ) from q for some i = 0, ..., k, p can be assured, again with high probability, that m q is the correct value m. Let S p denote the set of nodes from which p can receive commit messages. A complication arises in attempting to guarantee that p does not miss any of the k + 1 broadcasts of m q by q ∈ S p . For instance, an extreme case occurs if every node in S p broadcasts commit messages before p begins sampling for the true value. In such a case, p will never receive the actual value to check against its fingerprint. To ensure that the appropriate nodes do not broadcast m q before p is ready, it is enough to impose a sufficiently long delay before any q ∈ S p broadcasts m q ; enough time for p to first commit to f maj . In particular, if all correct nodes in N (q) have obtained their majority fingerprint value, then it is safe for q to begin executing its k + 1 broadcasts of commit(p, m q ). Assuming the dealer broadcasts the initial fingerprint at time t init , then by Lemma 2 it will take at most t init + 2(2r + 1) 2 (|x| + |y| − r) time steps for p(x, y) to commit to f maj . Therefore if q waits until after this time step, it can be assured that p will be able to receive its transmission of m. In general, q must wait until all peers in N (q) can commit to a fingerprint. Since all nodes in N (q) are located at most r distance away, q(x ′ , y ′ ) can wait until time t init + 2(2r + 1) 2 ((|x ′ | + r) + (|y ′ | + r) − r) = t init + 2(2r + 1) 2 (|x ′ | + |y ′ | + r) at which point all of N (q) is guaranteed to have committed to a fingerprint. Define T be the time slot that is 1) scheduled for node q to broadcast and 2) occurs first after time step t init + 2(2r + 1) 2 (|x ′ | + |y ′ | + r) + 1. By Lemma 2 guarantees that p ∈ N (q) will have already committed to a majority fingerprint value and be ready to listen to m.
By the hard guarantee of our streaming problem algorithm, p will obtain a message that, when hashed, matches the fingerprint to which p committed. Therefore, p is guaranteed to commit to a value m p and, with high probability in |m|, m p is the correct value sent by the dealer 5 . Finally, again guaranteed by Lemma 2, p only begins the first of two consecutive broadcasts of commit(p, m p ) after all nodes in N (p) have been given enough time to commit to a fingerprint.
To show resource costs, note that p listens to (2t + 1) ≤ r(2r + 1) fingerprints, for a total of O(r(2r + 1) log 2 |m|) bits before sampling. Now note that the sampling strategy described in Step 6 matches our algorithm for the streaming problem 6 . While in the streaming problem, we attempt to obtain a 1 at unit cost per query, here node p is attempting to select a correct node at the cost of listening to |m| bits per selection. Theorem 7 guarantees that a correct message is obtained at an expected cost of O(lg (k) (n/2) + k) bits where n = (2r + 1) 2 . Therefore, the total expected cost is O(r 2 log 2 |m| + |m|(lg (k) (r) + k)).
Note that |m| need not be very large in order to make the probability of a collision negligible. For instance, if |m| = 1 kilobyte, the probability of a collision is already less than 10 −30 . Finally, it follows immediately from the above theorem that for a message m of size |m| ∈ ω(log 2 N ), the bit-reduction algorithm achieves a substantially lower communication complexity.

Future Work and Conclusion
We have designed new algorithms for reliable broadcast in radio networks that achieve near optimal energy savings. These algorithms consume significantly less power than any other algorithms for this problem of which we are aware. In the process of designing and analyzing these algorithms, we have defined and studied a novel data streaming problem, which we call the Bad Santa problem. Several open problems remain including: Can we close the gap between the upper and lower-bound for the multi-round Bad Santa problem? Can we be robust to Byzantine faults caused by a computationally unbounded adversary and still reduce power consumption? Can we generalize our techniques to radio networks that are not laid out on a two dimensional grid? Are there other applications for the Bad Santa data streaming problem both in and outside the domain of radio networks?