Broadcasting in UDG radio networks with unknown topology

The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning. It turns out that broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g, which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O (D g) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than ${\Omega (D \sqrt{g})}The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning. It turns out that broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g, which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O (D g) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than W(D ?g){\Omega (D \sqrt{g})} . For the spontaneous wake up model, we design two deterministic broadcasting algorithms: the first works in time O (D + g ²) and the second in time O (D log g). While neither of these algorithms alone is optimal for all parameter values, we prove that the algorithm obtained by interleaving their steps, and thus working in time O ( min{ D + g², D logg}){ O \left( \min\left\{ D + g^2, D \log{g}\right\}\right) }, turns out to be optimal by establishing a matching lower bound.     

On the effect of the deployment setting on broadcasting in Euclidean radio networks

The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane (each station knows its own coordinates). In any given time step, a station can either receive or transmit. A message transmitted from station v is delivered to every station u at distance at most 1 from v, but u successfully hears the message if and only if v is the only station at distance at most 1 from u that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [17] that the time complexity of deterministic broadcasting algorithms depends on two parameters of the network, namely, its diameter (in hops) D and a lower bound d on the Euclidean distance between any two stations. The inverse of d is called the granularity of the network, denoted by g. Specifically, the authors of [17] present a deterministic broadcasting algorithm that works in time O (Dg) and prove that every broadcasting algorithm requires \(\varOmega \left( D \sqrt{g} \right) \) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [17], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a d-spaced grid. Does the latter (more restricted) setting provide any speedup in broadcasting time complexity? Although the O (Dg) broadcasting algorithm of [17] works under the (original) arbitrary deployment setting, it turns out that the \(\varOmega \left( D \sqrt{g} \right) \) lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We establish a tight lower bound on the time complexity of deterministic broadcasting algorithms under the arbitrary deployment setting proving that broadcasting cannot be completed in less than \(\varOmega (D g)\) time. For the grid deployment setting, we develop a deterministic broadcasting algorithm that runs in time \(O \left( D g^{5 / 6} \log g \right) \), thus breaking the linear dependency on g.     

Acknowledged broadcasting in ad hoc radio networks

We consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished source to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the source message, Chlebus et al. [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where n is the number of nodes and D is the eccentricity of the source. Uchida et al. [J. Uchida, W. Chen, K. Wada, Acknowledged broadcasting and gossiping in ad hoc radio networks, Theoret. Comput. Sci. 377 (2007) 43-54] showed an AB algorithm without collision detection working in time O(n4/3log10/3n) for all strongly connected networks of size at least 2. In particular, it follows that the impossibility result from [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] is really caused by the singleton network for which AB amounts to realize that the source is alone. We improve those two results by presenting two generic AB algorithms using a broadcasting algorithm without acknowledgement, as a procedure. For a large class of broadcasting algorithms the resulting AB algorithm has the same time complexity. Using the currently best known broadcasting algorithms, we obtain an AB algorithm with collision detection working in time O(min{nlog²D,nlognloglogn}), for arbitrary strongly connected networks, and an AB algorithm without collision detection working in time O(nlognloglogn) for all strongly connected networks of size n?2. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exists an infinite family of networks for which this algorithm is incorrect.     

A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs

We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NP-hard and various constant factor approximations are known, with the current best ratio of 3. Our main result is a weakly robust polynomial time approximation scheme (PTAS) for UDGs expressed with edge-lengths that either (i) computes a clique partition or (ii) gives a certificate that the graph is not a UDG; for the case (i) it computes a clique partition having size that is guaranteed to be within (1+ε) of the optimum size if the input is UDG; however if the input is not a UDG it either computes a clique partition as in case (i) with no guarantee on the quality of the clique partition or detects that it is not a UDG. Noting that recognition of UDG’s is NP-hard even if we are given edge lengths, our PTAS is a weakly-robust algorithm. Our algorithm can be transformed into an $O(\frac{\log^{*} n}{{\varepsilon}^{O(1)}})$ time distributed PTAS. We consider a weighted version of the clique partition problem on vertex-weighted UDGs that generalizes the problem. We note some key distinctions with the unweighted version, where ideas useful in obtaining a PTAS break down. Yet, surprisingly, it admits a (2+ε)-approximation algorithm for the weighted case where the graph is expressed, say, as an adjacency matrix. This improves on the best known 8-approximation for the unweighted case for UDGs expressed in standard form.     

Deterministic broadcasting time with partial knowledge of the network

We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v. Apart from that, each node knows the maximum degree Δ of the network. One node of the network, called the source, has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well, in at most the same time.

We show trade-offs between knowledge radius and time of deterministic broadcasting, when the knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is Θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radius 1. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal.     

Faster Deterministic Communication in Radio Networks

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than units of time. Moreover, we show a schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log ³ n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log ² n) time broadcasting schedule by Kowalski and Pelc. A preliminary version of this paper appeared in the proceedings of ISAAC’06. F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported by the Research Council of Norway through the SPECTRUM project.     

Analysis of Galerkin Methods for the Fully Nonlinear Monge-Ampère Equation

This paper develops and analyzes finite element Galerkin and spectral Galerkin methods for approximating viscosity solutions of the fully nonlinear Monge-Ampère equation det (D ² u ⁰)=f (>0) based on the vanishing moment method which was developed by the authors in Feng and Neilan (J. Sci. Comput. 38:74–98, 2009) and Feng (Convergence of the vanishing moment method for the Monge-Ampère equation, submitted). In this approach, the Monge-Ampère equation is approximated by the fourth order quasilinear equation −εΔ² u ^ε +det D ² u ^ε =f accompanied by appropriate boundary conditions. This new approach enables us to construct convergent Galerkin numerical methods for the fully nonlinear Monge-Ampère equation (and other fully nonlinear second order partial differential equations), a task which has been impracticable before. In this paper, we first develop some finite element and spectral Galerkin methods for approximating the solution u ^ε of the regularized problem. We then derive optimal order error estimates for the proposed numerical methods. In particular, we track explicitly the dependence of the error bounds on the parameter ε, for the error u^e-u^e_hu^{\varepsilon}-u^{\varepsilon}_{h}. Due to the strong nonlinearity of the underlying equation, the standard error estimate technique, which has been widely used for error analysis of finite element approximations of nonlinear problems, does not work here. To overcome the difficulty, we employ a fixed point technique which strongly makes use of the stability property of the linearized problem and its finite element approximations. Finally, using the Argyris finite element method as an example, we present a detailed numerical study of the rates of convergence in terms of powers of ε for the error u⁰-u_h^eu^{0}-u_{h}^{\varepsilon}, and numerically examine what is the “best” mesh size h in relation to ε in order to achieve these rates.     

Greedy distributed optimization of multi-commodity flows

The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in connection-oriented network architectures. We consider solutions for distributed multi-commodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We provide the first stateless greedy distributed algorithm for the concurrent multi-commodity flow problem with poly-logarithmic convergence. More precisely, our algorithm achieves ${1+\varepsilon}The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in connection-oriented network architectures. We consider solutions for distributed multi-commodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We provide the first stateless greedy distributed algorithm for the concurrent multi-commodity flow problem with poly-logarithmic convergence. More precisely, our algorithm achieves 1+e{1+\varepsilon} approximation, with running time O(H· log^O(1)m· (1/e)^O(1)){O(H{\cdot} \log^{O(1)}m{\cdot} (1{/}\varepsilon)^{O(1)})} where H is the number of edges on any allowed flow-path. No prior results exist for our model. Our algorithm is a reasonable alternative to existing polynomial sequential approximation algorithms, such as Garg–K?nemann (Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, USA, pp. 300–309, 1998). The algorithm is simple and can be easily implemented or taught in a classroom. Remarkably, our algorithm requires that the increase in the flow rate on a link is more aggressive than the decrease in the rate. Essentially all of the existing flow-control heuristics are variations of TCP, which uses a conservative cap on the increase (e.g., additive), and a rather liberal cap on the decrease (e.g., multiplicative). In contrast, our algorithm requires the increase to be multiplicative, and that this increase is dramatically more aggressive than the decrease.     

Performance improvements for network-wide broadcast with instantaneous network information

We study the performance of network-wide broadcasting as a function of the information implicitly available at nodes from neighbourhood transmissions. We term this set of instantaneous information as network information. Our discussion is focused on stateless broadcasting algorithms in which nodes decide on their forwarding behaviour based on the available network information. While stateless broadcasting schemes in the existing literature use various design guidelines that take advantage of specific aspects of the information, we develop a unified analytical model by characterizing the information available during different stages of broadcasting. Thus, our results are applicable to all stateless algorithms. We analyze broadcasting performance in terms of the transmission probability and redundancy of transmissions. Subsequently, we use our results to obtain insights on the feasibility conditions governing algorithm design depending on the network density and costs. While the first part of the work considers ideal channel conditions modeled as a unit disk graph (UDG), we subsequently enhance the model using a quasi-unit disk graph model (QUDG) to understand the effect of dynamic channel conditions.     

Error Analysis for hp-FEM Semi-Lagrangian Second Order BDF Method for Convection-Dominated Diffusion Problems

We present in this paper an analysis of a semi-Lagrangian second order Backward Difference Formula combined with hp-finite element method to calculate the numerical solution of convection diffusion equations in ℝ². Using mesh dependent norms, we prove that the a priori error estimate has two components: one corresponds to the approximation of the exact solution along the characteristic curves, which is O(Dt²+h^m+1(1+\frac\mathopen|logh|Dt))O(\Delta t^{2}+h^{m+1}(1+\frac{\mathopen{|}\log h|}{\Delta t})); and the second, which is O(Dt^p+|| [(u)\vec]-[(u)\vec]_h||_L^￥)O(\Delta t^{p}+\| \vec{u}-\vec{u}_{h}\|_{L^{\infty}}), represents the error committed in the calculation of the characteristic curves. Here, m is the degree of the polynomials in the finite element space, [(u)\vec]\vec{u} is the velocity vector, [(u)\vec]_h\vec{u}_{h} is the finite element approximation of [(u)\vec]\vec{u} and p denotes the order of the method employed to calculate the characteristics curves. Numerical examples support the validity of our estimates.     

Broadcasting in undirected ad hoc radio networks

We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in expected time in n-node radio networks of diameter D, which is optimal, as it matches the lower bounds of Alon et al. [1] and Kushilevitz and Mansour [16]. Our algorithm improves the best previously known randomized broadcasting algorithm of Bar-Yehuda, Goldreich and Itai [3], running in expected time . (In fact, our result holds also in the setting of n-node directed radio networks of radius D.) For deterministic broadcasting, we show the lower bound on broadcasting time in n-node radio networks of diameter D. This implies previously known lower bounds of Bar-Yehuda, Goldreich and Itai [3] and Bruschi and Del Pinto [5], and is sharper than any of them in many cases. We also give an algorithm working in time , thus shrinking - for the first time - the gap between the upper and the lower bound on deterministic broadcasting time to a logarithmic factor. Received: 1 August 2003, Accepted: 18 March 2005, Published online: 15 June 2005 Dariusz R. Kowalski: This work was done during the stay of Dariusz Kowalski at the Research Chair in Distributed Computing of the Université du Québec en Outaouais, as a postdoctoral fellow. Research supported in part by KBN grant 4T11C04425. Andrzej Pelc: Research of Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais.     

Fast message dissemination in random geometric networks

We analyze information dissemination in random geometric networks, which consist of n nodes placed uniformly at random in the square ${[0,\sqrt{n}]^{2}}$ . In the corresponding graph two nodes u and v are connected by a (directed) edge, i.e., u is an (incoming) neighbor of v, if and only if the distance between u and v is smaller than the transmission radius assigned to u. In order to study the performance of distributed communication algorithms in such networks, we adopt here the ad-hoc radio communication model with no collision detection mechanism available. In this model the topology of network connections is not known in advance. Also a node v is capable of receiving a message from its neighbor u if u is the only (incoming) neighbor transmitting in a given step. Otherwise a collision occurs prompting interference that is not distinguishable from the background noise in the network. First, we consider networks modeled by random geometric graphs in which all nodes have the same radius ${r > \delta \sqrt{\log n}}$ , where δ is a sufficiently large constant. In such networks, we provide a rigorous study of the classical communication problem of distributed gossiping (all-to-all communication). We examine various scenarios depending on initial local knowledge and capabilities of network nodes. We show that in many cases an asymptotically optimal distributed O(D)-time gossiping is feasible, where D stands for the diameter of the network. Later, we consider networks in which the transmission radii of the nodes vary according to a power law distribution, i.e., any node is assigned a transmission radius r > r _min according to probability density function ρ(r) ~ r ^?α . More precisely, ${\rho(r) = (\alpha-1)r_{\min}^{\alpha-1} r^{-\alpha}}$ , where ${\alpha \in (1, 3)}$ and ${r_{\min} > \delta \sqrt{\log n}}$ with δ being a large constant. In this case, we develop a simple broadcasting algorithm that runs in time O(log log n) (i.e., O(D)) always surely, and we show that this result is asymptotically optimal. Finally, we consider networks in which any node is assigned a transmission radius r > c according to the probability density function ρ(r) =  (α?1)c ^α-1 r ^?α , where α is a constant from the same range as before and c is a constant. In this model the graph is usually not strongly connected, however, there is one giant component with Ω(n) nodes, and there is a directed path from each node of this giant component to every other node in the graph. We assume that the message which has to be disseminated is placed initially in one of the nodes of the giant component, and every node is aware of its own position in ${[0,\sqrt{n}] \times [0,\sqrt{n}]}$ . Then, we show that there exists a randomized algorithm which delivers the broadcast message to all nodes in the network in time O(D . (log log n)²), almost always surely, where D stands for the diameter of the giant component of the graph. One can conclude from our studies that setting the transmission radii of the nodes according to a power law distribution brings clear advantages. In particular, one can design energy efficient radio networks with low average transmission radius, in which broadcasting can be performed exponentially faster than in the (extensively studied) case where all nodes have the uniform low transmission power.     

Distributed algorithms for ultrasparse spanners and linear size skeletons

We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the tradeoff between time, sparseness, and distortion. All of our algorithms assume a synchronized distributed network, where relatively short messages may be communicated in each time step. Our first result is a fast distributed algorithm for finding an ${O(2^{{\rm log}^{*} n} {\rm log} n)}We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the tradeoff between time, sparseness, and distortion. All of our algorithms assume a synchronized distributed network, where relatively short messages may be communicated in each time step. Our first result is a fast distributed algorithm for finding an O(2^{log* n} log n){O(2^{{\rm log}^{*} n} {\rm log} n)} -spanner with size O(n). Besides being nearly optimal in time and distortion, this algorithm appears to be the first that constructs an O(n)-size skeleton without requiring unbounded length messages or time proportional to the diameter of the network. Our second result is a new class of efficiently constructible (α, β)-spanners called Fibonacci spanners whose distortion improves with the distance being approximated. At their sparsest Fibonacci spanners can have nearly linear size, namely O(n(loglogn)^f){O(n(\log \log n)^{\phi})} , where f = (1 + ?5)/2{\phi = (1 + \sqrt{5})/2} is the golden ratio. As the distance increases the multiplicative distortion of a Fibonacci spanner passes through four discrete stages, moving from logarithmic to log-logarithmic, then into a period where it is constant, tending to 3, followed by another period tending to 1. On the lower bound side we prove that many recent sequential spanner constructions have no efficient counterparts in distributed networks, even if the desired distortion only needs to be achieved on the average or for a tiny fraction of the vertices. In particular, any distance preservers, purely additive spanners, or spanners with sublinear additive distortion must either be very dense, slow to construct, or have very weak guarantees on distortion.     

双环Petersen图互联网络及路由算法

Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.     

Achievable complexity-performance tradeoffs in lossy compression

We present several results related to the complexity-performance tradeoff in lossy compression. The first result shows that for a memoryless source with rate-distortion function R(D) and a bounded distortion measure, the rate-distortion point (R(D) + γ, D + ?) can be achieved with constant decompression time per (separable) symbol and compression time per symbol proportional to $\left( {{{\lambda _1 } \mathord{\left/ {\vphantom {{\lambda _1 } \varepsilon }} \right. \kern-0em} \varepsilon }} \right)^{{{\lambda _2 } \mathord{\left/ {\vphantom {{\lambda _2 } {\gamma ^2 }}} \right. \kern-0em} {\gamma ^2 }}}$ , where λ ₁ and λ ₂ are source dependent constants. The second result establishes that the same point can be achieved with constant decompression time and compression time per symbol proportional to $\left( {{{\rho _1 } \mathord{\left/ {\vphantom {{\rho _1 } \gamma }} \right. \kern-0em} \gamma }} \right)^{{{\rho _2 } \mathord{\left/ {\vphantom {{\rho _2 } {\varepsilon ^2 }}} \right. \kern-0em} {\varepsilon ^2 }}}$ . These results imply, for any function g(n) that increases without bound arbitrarily slowly, the existence of a sequence of lossy compression schemes of blocklength n with O(ng(n)) compression complexity and O(n) decompression complexity that achieve the point (R(D), D) asymptotically with increasing blocklength. We also establish that if the reproduction alphabet is finite, then for any given R there exists a universal lossy compression scheme with O(ng(n)) compression complexity and O(n) decompression complexity that achieves the point (R, D(R)) asymptotically for any stationary ergodic source with distortion-rate function D(·).     

Distributed discovery of large near-cliques

Given an undirected graph and 0 ￡ e ￡ 1{0\le\epsilon\le1}, a set of nodes is called an e{\epsilon}-near clique if all but an e{\epsilon} fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size e{\epsilon}-near clique if there exists an e³{\epsilon^3}-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n ^−Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of size Ω(n/(log log n) ^α ) for some a ? (0,1){\alpha \in (0,1)}. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.     

Lower bounds for the broadcast problem in mobile radio networks

Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any D≦n/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996     

Faster communication in known topology radio networks

This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology of the network. The first part of the paper examines the two communication primitives in arbitrary graphs. In particular, for the broadcast task we deliver two new results: a deterministic efficient algorithm for computing a radio schedule of length D + O(log³ n), and a randomized algorithm for computing a radio schedule of length D + O(log² n). These results improve on the best currently known D + O(log⁴ n) time schedule due to Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Later we propose a new (efficiently computable) deterministic schedule that uses 2D + Δlog n + O(log³ n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time , for any network with the diameter D = Ω(log ⁱ⁺⁴ n), where i is an arbitrary integer constant i ≥ 0, see Gąsieniec et al. (Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity, vol. 3104, pp. 173–184, 2004). The second part of the paper focuses on radio communication in planar graphs, devising a new broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on the currently best known D + O(log³ n) time schedule proposed by Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Our new algorithm should be also seen as a separation result between planar and general graphs with small diameter due to the polylogarithmic inapproximability result for general graphs by Elkin and Kortsarz (Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 3122, pp. 105–116, 2004; J. Algorithms 52(1), 8–25, 2004). The second author is supported in part by a grant from the Israel Science Foundation and by the Royal Academy of Engineering. Part of this research was performed while this author (Q. Xin) was a PhD student at The University of Liverpool.     

Deterministic broadcasting in ad hoc radio networks

We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes know neither the topology nor the size of the network, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. Such networks are called ad hoc multi-hop networks. We study the time of deterministic broadcasting under this scenario. For the model without collision detection, we develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal, and an algorithm for arbitrary n-node graphs, working in time . Next we show that broadcasting with acknowledgement is not possible in this model at all. For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs. Received: January 2000 / Accepted: June 2001     

A fast distributed approximation algorithm for minimum spanning trees

We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time Õ(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any $H\,\in\,[1, \Theta({\rm log} n)]We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time ?(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any . Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal ?(D(G)) time.