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.     

An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges

In this paper, we study fault-tolerant routing in bijective connection networks with restricted faulty edges. First, we prove that the probability that all the incident edges of an arbitrary node become faulty in an n-dimensional bijective connection network, denoted by X_n, is extremely low when n becomes sufficient large. Then, we give an O(n) algorithm to find a fault-free path of length at most n+3⌈log₂∣F∣⌉+1 between any two different nodes in X_n if each node of X_n has at least one fault-free incident edge and the number of faulty edges is not more than 2n−3. In fact, we also for the first time provide an upper bound of the fault diameter of all the bijective connection networks with the restricted faulty edges. Since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., all the results are appropriate for these cubes.     

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.     

Rumor spreading in social networks

Social networks are an interesting class of graphs likely to become of increasing importance in the future, not only theoretically, but also for its probable applications to ad hoc and mobile networking. Rumor spreading is one of the basic mechanisms for information dissemination in networks; its relevance stemming from its simplicity of implementation and effectiveness. In this paper, we study the performance of rumor spreading in the classic preferential attachment model of Bollobás et al. which is considered to be a valuable model for social networks. We prove that, in these networks: (a) The standard PUSH-PULL strategy delivers the message to all nodes within O(log²n) rounds with high probability; (b) by themselves, PUSH and PULL require polynomially many rounds. (These results are under the assumption that m, the number of new links added with each new node is at least 2. If m=1 the graph is disconnected with high probability, so no rumor spreading strategy can work.) Our analysis is based on a careful study of some new properties of preferential attachment graphs which could be of independent interest.     

Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks

