The Wake-Up Problem in Multi-Hop Radio Networks Marek Chrobak Abstract We study the problem of waking up a collection of processors connected by a multi-hop ad-hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. Each node in the network wakes-up spontaneously, or it is activated by receiving a wake-up signal from another node. All active nodes transmit the wake-up signals according to a given protocol . The running time of is the number of steps counted from the first spontaneous wake-up, until all nodes become activated. We provide two protocols for this problem. The first one is a deterministic protocol with running time . Our protocol is based on a novel concept of a rotationtolerant selector to which we refer as a synchronizer. The second protocol is randomized, and its expected running time is , where is the diameter of the network. Subsequently we show how to employ our wake-up protocols to solve two other communication primitives: leader election and clock synchronization. 1 Introduction We define an ad-hoc multi-hop radio network as a directed, strongly-connected graph with vertices, whose nodes represent processors and outgoing edges represent their transmission ranges. The execution time is divided into discrete time steps, same for all processors. We assume that each processor is assigned a unique integer identifier from a range of size . The processors know the range of the identifiers, but they do not know the network's topology. We consider the fundamental problem of waking up the processors of an ad-hoc multi-hop radio network. Initially, all nodes are assumed to be asleep. Each node in the network can wake-up spontaneously, or can be activated by receiving Department of Computer Science, University of California, Riverside, CA 92521, USA. Research supported by NSF grants CCR-9988360 and CCR-0208856. Email: marek@cs.ucr.edu. Dept. of Computer Science, University of Liverpool, Liverpool L69 7ZF, UK. Email: leszek@csc.liv.ac.uk. Research supported by the EPSRC grant GR/R84917/01. Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02­ 097, Warszawa, Poland, and Max-Planck-Institut fur Informatik, Stuhlsatzenhausweg 85, 66123 Saarbruecken, Germany. Email: darek@mimuw.edu.pl. Research supported by KBN grant 4T11C04425. Leszek Gasieniec ¸ Dariusz Kowalski a wake-up signal from another node. Once a node is activated, it starts executing its wake-up protocol . This protocol dictates during which time steps will transmit a wake-up signal. In our model, the network does not have a global clock, so depends only on the local clock of (the number of steps since activation), and possibly additional information received earlier from other nodes. The wake-up signal from is sent, during the same time step, to all outneighbors of . However, an out-neighbor of receives this signal only if no collision occurred, that is, if no other inneighbor of transmitted at the same time. In other words, we do not assume any collision detection capability. The running time of is the number of time steps, counting from the first spontaneous wake-up, until all nodes become activated. While other important communication primitives, such as broadcasting (one-to-all communication) and gossiping (all-to all communication), have been explored extensively in the context of ad-hoc multi-hop radio networks, e.g., see [1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 16, 18], the wakeup and synchronization problems were studied primarily for one-hop networks (i.e., in the presence of a complete graph of connections). For one-hop networks, Gasieniec ¸ et al. [11] presented a deterministic protocol with running time . They also gave a probabilistic argument showing that there exists a wake-up protocol with running time . Later, Indyk [12] showed that the same proof can be turned into a constructive argument, with only a slight increase in the running time. In the randomized case, in [11] one can find an algorithm that, for any given , completes the wake-up process in time , with probability at least . This result was recently improved by Jurdzinski and Stachowiak [13] who gave a protocol with ´ running time . Note that broadcasting can be reduced to wake-up, in the following sense. Given a wake-up protocol , we can use it to perform broadcasting by waking-up only the node that wants to initiate the broadcast, and then using the transmissions of to transmit the broadcast message instead of the wake-up signal. Therefore the wake-up problem can be thought of as a generalization of broadcasting. Our results. We study the wake-up problem in arbitrary ad-hoc multi-hop radio networks (far more general than the one considered in [11, 13]), when the network has an arbitrary topology and, further, this topology is not known to Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 992 B@ CA9 3 3 ""9GE¦ ¦ PIHFD876¨£§¥ ¤ 3 ¤ 4 3 ¢ "9 E £ ¦ P"VUGHF¦T876587%§¥ 9Q SRE ¤ ¤ ¤ "#(876%£§¥ £' ¦ "£ #5 ' %£§¥ ¦ 3 3 4 ¡ W " £ © ¦ #! ¨£§¥ £ ¤ £ $ "£' ¦ #)( &%$§¥ ¤ "¦ #%£§¥ 1 2 0 2 Preliminaries Radio networks. A radio network is a directed, strongly-connected graph with vertices that represent processors. To simplify presentation, throughout the paper we assume, without loss of generality, that is a power of . If there is an edge from to , then we say that is an out-neighbor of and is an in-neighbor of . The set of all in-neighbors of is denoted by , of simply , if is understood from context. Each node is assigned a unique identifier , also called a label. The labels are integer numbers from an interval min . Initially, max , where max min each node knows only its label and the bounds max , min . In , since otherwise a node the paper we assume that min instead of label can use an auxiliary label min for execution. In the construction of synchronizers and wakeup protocols, we further simplify the notation by assuming that the label set is , so that we can identify nodes by their labels. (Note that we cannot make this assumption in the leader election and synchronization 993 D 3 V " !(§ ¦ D " ¡ PVV ¤¦ E Q 4HFD D GE D B) § 3 ' 1 " C&" BA@8 5 5% 9 7 5 6 2 431 3 " ¡ P¦ X ¤ R S T¡P 3 0 ¤ ¤ ¤ R¡ S QP 3 § " ¡ P¦ § ¤ D D EU &H" ¡ P¦ § ¤ 4 ¦ §¦ D B ¤ ¡ 4 W D 3 " ) 0 B " (C" BA@7 '% 9 I R S T¡P R S ¡ PP ¤ I 3 '%" " (&$" #!¦ W D 3 4 4 D ¦ the algorithm. We provide two protocols for this problem. First, we give a probabilistic construction of a deterministic wake-up protocol with running time . Our construction works in several stages. During the first stage, we construct certain combinatorial structures called synchronizers. Later, we take a random protocol that consists of a synchronizer followed by a random sequence of transmissions, where each transmission is executed with probability . We prove that, with very high probability, this random protocol completes the wake-up task in time in so-called path graphs, implying, via the probabilistic method, the existence of a deterministic protocol for path graphs with the same running time. Finally, we prove that works, in fact, for arbitrary graphs. As our second result, we give a randomized wakeup protocol whose expected running time is , where is the diameter of the network. Completing the wake-up alone is necessary but not sufficient for effective communication between the processors. Thus, we subsequently study two other communication primitives: leader election and clock synchronization. In the leader election problem, we want to designate one node, typically the one with minimum label, as the leader. All nodes have to be informed about the leader identity (label). In the clock synchronization problem, we require that, after the completion of the protocol, all nodes agree on some integer value (typically, the local time of one selected node) as the current global time. Assuming that all node labels are integers drawn from an -size range, we show that both problems, leader election and clock synchronization, can be , and in achieved deterministically in time time with randomization. protocols, because then node could be always selected as the leader, making both problems trivial.) The execution time is divided into discrete time steps. Since our focus is on communication, we assume that processors have unlimited computing power and can perform arbitrary computations within one time step. However, only one transmission or message receipt is allowed in one time step. By a wake-up schedule we mean any vector , where denotes the time step in which wakesup spontaneously. For any set , by we denote the earliest wake-up time step in , that is . For our convenience, we will be assuming that . A node with is referred to as a start node. Note that there may be several start nodes present. A node is called active at time if it either wokeup spontaneously or if it was activated by another active node by receiving its wake-up signal in some time step . A wake-up protocol is a function that, for each label and for each step , given all past messages received by the node with label , specifies whether will transmit the wake-up signal in step (since its activation). A message transmitted in step from a node is sent instantly to all its out-neighbors. However, an out-neighbor of receives in time step only if no collision occurred, i.e., if the other in-neighbors of do not transmit in step at all. Further, collisions cannot be distinguished from the background noise. If does not receive any message in step , it knows that either none of its in-neighbors transmitted in step , or that at least two did, but it does not know which of these two events occurred. and a wake-up schedule , by a Given a network wake-up network we will mean the pair . The wake-up network, together with a wake-up protocol fully determine the state of the network during each time step. We call the triple an execution of protocol in the wake-up network . Let acttime denote the activation time step of node , that is, either or the time when received a wake-up message, whichever comes first. Note that, by the definition of active nodes, is active for the first time at step acttime . By ActSet we denote the set of all active nodes in time step . We will often simplify this notation and omit the arguments that are well understood from context, writing acttime , ActSet , etc. The running time of a wake-up protocol is the smallest such that, for any wake-up network , all nodes are activated by time , that is ActSet . Protocols for leader election and synchronization, as well as their running times, are defined in an analogous manner. We remark here, however, that in our wake-up and leader election protocols, nodes only transmit wakeup signals to its neighbors; no other messages are used. " £ © ¦ #! ¨£§¥ " #£ ' %$§¥ ¦ " %3¦ £ ¦Q § ¦ ¦¦ "¦ #¨£§¥ 3 § ¨¦ " #£ ' #%£§¥ © ¦ 3 £ E Q £ E B © " ¨3¦ ¥£ ¤ ¦ Q £ B 3 ¦ "¦ #%£§¥ 4 ¦ ¡ 4 ¦ © ¦ §¦ 3 "¦ #£ ' 87 %$§¥ 4 3 ¤ ¤ " £ © ¦ #!87#P¨£§¥ £G HUE $ ¡ ¢ 3 (1) We define a random protocol and a class of graphs that we call path graphs. We also define a slightly different communication model for those graphs that we call the restricted model. P P (2) We show that, with probability exponentially close to , will complete the wake-up task in time , according to the restricted model, for an arbitrary -vertex path graph and a wake-up schedule. (3) Using the error bound on the failure probability in (2), we show that there exists a deterministic protocol for path graphs with running time , in the restricted model. (4) Finally, we prove that (3) implies that our protocol works in fact also in arbitrary directed graphs, with running time . 994 " £ © ¦ #! #%£§¥ " £ © ¦ #! %£§¥ £ Q E RE E ¤H5 2 IC&" H 5% 5% CC" @ D@ @ B PB AV ¢ F GE EAV ¢ 9 % B CE AV ¢ £ " 2 " 9 "#£!87#P¨£§¥ © ¦ E "! ¢ D 1 D "#&81 &7© E 1 6)U # ) &4D 0 5§ 5 5¦& 5 #3 2 1& 10 ¨ S()1 ( G 1 '(C" " ¡© % ¨ " #£!87#©%£¦§¥ " § H¥ ¨£¦ ¨ HE B G E " Proof. We use here a probabilistic argument. Let , where is a constant to be specified later. . Without loss of generality, we can assume that For all and , independently, assign with probability , and otherwise. We show that, with very high probability, is an synchronizer. Initially, we fix a set of nodes with and a wake-up schedule . Pick with . For any given time , let be the set of nodes in that are "awaken" at time . By the independence of the random variables , we have 4 A Deterministic Wake-Up Protocol In this section we use the probabilistic method to show the existence of a deterministic protocol that completes the wake-up task in -vertex directed graphs in time . We proceed in four steps: § ¨ $ ¢ % § ¨ % # £ "£ ¦ #!87 ' ¨ §¥ £ G ¨ L E M M A 3 . 1 . For each and -synchronizer with § there exists an . e.g., for a constant than , there exists a . . Since this probability is less -synchronizer with r w ¥y xW E ¥y w W Ey w uu W £ W uvd "#£!87 ' ¨ ¢¦ ' £ $ ¨ " § t ¨£¦ ¢¢ G G $ W ¦ d W " § ¢¦ ' £ £ !87 ' E W We assume here that , for . One can interpret as a transmission protocol, where indicates that the node transmits in step . Thus the condition states that, in at most steps after the first node in wakes-up, there will be a time when exactly one node in transmits. " # W & h For any set of cardinality at most , and for any wake-up schedule , there exists , where , such that, . The probability that violates the definition of the -synchronizer can be estimated by multiplying the above probability by the number of choices of and . Note that we can restrict our considerations only to those wake-up schedules with , for each . For an arbitrary wake-up schedule and , we define another wake-up schedule as for , and for . Then satisfies the condition for and , iff satisfies for and . It follows that the number of all relevant wake-up schedules is not greater than . The number of ways in which can be chosen is at most . Thus the probability that is not a -synchronizer is at most ¨ " § H¥ ¨£¦ r s W rp ' £ G t' Gq¨ W 1 " § ¢ ¦ G HE U i§¦ " E S 1 " ¦ © 1 I¦ "© 1 G & 0 B E" 1 C § 5 Q " © A @7 E" E 9 21 1& 4g0 § fG ) G B " 1 E ' e # ¨ " § ¥ %£¦ 0 d for W ¦ d G ¤ In this section we introduce a new type of selector-like structures (for the definition of selectors see, e.g., [7]) which tolerate arbitrary transposition (rotation) of transmission protocols used by the nodes of the network. We refer to the new type of selectors as synchronizers since they are used to coordinate the work (transmissions) of nodes whose local clocks lack synchronization. Let , where each is a binary 0-1 sequence of length . We say that is a -synchronizer if it satisfies the following property: ' ¢ " ¦ ¥ " ¢ "¤ S Q 5% CC" 3 Synchronizers G B§ c U # GD 5 ¢ 9 P ¦ ¨ Q E ¢ RE ¢ For clock synchronization, messages are numerical values representing the global time. Therefore, using again the independence of the "! , 5 b ` @ # E aY" V GD U" 5 ¢ £ ¨ " § U E ¤ D US VT¨ W XS B § E¢ ¨ Q Q¨ E RE E " § 0 ¢ Q R¨ "V ¨ B "! 5% C&" £ '% (&" " ¡© % % 2 431 " ¦ © ¢ $ E "! &'0 £ ! ' ¨ 1 1 §U 5 " ¦ © ¨ " § H¥ ¨£¦ ¨ " § H¥ ¨£¦ E "! ¢ ¢ $ Thus the difference between the standard and restricted models in path graphs is that the nodes , for , cannot be activated by their in-neighbors in even if exactly one of them transmits. (Nodes , for cannot be activated in either model, by the choice of .) Given a protocol , we refer to the execution of under the restricted model on as a restricted execution, and we denote it , where the asterisk indicates that this execution takes place under the restricted model. Recall that is the length of our synchronizer and where is a random 0-1 sequence of length , in which is a constant from the proof of Lemma 3.1, such that each bit is chosen, independently, to be with probability . and with probability . Then is a random protocol. We refer to the sequence as the L E M M A 4 . 1 . Let be an arbitrary path wake-up netS-stage and as the U-stage of . work with vertices from . Consider the restricted execution Path graphs and restricted executions. A directed . The probability that does not activate the graph is called a path graph if it has the following of on target node of in time is at most , for structure: The nodes of can be partitioned into sets , some constant . , called layers, each with a distinguished node . The edges of are of the form , where Proof. Let be the layers of and and . We refer to as the depth of . The be the main path. The activation time of a layer is called the main path of . Node path is a random variable that is either or the time when is the start node and is the target node (see the figure and receives the wake-up signal from , below). If is a path graph and is a wake-up schedule, whichever comes first. we will refer to the pair as a path wake-up network. Whenever the head index increases, we call it an advance. Recall that is assumed to wake up at time . L2 L1 L0 L3 We want to bound the probability of failure, i.e., that is L4 v2 still not woken-up at time . v1 v4 target start v0 We group all time steps into two categories: v3 S-steps: time steps when at least one node in a head layer executes its S-stage, and 995 § £ D § (Act1) , or Suppose that was a head layer for some period of time, starting at time . If the number of active nodes in at time is at most then we say that is fast. Otherwise, we call slow. (We emphasize that the notions of fast and slow layers are relative to a particular execution of ; the same layer can be slow or fast, depending on the outcomes of random choices before .) We now make two important observations. First, if is fast then, since is a -synchronizer with , an advance to will occur during the time period with probability . The second observation, following from the previous one, is that U-steps occur only when the head layer is slow, and thus has size at least . Now we look at the execution of on globally. The total number of S-steps is at most . ! ! "#!87#P¨£§¥ £ © ¦ R P ¦ P ¤ £ § § ¨ ! $" ¥9§ § E $D E ¨ " § H¥ ¨£¦ P ¤ £ ¤ E $D ! ! § ! § § 5 a§ § g U ED U ED E U ED ¤ @ £ In path wake-up networks, we only consider wake-up schedules with as the start node, that is and for . The wake-up task is also different: our objective is to wake-up only the target node , not necessarily all nodes. We will consider a restricted communication model for path graphs that differs slightly from the standard model described in Section 2. Let be a path graph and a wakeup schedule. Assume that the sets of active nodes are already defined in all steps (as in a standard radio wakeup execution, if a node becomes active, it remains active through the end of the execution). We denote by the greatest index of an active layer (that is, a layer with at least one active node) at step . We refer to as the head layer at step . A non-active node becomes activated in step if one of the following cases apply: U-steps: time steps when all active nodes in their U-stage. execute ¤ ! ( )R B ¦ ! P ru 3 § 1 2 V &G ! £ $" § " ¦ D " £ ¦ #! © ¨£§¥ W 64 75 ! V! E U V '5" !@ 3 " £ © ¦ #! #¨£§¥ ¦ V ! ! R 0P ¦ 3 3 D D § B@3 ! ¤ 3 § £ !87#P ' £ $" ¦ R 0P ¦ D 33 § E Q5" V ! § ! 3 3 $" ¥8§ R P ¦ We point out here that applying the probabilistic method to path graphs, rather than directly to arbitrary graphs, is crucial, since the number of path graphs is substantially smaller than the number of arbitrary directed graphs ­ roughly instead of . Random protocol. We define a random protocol as follows. Let be a -synchronizer with and . The existence of has been established in Lemma 3.1. For each we define a random 0-1 sequence as r (Act2) step . and exactly one node in transmits in $ $ § ! '(%&" " " © E '£ £ § V 3 B § ! ¦ $" %#§ " ¤ ! 3 ¨3¦ ¦ & " ¥" " ¤ " 0 £ ! ' £ § '% (C" $ " © ¨ " § t ¨£¦ 3 ! § " £G UHE Q E $ D R P ¦ D E ¦ 3 ¦ ¦ 3 ¤ 3 3 §& $ " GB ! ©c3 § ¨& 3 ! ! $ B " 3 D ¢ £¤ 3 ` 3 " " r ¡r ¤ ¦ ¢ ¤ £ B " B D ¦ ¤ % h £G HHE § 3 ¨ for some constant . Consider one U-step, say the th one, for some fixed execution history (that is, all random choices up to this point). At this step, the head layer has active . Since we can choose arnodes and all these nodes transmit with probability . The for large enough and bitrarily large in Lemma 4.1, this implies that there exists probability of an advance is the probability that exactly one a deterministic protocol with running time of them transmits, so that completes wake-up for any -vertex path graph and any wake-up schedule, under the restricted model. (4.2) P The last inequality holds because it is true for and is a non-decreasing function for . Therefore P . The idea behind the proof of (4.1) is this: we can think of the 's as a sequence of Bernoulli trials in which the probability of a success (an advance) is . Then the probability that in this process the number of advances in U-steps is less than can be bounded by , for some constant , which is the bound we are after (however we have to assume to assure that the expected number of advances is ). The flaw in the above argument is that the advance events (variables are not fully independent, and thus this is not truly a Bernoulli process. To make the argument rigorous, we introduce independent random variables , where P , and assume that . It is not difficult to show that for all and we have P P . Then, by the Chernoff bound (see [17], for example), we get: T H E O R E M 4 . 1 . There exists a deterministic protocol that completes the wake-up process in -vertex directed graphs in time . Proof. We prove that protocol from Lemma 4.2 satisfies be the running time of the theorem. Let protocol from Lemma 4.2, in the restricted model, on any path wake-up network , where the vertex set of is a subset of . We show that completes the wake-up in any graph with vertex set under any wake-up schedule in time . Fix a wake-up network , and denote by the start node, where and for all . Let be some arbitrary but fixed target node , and let be the shortest path from to . We define a subgraph of as follows: The vertices of are all nodes , and all in-neighbors of nodes . The edges of are all edges in such that and for . Clearly, is a path graph with main path . As usual, by we denote the layers of . Define a wake-up schedule for nodes by acttime , the activation time of in under protocol and wake-up schedule . We compare two executions of : 996 § ¦ (R ¥¦ P § L E M M A 4 . 2 . There exists a deterministic protocol that, under the restricted model, for any wake-up network with at most nodes, activates the target node of in time . (ii) , the execution of on with wake-up schedule , under the restricted model. ¡ R S ¡ P (i) , the execution of schedule , and completing the proof. % ' ( % ) " # ¦ ¦ B @ ¦ 3 ru £ G B P ' £ ! " £ © ¦ #!87#P¨£§¥ £ 1 ¤ ¡! 9 P for some in with wake-up " £ © ¦ #!87#P¨£§¥ ¡4 " ¡ T ¦ § ¦ 4 & §¦ § § 3 3 ¤ 3 3 §@¦ " )@ ¡ G & " 3 ¨4¦ §¦& @©74 ¡ " ! 3 ¨4¦ §¦ 3 ¤ 3 3 3 § @¦ ¡ §¦ 3 3 3 3 ¤ 3 3 ¡&3 3 ¡&4 B% B § 3 R S ¡P " £ © ¦ #!87#%£§¥ W ¦ R ¦P " £ © ¦ #! #¨£§¥ W r £! © £ £ ¢ ! ' r ¨ % & u £ u 1 1 E £ £ # $ £ @ ' $ G r" W ¢¦ r £ G 3 ' " £ © ¦ #5 #¨£§¥ $ ¨ ru ' 1 £ £ £0 ¤ £ 0 ' £ ' ¤ % $ & ! ru £G UHE £ 1 ¤ £ ' £ ' % ru § 0 ¤ G % £ ! ¤ ' £ ¢ " G G G!1 ¤! P ' £ ' ¡E ! @ 5 £ RE £ 0 QE "E ¤ ¥ ¡ 1 B ' £ ' ' £ ¤ % ' £ "! 1 P ' £ ' £ £ ¤ ¦ §% ! B@ % ¤ 1 !1 5E ! 1 " £ G@ E ¦ " #UHE Q F0 ¨ © $ ¤ ¤ ¢ 3 5 ¡! ¢ ( Y 9 (4.1) P G" GB r" W ¦ ¢ E r £ £ ! © £ 0 ! " W W ¢ G E W U £ £ During these S-steps, will complete advances from all fast layers in its execution with probability . Since each slow layer has size at least , the number of slow layers in any execution cannot exceed . Let be a random variable such that if there is an advance in the th U-step, and otherwise. Thus, it is sufficient to prove that ! Proof. Let be the running time from Lemma 4.1. Each path graph has out-degree , so the number of -vertex path graphs is at most . We only need to be concerned with wake-up schedules that satisfy , for all . There are at most such wakeup schedules. Thus, by Lemma 4.1, the probability that does not complete the wake-up during a restricted execution on some -vertex path graph and some wake-up schedule is at most 1 P ' £ ¤ £ 1 E E ! 1 B r ¦ 3 § E ! 1@ ¤ ¡! r ¦ " EB© § £ ¦ We start with the following technical lemma from [13]: T H E O R E M 5 . 1 . Let and let be any wake-up network with nodes and diameter . With probability at least , completes wake-up in in time . 997 ! % % ! We would like to point out to the reader that the above proof is not valid for all protocols, as we strongly use the fact that in our protocol the active nodes do not use any information about how they have been activated (spontaneously or by a wake-up signal). D 4 HG !¢ V £ D $ 4W V § & 4 £ $ §£ 3 %§ B 5 % § D@ § B (§ D E §U D @ ! (§ D 3 E UD ¡ 9 © !3 ( # @V " § ¦¦ " 9G F"VU%£¦T 6£! &$ A¥ $ ¦ " Q¦ V ¡ ¤ ¥" ! ¨R¥£ 3¦ ¤ © V! ¦ U (§ D @&§ D © " # (§ D 3 E U D @ § 6 !3 E U D @ 6§ 3 ¡ (§ D Q § D ¨ !C A @7 % 9 (§ D §¦ E U D 6§ E U D §D § 3 E U V£ E U V! " 3 R S ¡P © !3 E UD ( R § ¦ P R S ¡P R S ¡ P E UD § @¦ £ 87D © E U &£ E U V ! ` " V W W §© V &£ V ! R S T¡P D " V£ "9 F"VUG£%¦ 6587 $ §¥ £ ¦ D R § 0P ¦ V! RS ¡QP © 9QE £ Proof. We divide the execution of into stages, where stage is simply the -th iteration of the for loop. By we denote the total execution time of (for a single node). Fix a wake-up network , and consider an execution of on . Let be the start node (the one that wakes up first). For any node , let acttime and acttime . Thus is the time it takes for to become activated since the time when the first of its in-neighbors gets activated. Call a node an obstruction if, during the execution of , we have but . If there is no obstruction, then, clearly, the execution of completes after steps. Thus it remains at most to prove that the probability that there exists an obstruction during an execution of is at most . Consider some fixed node , and fix some value of . To simplify notation, we can in fact assume that . If , then P , and we are done, so we can assume that . We now need to estimate the probability that will receive a wake-up signal from in at most steps. For , let be the probability that transmits at time (that is, if is in stage at time ), ! ! % % ! ! ! W Then ¢G !¤ ¡! ¨ ' $ R S T¡P ¤ G' ¤ % " QE RF¦ ¤ B@9 ! W 5 ¤ L E M M A 5 . 1 . [13] & Suppose we , such that have numbers, . £ UG ¢ "G ¢ 9I¨£¦ 87 C¢ E Q £ 87 E B for do repeat times T R A N S M I T with probability B @9 ' %B¦ ! ¤ W ¡! 3 © W ' ¤ © W For any , if (4.3) holds for each time , then the activation times of in both executions are the same. This is true, in particular, for the target node . Since was chosen arbitrarily, the theorem follows from Lemma 4.2. Thus, to complete the proof of the theorem, it is sufficient to prove (4.3). We now prove invariant (4.3). Note first, that for each , its activation times in both executions are the same, acttime acttime . Thus invariant (4.3) holds for nodes . The implication is also immediate from the definition of . It is thus only sufficient to prove implication for . The proof is by induction on time step . For , invariant (4.3) holds by the very definition of . Suppose that (4.3) is satisfied up to step . We show that it is also satisfied for step . It follows directly from invariant (4.3) applied to steps that the activation times (up to step ) of active nodes in are the same in both executions and . Consequently, any ActSet performs the same action in step in both executions. does not depend on whether woke up (This is because spontaneously or was activated by another node.) As before, let be the head layer of at time . We define analogously index to be the largest index of a layer that is active at time in . Note that , by invariant (4.3) and the definition of a path graph. For any , it follows directly from node , where the definition of and rule (Act1) of the restricted model that is activated in step of execution iff it is activated in step of execution . Consider , for , and suppose that is activated in at time . If , then is activated in as well, by the definition of . It is sufficient to prove that is not possible. Towards contradiction, suppose , that is, was activated using rule (Act2) by a wake-up signal from some node in . Then, by the definitions of and , and ActSet also by invariant (4.3), we have ActSet , and all nodes in this set are in the same state in both executions. It follows that would have received the same message in in step as well ­ contradiction with the assumption . This completes the proof of invariant (4.3). © ( # @V " § ¦¦ % We claim that the following invariant holds in each step : (4.3) for all ActSet iff ActSet 5 A Randomized Wake-Up Protocol In [13], the authors presented a randomized wake-up protocol for complete graphs. We now give a randomized MonteCarlo wake-up protocol for general multi-hop radio networks. receives on input a parameter , which is the bound on the probability of failure. Protocol . The pseudo-code of the protocol for an arbitrary node follows: ( # § ¦ V "¦ R S ¡ P B D D &4 " ¡¦ ¢ Q ¦ '4 & " ¡ ¦ D 4 D D 3 & % & f 4 E UD 4 3 " Q¡V ¦ D ( # @¦ ¦ "§ E &U D & 4 % 4 % § " ¡¦ (R § ¦ P D E 8 ¦ § @¦ ¤ ! § & Q§ ¦ ¤ ¥ 4 & § " ! ¨3¦ ! ! 4 // stage starts ! ¦ ! ! § 3 3 3 3 ¨¦ ¥§ & £ 4 (5.4) for 6.1 Leader Election The leader election protocol consists , of two stages: wake-up stage and election stage. We first at describe both stages informally, and then give a pseudocode for the complete protocol. Wake-up stage. In this stage all nodes become wokenup. Each node , once it becomes activated, starts executing its wake-up protocol . After completing this protocol, suspends itself for time steps. The purpose of this Then the probability that will not receive a wake-up signal in steps is at most . We conclude suspension period is to ensure that the wake-up stage does that the probability that is an obstruction is bounded by not overlap with the election stage that follows. Election stage. In this stage, all nodes in the network as well. Therefore the probability that there exists an select a node that possesses the smallest label as the obstruction node during the execution of is at most leader. The selection process is performed in rounds, where in round , for , the th highest bit of is announced. At the beginning of round all nodes know the top bits of . Let completing the proof. be the string consisting of these min label We can modify to obtain a Las Vegas protocol with bits. Nodes for which min label are low expected running time. Let be with , potential candidates for the leader. If such a candidate node so that the running time of is . The also has a on the th bit, it informs other nodes about its protocol has three stages. First, we run , then we let existence by initiating a wake-up process. If no wake-up each active node suspend itself for steps, and then we run process is initiated in round , by the end of the round all a deterministic wake-up protocol, say protocol from the nodes conclude that the th most significant bit in is . previous section. Call this new protocol . We obtain: The difficulty that we need to overcome is that, due to lack of synchronization, the division into consecutive rounds must be based on the local clocks. It means that T H E O R E M 5 . 2 . Let be any wake-up network with nodes. Protocol described above completes wake-up in very likely there will be some time overlaps (of size at in expected time and worst-case time most - the maximum offset between the activation times of any two nodes) between neighboring rounds of different . nodes. In order to avoid simultaneous transmissions of signals belonging to two different rounds, we will pad each 6 Leader Election and Clock Synchronization round with two wait periods of length , one at the beginning In the leader election problem, we want to designate one and one at the end. More specifically, every round is split into node as the leader, and to announce its identity to all nodes four sub-rounds, each of length . If a node is a candidate in the network. In the clock synchronization problem, for the leader and initiates the transmission process by itself, upon the completion of the protocol, all nodes must agree this is always done in the beginning of the second sub-round. on a common global time. In this section we show that On the other hand, can be activated to start its wake-up any wake-up protocol (deterministic or randomized) can process by another node at any time during the first, second be transformed into a leader election protocol or a clock or third sub-round. synchronization protocol with only a logarithmic overhead. Leader election protocol . Below, we give a pseuLet be a wake-up protocol. For any node , let docode for the protocol executed by a node . We use be the instance of executed by node . (Formally, the small capitals font, S TA RT, E X E C U T E, etc, for commands execution of depends on the label, but, for simplicity related to timing. Variable clock measures the local time of a of notation, we write instead of .) Fix , and by node. denote the running time of , if all node labels Thus, by Lemma 5.1, for each time the probability that receives a wake-up signal from time is % 998 B 3 ¡E Q B B B ¦ § 5 3 @ 5 ¡E ! BB B ¦ Q @ § §¦ §¦ E Q #£ T87 E B " ¦ " ¦ #£ T87 (3 G E ¦Q § ¨¦ 3 BB E U " " ¦ 3 5 ¦ ¦ BB " ¦ § @ ! § ! § §¦ 4 " 3 " #£ ¦ 3 B " £ 3 ¦ and let . We have , , and is non-decreasing. By the definition of , for any , we have , since in steps the active nodes will double their probability of transmission, and each other node contributes at most to . Choose the largest for which . Then and . We conclude that © ' ¢"¤¦ 3 ' ¢ E ¢" ¤¦ 3 ¨ ¦¤¨ % © §¥!2 ¨ !C % ' % " V $ 2 Q F¦ E V $ ¤ D §£ 3 E§( UQE D B E U E D E$D D Q ' E Q U E D E D D ¢ G V G ¤ G E U ¤ HV ¢ G ¤ ¢ HV ED § £ " #£ ' &%$§¥ W ¦ £ 9 © ¤ ' %¢ 7£ ¤ ' 9 G % ¢ 3 £ ¡ ' HV V UHE ¤ £G E U V¢ G © B ¢ r © E 3 ¨ y w " ' !£ G ¦ © "#£)'(87 %$¦§¥ E R S T¡P ¤ W © ¢ ¤ H V ¢ © r % V ¢ V $ § ! % ¥y w are drawn from the range min max , where max min , for some constant . Note that our wake-up protocols described earlier in the paper satisfy this requirement. Recall that, without loss of generality, we assume that . We can then think of the labels as binary strings min of length , and by we denote the string consisting of the bits of on positions , counting from left to right (that is, highest bits first). ¨!% © '¦ P' " ' !£ ¢ " ' !£ ¦ ¤ ¤ % © " £ ¦ #!87 P© ¨£§¥ R S T¡P Q BB E D V % ! V " #¨£¦ 6.2 Clock Synchronization It is not difficult to extend the leader election protocol from the previous sub-section to perform clock synchronization. We first run . Once a leader has been elected, waits for steps, and then broadcasts its local time to all other nodes using some broadcasting protocol (see, for example [7]). When the nodes perform , they increment their global time counter at each step, to make sure that the correct value is transmitted. (A similar idea appeared in [18].) Denote by the running time of . Thus we obtain: T H E O R E M 6 . 2 . Suppose that is a wake-up protocol with running time , and is a broadcasting protocol with running time . Then and can be converted into a clock synchronization protocol with running time . 6.3 New Protocols Recall that our deterministic wake-up protocol runs in time , randomized protocol in time and with error probability , and protocol runs in expected time . Using the protocols from the previous two sub-sections, the broadcasting protocol from [7] or [10], and any randomized broadcasting protocol in [1, 15, 10], we obtain the following corollary. C O RO L L A RY 6 . 1 . There exist protocols for leader election and clock synchronization with the following performance in -node networks: (a) A deterministic . protocol with running (b) A Monte Carlo protocol with running time and error probability at most . (c) A Las Vegas protocol with expected running time . The randomized Las Vegas protocols in Corollary 6.1.(c) are obtained by taking te corresponding Monte Carlo protocols with sufficiently small error probability, say , followed by a deterministic protocol from part (a). 7 Final Comments In this paper, we initiated the study of wake-up protocols in a general model of multi-hop radio networks where the Note that, in the theorem above, we do not make any assumptions on the wake-up protocol . One detail that we should clarify is that, when we simulate in protocol 999 £ 9 T H E O R E M 6 . 1 . Suppose that is a wake-up protocol with running time . Then can be converted into a leader election protocol with running time . " #£ ' %$§¥ ¦ 9 E© ""9G ¦ £ ¦ FVU%£T876!87&$ §¥ " £ © ¦ #!87#P#¨£§¥ ""9G ¦ £ ¦ PVU¨£D 6! &%$§¥ "¦ F"#£¨I U £ 87 #¨£¦ §¥ " ¦ "#%£U ¦ " #¨£¦ " © ¦ #£ ' 87#P¨£§¥ " #£ ' &%$§¥ ¦ 9 £ © To justify correctness, it is sufficient to show that there will be no interferences between wake-up processes from different rounds. The crucial property used in the argument is that the (global) activation times (in the wake-up phase) of any two nodes differ by at most . This implies, in particular, that two rounds of different nodes can overlap only if they are consecutive and if so, they can overlap on at most time steps. More specifically, the only possible overlap is when the fourth sub-round of a node in round overlaps the first sub-round of another node that is in round . (In our argument, to avoid dealing separately with the wake-up phase, we can treat the wake-up phase as round of the election phase.) If a wake-up process in round is initiated at a (global) time , then all nodes will be activate by time , and they will have completed their transmissions at time . Since wake-ups are initiated at the beginning of the second sub-round, and the local times are shifted by at most , it follows that, in each round , each node will be activated no later than at the end of its third sub-round, and thus complete its transmissions by the end of its round . Fix a node that is first to execute its transmission from round . This means that initiates a wake-up process, and it starts transmitting in the first step of its second subround. But, again, using the fact that the offset between different rounds is at most , by that time, all other nodes completed their transmissions from round . Thus we obtain: ! "¦ #¨£I ! ( 3 ( ! 3 EQ " U ¦ " 8 U¦ ¢ UD © § ¨¦ ¥ SLEEPUNTIL wake up signal (spontaneous or external) S TA RT clock EXECUTE ( steps) WA I T F O R clock min label // empty string for do bit // round , local time is clock if min label then bit WA I T F O R wake up signal or clock else WA I T F O R wake up signal or clock if wake up signal then bit if bit then E X E C U T E ( steps) min label min label bit WA I T F O R clock # ¦ ¦ during the election stage, all nodes "pretend" to be asleep during the wait periods, and nodes that initiate wake-up "pretend" to be woken-up spontaneously. During the simulation of a wake-up process, each node uses an auxiliary clock to simulate a local clock used by . " #£ #¨£¦ " UD £ ¤¢ ¡ ¦ §¥ B § B " 8 U¦ 3 B § 5 B B B ¦ E@ E Q!#£ ¦T E B " 5 @ ¢ ¦ " #%£¦ ! B § 3 B EU D EU time References [17] [1] R. Bar-Yehuda, O. Goldreich and A. Itai, On the time complexity of broadcast in radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences 45 (1992), 104-126. [2] R. Bar-Yehuda, A. Israeli and A. Itai, Multiple communication in multihop radio networks, SIAM J. on Computing 22 (1993), 875-887. [3] D. Bruschi and M. Del Pinto, Lower bounds for the broadcast problem in mobile radio networks, Distributed Computing 10 (1997), 129-135. [4] I. Chlamtac and O. Weinstein, The wave expansion approach to broadcasting in multihop radio networks, IEEE Trans. on Communications 39 (1991), 426-433. [5] B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc and W. Rytter, Deterministic broadcasting in unknown radio networks, Distributed Computing 15 (2002), 27-38. ¨ [6] B.S. Chlebus, L. Gasieniec, A. Ostlin and J.M. Robson, De¸ terministic radio broadcasting, Proc. 27th Int. Coll. on Automata, Languages and Programming (ICALP'2000), LNCS 1853, 717-728. [7] M. Chrobak, L. Gasieniec and W. Rytter, Fast broadcasting ¸ and gossiping in radio networks, Proc. 41st Symposium on Foundations of Computer Science (FOCS'2000), 575-581. [8] A. Clementi, P. Crescenzi, A. Monti, P. Penna and R. Silvestri, On computing ad-hoc selective families, Proc. 5th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM-APPROX'2001), 211-222. [9] A.E.F. Clementi, A. Monti and R. Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, Proc. 12th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'2001), 709-718. [10] A. Czumaj and W. Rytter, Broadcasting Algorithms in Radio Networks with Unknown Topology, Proc. 44th Symposium on Foundations of Computer Science (FOCS'2003), to appear. [11] L. Gasieniec, A. Pelc and D. Peleg, The wakeup problem in ¸ synchronous broadcast systems, SIAM Journal on Discrete Mathematics 14 (2001), 207-222. [12] P. Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proc. 13th [18] 1000 ©© ¡ [16] ¢ ¨ ¦¤ ¢ £¢ ©§¥£¢ topology of the network is unknown and there is no collision detection. Since the lower bounds for the broadcasting (see [3, 16]) apply to the wake-up problem, no randomized wake-up protocol can be faster than . Thus our randomized protocol is within a poly-logaritmic factor of the optimum. However, in the deterministic case, there still remains a substantial gap between the lower bound of and the upper bound achieved by our protocol . Another direction for study would be to develop explicit and efficient constructions of small synchronizers. [13] [14] [15] Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'2002), 697-704. T. Jurdzinski, G. Stachowiak, Probabilistic Algorithms for ´ the Wakeup Problem in Single-Hop Radio Networks, In Proceedings of 13th Annual International Symposium on Algorithms and Computation (ISAAC'2002), 535-549. D. Kowalski and A. Pelc, Faster deterministic broadcasting in ad hoc radio networks, Proc. 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS'2003), 109-120. D. Kowalski and A. Pelc, Broadcasting in undirected ad hoc radio networks, Proc. 22nd ACM Symposium on Principles of Distributed Computing (PODC'2003), 73-82. E. Kushilevitz and Y. Mansour, An lower bound for broadcast in radio networks, SIAM J. on Computing 27 (1998), 702-712. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995. D. Peleg, Deterministic radio broadcast with no topological knowledge, manuscript (2000). " £ ¦ #!87 P© %£§¥ " $G ¦ F" I¨£D %$6 ¦ "£ ¦ #!876¨£6