We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem which we call the Bad Santa problem. Our results on this problem apply for any situation where: (1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and (2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a \(\Theta(\sqrt{n})\) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log?^? n) times (i.e. in O(log?^? n) rounds each consisting of the n time slots), then listening to O(log?^? n) expected number of time slots suffices. We show that this is near optimal.We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message m, all awake nodes within L _∞ distance r receive m. In this model, up to \(t<\frac{r}{2}(2r+1)\) nodes within any 2r+1 by 2r+1 square in the grid can suffer Byzantine faults. Moreover, we assume that the nodes that suffer Byzantine faults are chosen and controlled by an adversary that knows everything except for the random bits of each non-faulty node. This type of adversary models worst-case behavior due to malicious attacks on the network; mobile nodes moving around in the network; or static nodes losing power or ceasing to function. Let n=r(2r+1). We show how to solve the broadcast problem in this model with each node sending and receiving an expected \(O(n\log^{2}{|m|}+\sqrt{n}|m|)\) bits where |m| is the number of bits in m, and, after broadcasting a fingerprint of m, each node is awake only an expected \(O(\sqrt{n})\) time slots. Moreover, for t≤(1?ε)(r/2)(2r+1), for any constant ε>0, we can achieve an even better energy savings. In particular, if we allow each node to send O(log?^? n) times, we achieve reliable broadcast with each node sending O(nlog?²|m|+(log?^? n)|m|) bits and receiving an expected O(nlog?²|m|+(log?^? n)|m|) bits and, after broadcasting a fingerprint of m, each node is awake for only an expected O(log?^? n) time slots. Our results compare favorably with previous protocols that required each node to send Θ(|m|) bits, receive Θ(n|m|) bits and be awake for Θ(n) time slots.     

Energy-efficient topology control algorithm for maximizing network lifetime in wireless sensor networks with mobile sink

Uneven energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern. Such unbalanced energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of prolonging network lifetime in large-scale wireless sensor networks where a mobile sink gathers data periodically along the predefined path and each sensor node uploads its data to the mobile sink over a multi-hop communication path. By using greedy policy and dynamic programming, we propose a heuristic topology control algorithm with time complexity O(n(m + n log n)), where n and m are the number of nodes and edges in the network, respectively, and further discuss how to refine our algorithm to satisfy practical requirements such as distributed computing and transmission timeliness. Theoretical analysis and experimental results show that our algorithm is superior to several earlier algorithms for extending network lifetime.     

Coloring unstructured radio networks

During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering even the most basic network coordination problems difficult. Before any reasonable communication can take place, nodes must come up with an initial structure that can serve as a foundation for more sophisticated algorithms. In this paper, we consider the problem of obtaining a vertex coloring as such an initial structure. We propose an algorithm that works in the unstructured radio network model. This model captures the characteristics of newly deployed ad hoc and sensor networks, i.e. asynchronous wake-up, no collision-detection, and scarce knowledge about the network topology. When modeling the network as a graph with bounded independence, our algorithm produces a correct coloring with O(Δ) colors in time O(Δ log n) with high probability, where n and Δ are the number of nodes in the network and the maximum degree, respectively. Also, the number of locally used colors depends only on the local node density. Graphs with bounded independence generalize unit disk graphs as well as many other well-known models for wireless multi-hop networks. They allow us to capture aspects such as obstacles, fading, or irregular signal-propagation. A preliminary version of this work has been published in [20] as Coloring Unstructured Radio Networks, In Proceedings of the 17th Symposium on Parallel Algorithms and Architectures (SPAA), Las Vegas, Nevada, 2005.     

On the complexity of distributed stable matching with small messages

We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of unmatched nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable matching problem requires ${\Omega(\sqrt{n/B\log n})}We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of unmatched nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable matching problem requires W(?{n/Blogn}){\Omega(\sqrt{n/B\log n})} communication rounds in the worst case, even for graphs of diameter O(log n), where n is the number of nodes in the graph. Furthermore, the lower bound holds even if we allow the output to contain O(?n){O(\sqrt n)} blocking pairs, and if a pair is considered blocking only if they like each other much more then their assigned match.     

Conditional edge-fault-tolerant Hamiltonicity of dual-cubes

The dual-cube is an interconnection network for linking a large number of nodes with a low node degree. It uses low-dimensional hypercubes as building blocks and keeps the main desired properties of the hypercube. A dual-cube DC(n) has n + 1 links per node where n is the degree of a cluster (n-cube), and one more link is used for connecting to a node in another cluster. In this paper, assuming each node is incident with at least two fault-free links, we show a dual-cube DC(n) contains a fault-free Hamiltonian cycle, even if it has up to 2n − 3 link faults. The result is optimal with respect to the number of tolerant edge faults.     

The fastcube: a variation on hypercube topology with lower diameter

This paper presents a class of n-dimensional interconnection topologies with N=2ⁿ nodes which we refer to as n-fastcubes. The node degree of the n-fastcube is n and its diameter is ⌈(n+1)/2⌉, which is substantially smaller than that of the same size hypercube. Topological properties as well as several routing algorithms for fastcubes are developed. In addition, a new methodology for the design and analysis of fastcubes is employed. This methodology is based on modeling interconnection networks as finite state automata. The inputs to these particular automata are routing sequences. The routing and embedding algorithms developed in this paper produce routing sequences. The main characteristic of routing sequences is their node independence. A node independent routing sequence, p(H), produces a path between any pair of nodes with the Hamming distance of H. Thus, these sequences can be used, without modification, at any node to establish paths in a fastcube.     

Probabilistic flooding in stochastic networks: Analysis of global information outreach

This article investigates probabilistic information dissemination in stochastic networks. The following problem is studied: A source node intends to deliver a message to all other network nodes using probabilistic flooding, i.e., each node forwards a received message to all its neighbors with a common network-wide forwarding probability ω. Question is: what is the minimum ω-value each node should use, such that the flooded message is obtained by all nodes with high probability? We first present a generic approach to derive the global outreach probability in arbitrary networks and then focus on Erd?s Rényi graphs (ERGs) and random geometric graphs (RGGs). For ERGs we derive an exact expression. For RGGs we derive an asymptotic expression that represents an approximation for networks with high node density. Both reliable and unreliable links are studied.     

Mesh网络容错广播路由算法的概率分析

One-to-all or broadcast communication is one of the most important communication patterns and occurs in many important applications in parallel computing. This paper proposes a fault tolerant, local-irdormation-based, and distributed broadcast routing algorithm based on the concept of k-submesh-cormectivity in all-port mesh networks.The paper analyzes the fault tolerance of the algorithm in terms of node failure probability. Suppose that every nodehas independent failure probability, and deduce the success probability of the broadcast routing, which successfully routes a message from a source node to all non-faulty nodes in the networks. The paper strictly proves that the broadcast routing algorithm with the success probability of 99％ to route among all non-faulty nodes on mesh networks with forty thousand nodes, in case that the node failure probability is controlled within 0.12％ Simulation results show that the algorithm is practically efficient and effective, and the time steps of the algorithm are very closeto the optimum.     

Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nⁿ nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.     

Optimal Routing in a Small-World Network

Substantial research has been devoted to the modelling of the small-world phenomenon that arises in nature as well as human society. Earlier work has focused on the static properties of various small-world models. To examine the routing aspects, Kleinberg proposes a model based on a d-dimensional toroidal lattice with long-range links chosen at random according to the d-harmonic distribution. Kleinberg shows that, by using only local information, the greedy routing algorithm performs in O（lg^2 n） expected number of hops. We extend Kleinberg＇s small-world model by allowing each node x to have two more random links to nodes chosen uniformly and randomly within （lg n）2/d Manhattan distance from x. Based on this extended model, we then propose an oblivious algorithm that can route messages between any two nodes in O（lg n） expected number of hops. Our routing algorithm keeps only O（（lgn）β＋1） bits of information on each node, where 1 〈 β 〈 2, thus being scalable w.r.t, the network size. To our knowledge, our result is the first to achieve the optimal routing complexity while still keeping a poly-logarithmic number of bits of information stored on each node in the small-world networks.     

Efficient unicast in bijective connection networks with the restricted faulty node set

The connectivity is an important criteria to measure the fault-tolerant performance of a graph. However, the connectivity based on the condition of the set of arbitrary faulty nodes is generally lower. In this paper, in order to heighten this measure, we introduce the restricted connectivity into bijective connection networks. First, we prove that the probability that all the neighbors of an arbitrary node becomes faulty in any n-dimensional bijective connection network X_n is very low when n becomes sufficient large. Then, we give a constructive proof that under the condition that each node of an n-dimensional bijective connection network X_n has at least one fault-free neighbor, its restricted connectivity is 2n − 2, about half of the connectivity of X_n. Finally, by our constructive proof, we give an O(n) algorithm to get a reliable path of length at most n + 3⌈log₂∣F∣⌉ + 1 between any two fault-free nodes in an n-dimensional bijective connection network. In particular, since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., our algorithm is appropriate for these cubes.     

Broadcasting Algorithms for the Star-Connected Cycles Interconnection Network

The star-connected cycles (SCC) graph was recently proposed as an alternative to the cube-connected cycles (CCC) graph, using a star graph to connect cycles of nodes rather than a hypercube. This paper presents an analysis of broadcasting algorithms for SIMD and MIMD SCCs, covering both one-port and multiple-port versions. We show that O(n log n) one-port broadcasting algorithms that have been proposed for the n-star cannot be efficiently extended to the case of the n-SCC graph. However, a simple but rather inefficient algorithm requiring O(n²) steps in the n-star graph can run in O(n) time in the n-SCC if a proper combination of parallelism and transmission rates in the links connecting the nodes is selected. The result is that broadcasting in the n-SCC can be accomplished efficiently, requiring a running time better than or equal to that of an n-star containing (n − 1) times fewer nodes.     

Efficient elections in chordal ring networks

We study the message complexity of the problem of distributively electing a leader in chordal rings. Such networks consist of a basic ring with additional links, the extreme cases being the oriented ring and the complete graph with a full sense of direction. We present a general election algorithm for these networks, and prove its optimality. As a corollary, we show thatO(logn) chords at each processor suffice to obtain an algorithm that uses at mostO(n) messages; this improves and extends a previous work, where an algorithm, also usingO(n) messages, was suggested for the case where alln-1 chords exist (the oriented complete network).     

Efficient distributed approximation algorithms via probabilistic tree embeddings

We present a uniform approach to design efficient distributed approximation algorithms for various fundamental network optimization problems. Our approach is randomized and based on a probabilistic tree embedding due to Fakcharoenphol et?al. (J Comput Syst Sci 69(3):485–497, 2004) (FRT embedding). We show how to efficiently compute an (implicit) FRT embedding in a decentralized manner and how to use the embedding to obtain efficient expected O(log n)-approximate distributed algorithms for various problems, in particular the generalized Steiner forest problem (including the minimum Steiner tree problem), the minimum routing cost spanning tree problem, and the k-source shortest paths problem. The distributed construction of the FRT embedding is based on the computation of least elements (LE) lists, a distributed data structure that is of independent interest. Assuming a global order on the nodes of a network, the LE-list of a node stores the smallest node (w.r.t. the given order) within every distance d (cf. Cohen in J Comput Syst Sci 55(3):441–453, 1997, Cohen and Kaplan in J Comput Syst Sci 73(3):265–288, 2007). Assuming a random order on the nodes, we give a distributed algorithm for computing LE-lists on a weighted graph with time complexity O(S log n), where S is a graph parameter called the shortest path diameter which can be considered the weighted counterpart of the diameter D of the graph. For unweighted graphs, our LE-lists computation has asymptotically optimal time complexity of O(D). As a byproduct, we get an improved synchronous leader election algorithm for general networks that is both time-optimal and almost message-optimal with high probability.     

Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles

We prove that, for the black hole search problem in networks of arbitrary but known topology, the pebble model of agent interaction is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of two asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node), can locate the black hole in an arbitrary network of known topology; this can be done with Θ(nlog?n) moves, where n is the number of nodes, even when the links are not FIFO. These results are obtained with a novel algorithmic technique, ping-pong, for agents using pebbles.     

A fast fault-identification algorithm for bijective connection graphs using the PMC model

Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N^2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2ⁿ, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs.