Invited Talks

Random Walks, Interacting Particles, Dynamic Networks: Randomness Can Be Helpful

Abstract

The aim of this article is to discuss some applications of random processes in searching and reaching consensus on finite graphs. The topics covered are: Why random walks?, Speeding up random walks, Random and deterministic walks, Interacting particles and voting, Searching changing graphs.

Colin Cooper

SINR Maps: Properties and Applications

Abstract

Most algorithmic studies in wireless networking to date employ simplified graphbased models such as the unit disk graph (UDG) model. These models conveniently abstract away complications stemming from interference and attenuation, and thus make it easier to deal with algorithmic issues. On the negative side, the simplifying assumptions adopted by the graph-based models result in network representations that fail to capture accurately some of the essential aspects of wireless communication.

David Peleg

Survey Talk

A Survey on Some Recent Advances in Shared Memory Models

Abstract

Due to the advent of multicore machines, shared memory distributed computing models taking into account asynchrony and process crashes are becoming more and more important. This paper visits models for these systems and analyses their properties from a computability point of view. Among them, the base snapshot model and the iterated model are particularly investigated. The paper visits also several approaches that have been proposed to model failures (mainly the wait-free model and the adversary model) and gives also a look at the BG simulation. The aim of this survey is to help the reader to better understand the power and limits of distributed computing shared memory models.

Sergio Rajsbaum, Michel Raynal

Fault Tolerance

Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults

Abstract

We compare the solvability of the Consensus and Broadcast problems in synchronous communication networks in which the delivery of messages is not reliable. The failure model is the mobile omission faults model. During each round, some messages can be lost and the set of possible simultaneous losses is the same for each round. We investigate these problems for the first time for arbitrary sets of possible failures. Previously, these sets were defined by bounding the numbers of failures. In this setting, we present a new necessary condition for the solvability of Consensus that unifies previous impossibility results in this area. This condition is expressed using Broadcastability properties. As a very important application, we show that when the sets of omissions that can occur are defined by bounding the numbers of failures, counted in any way (locally, globally, etc.), then the Consensus problem is actually equivalent to the Broadcast problem.

Emmanuel Godard, Joseph Peters

Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing

(Extended Abstract)

Abstract

We present generic transformations, which allow to translate classic fault-tolerant distributed algorithms and their correctness proofs into a real-time distributed computing model (and vice versa). Owing to the non-zero-time, non-preemptible state transitions employed in our real-time model, scheduling and queuing effects (which are inherently abstracted away in classic zero step-time models, sometimes leading to overly optimistic time complexity results) can be accurately modeled. Our results thus make fault-tolerant distributed algorithms amenable to a sound real-time analysis, without sacrificing the wealth of algorithms and correctness proofs established in classic distributed computing research. By means of an example, we demonstrate that real-time algorithms generated by transforming classic algorithms can be competitive even w.r.t. optimal real-time algorithms, despite their comparatively simple real-time analysis.

Heinrich Moser, Ulrich Schmid

Self-stabilizing Hierarchical Construction of Bounded Size Clusters

Abstract

We present a self-stabilizing clustering algorithm for asynchronous networks. Our algorithms works under any scheduler and is silent. The sizes of the clusters are bounded by a parameter of the algorithm. Our solution also avoids constructing a large number of small clusters. Although the clusters are disjoint (no node belongs to more than one cluster), the clusters are connected to form a tree so that the resulting overlay graph is connected. The height of the tree of clusters is bounded by the diameter of the network.

Alain Bui, Simon Clavière, Ajoy K. Datta, Lawrence L. Larmore, Devan Sohier

The Universe of Symmetry Breaking Tasks

Abstract

Processes in a concurrent system need to coordinate using a shared memory or a message-passing subsystem in order to solve agreement tasks such as, for example, consensus or set agreement. However, coordination is often needed to “break the symmetry” of processes that are initially in the same state, for example, to get exclusive access to a shared resource, to get distinct names or to elect a leader.

This paper introduces and studies the family of generalized symmetry breaking (GSB) tasks, that includes election, renaming and many other symmetry breaking tasks. Differently from agreement tasks, a GSB task is “inputless”, in the sense that processes do not propose values; the task only specifies the symmetry breaking requirement, independently of the system’s initial state (where processes differ only on their identifiers). Among various results characterizing the family of GSB tasks, it is shown that (non adaptive) perfect renaming is universal for all GSB tasks.

Damien Imbs, Sergio Rajsbaum, Michel Raynal

Routing

Determining the Conditional Diagnosability of k-Ary n-Cubes Under the MM* Model

Abstract

Processor fault diagnosis plays an important role for measuring the reliability of multiprocessor systems, and the diagnosability of many well-known interconnection networks has been investigated widely. Conditional diagnosability is a novel measure of diagnosability, which is introduced by Lai et al., by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. The class of k-ary n-cubes contains as special cases many topologies important to parallel processing, such as rings, hypercubes, and tori. In this paper, we study some topological properties of the k-ary n-cube, denoted by \(Q^k_n\). Then we apply them to show that the conditional diagnosability of \(Q^k_n\) under the comparison diagnosis model is \(t_c(Q^k_n)=6n-5\) for k ≥ 4 and n ≥ 4.

Sun-Yuan Hsieh, Chi-Ya Kao

Medium Access Control for Adversarial Channels with Jamming

Abstract

We study broadcasting on multiple access channels with dynamic packet arrivals and jamming. The presented protocols are for the medium-access-control layer. The mechanisms of timing of packet arrivals and determination of which rounds are jammed are represented by adversarial models. Packet arrivals are constrained by the average rate of injections and the number of packets that can arrive in one round. Jamming is constrained by the rate with which the adversary can jam rounds and by the number of consecutive rounds that can be jammed. Broadcasting is performed by deterministic distributed protocols. We give upper bounds on worst-case packet latency of protocols in terms of the parameters defining adversaries. Experiments include both deterministic and randomized protocols. A simulation environment we developed is designed to represent adversarial properties of jammed channels understood as restrictions imposed on adversaries.

Lakshmi Anantharamu, Bogdan S. Chlebus, Dariusz R. Kowalski, Mariusz A. Rokicki

Full Reversal Routing as a Linear Dynamical System

Abstract

Link reversal is a versatile algorithm design paradigm, originally proposed by Gafni and Bertsekas in 1981 for routing, and subsequently applied to other problems including mutual exclusion and resource allocation. Although these algorithms are well-known, until now there have been only preliminary results on time complexity, even for the simplest link reversal scheme for routing, called Full Reversal (FR). In this paper we tackle this open question for arbitrary communication graphs. Our central technical insight is to describe the behavior of FR as a dynamical system, and to observe that this system is linear in the min-plus algebra. From this characterization, we derive the first exact formula for the time complexity: Given any node in any (acyclic) graph, we present an exact formula for the time complexity of that node, in terms of some simple properties of the graph. These results for FR are instrumental in analyzing a broader class of link reversal routing algorithms, as we show in a companion paper that such algorithms can be reduced to FR. In the current paper, we further demonstrate the utility of our formulas by using them to show the previously unknown fact that FR is time-efficient when executed on trees.

Bernadette Charron-Bost, Matthias Függer, Jennifer L. Welch, Josef Widder

Partial is Full

Abstract

Link reversal is the basis of several well-known routing algorithms [1,2,3]. In these algorithms, logical directions are imposed on the communication links and a node that becomes a sink reverses some of its incident links to allow the (re)construction of paths to the destination. In the Full Reversal (FR) algorithm [1], a sink reverses all its incident links. In other schemes, a sink reverses only some of its incident links; a notable example is the Partial Reversal (PR) algorithm [1]. Prior work [4] has introduced a generalization, called LR, of link-reversal routing, including FR and PR. In this paper, we show that every execution of LR on any link-labeled input graph corresponds, in a precise sense, to an execution of FR on a transformed graph. Thus, all the link reversal schemes captured by LR can be reduced to FR, indicating that “partial is full.” The correspondence preserves the work and time complexities. As a result, we can, for the first time, obtain the exact time complexity for LR, and by specialization for PR.

Bernadette Charron-Bost, Matthias Függer, Jennifer L. Welch, Josef Widder

Mobile Agents/Robots (I)

Convergence with Limited Visibility by Asynchronous Mobile Robots

Abstract

Consider a community of simple autonomous robots freely moving in the plane. The robots are decentralized, asynchronous, deterministic without the common coordination system, identities, direct communication, memory of the past, but with the ability to sense the positions of the other robots. This paper presents a distributed algorithm for the convergence problem with limited visibility in 1-bounded asynchrony. The presented algorithm also solves the convergence problem with unlimited visibility in full asynchrony without the need for the multiplicity detection.

Branislav Katreniak

Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally

Abstract

We are given a winding chain of n mobile robots between two stations in the plane, each of them having a limited viewing range. It is only guaranteed that each robot can see its two neighbors in the chain. The goal is to let the robots converge to the line between the stations. We use a discrete and synchronous time model, but we restrict the movement of each mobile robot to a distance of δ in each round. This restriction fills the gap between the previously used discrete time model with an unbounded step length and the continuous time model which was introduced in [1]. We adapt the strategy by Dynia et al. [2]: In each round, each robot first observes the positions of its neighbors and then moves towards the midpoint between them until it reaches the point or has moved a distance of δ. The main energy consumers in this scenario are the number observations of positions of neighbors, which equals the number of rounds, and the distance to be traveled by the robots. We analyze the strategy with respect to both quality measures and provide asymptotically tight bounds. We show that the best choice for δ for this strategy is \(\delta \in \Theta(\frac{1}{n})\), since this minimizes (up to constant factors) both energy consumers, the number of rounds as well as the maximum traveled distance, at the same time.

Philipp Brandes, Bastian Degener, Barbara Kempkes, Friedhelm Meyer auf der Heide

Asynchronous Mobile Robot Gathering from Symmetric Configurations without Global Multiplicity Detection

Abstract

We consider a set of k autonomous robots that are endowed with visibility sensors (but that are otherwise unable to communicate) and motion actuators. Those robots must collaborate to reach a single vertex that is unknown beforehand, and to remain there hereafter. Previous works on gathering in ring-shaped networks suggest that there exists a tradeoff between the size of the set of potential initial configurations, and the power of the sensing capabilities of the robots (i.e. the larger the initial configuration set, the most powerful the sensor needs to be). We prove that there is no such trade off. We propose a gathering protocol for an odd number of robots in a ring-shaped network that allows symmetric but not periodic configurations as initial configurations, yet uses only local weak multiplicity detection. Robots are assumed to be anonymous and oblivious, and the execution model is the non-atomic CORDA model with asynchronous fair scheduling. Our protocol allows the largest set of initial configurations (with respect to impossibility results) yet uses the weakest multiplicity detector to date. The time complexity of our protocol is O(n ²), where n denotes the size of the ring. Compared to previous work that also uses local weak multiplicity detection, we do not have the constraint that k < n/2 (here, we simply have 2 < k < n − 3).

Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil

Mobile Agents/Robots (II)

Gathering Asynchronous Oblivious Agents with Local Vision in Regular Bipartite Graphs

Abstract

We consider the problem of gathering identical, memoryless, mobile agents in one node of an anonymous graph. Agents start from different nodes of the graph. They operate in Look-Compute-Move cycles and have to end up in the same node. In one cycle, an agent takes a snapshot of its immediate neighborhood (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each agent. The novelty of our model with respect to the existing literature on gathering asynchronous oblivious agents in graphs is that the agents have very restricted perception capabilities: they can only see their immediate neighborhood.

An initial configuration of agents is called gatherable if there exists an algorithm that gathers all the agents of the configuration in one node and keeps them idle from then on, regardless of the actions of the asynchronous adversary. (The algorithm can be even tailored to gather this specific configuration.) The gathering problem is to determine which configurations are gatherable and find a (universal) algorithm which gathers all gatherable configurations. We give a complete solution of the gathering problem for regular bipartite graphs. Our main contribution is the proof that the class of gatherable initial configurations is very small: it consists only of “stars” (an agent A with all other agents adjacent to it) of size at least 3. On the positive side we give an algorithm accomplishing gathering for every gatherable configuration.

Samuel Guilbault, Andrzej Pelc

Gathering of Six Robots on Anonymous Symmetric Rings

Abstract

The paper deals with a recent model of robot-based computing which makes use of identical, memoryless mobile robots placed on nodes of anonymous graphs. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot.

In particular, we consider the case of only six robots placed on the nodes of an anonymous ring in such a way they constitute a symmetric placement with respect to one single axis of symmetry, and we ask whether there exists a strategy that allows the robots to gather at one single node. This is in fact the first case left open after a series of papers [1,2,3,4] dealing with the gathering of oblivious robots on anonymous rings. As long as the gathering is feasible, we provide a new distributed approach that guarantees a positive answer to the posed question. Despite the very special case considered, the provided strategy turns out to be very interesting as it neither completely falls into symmetry-breaking nor into symmetry-preserving techniques.

Gianlorenzo D’Angelo, Gabriele Di Stefano, Alfredo Navarra

Tight Bounds for Scattered Black Hole Search in a Ring

Abstract

We study the problem of locating a particularly dangerous node, the so-called black hole in a synchronous anonymous ring network with mobile agents. A black hole destroys all mobile agents visiting that node without leaving any trace. Unlike most previous research on the black hole search problem which employed a colocated team of agents, we consider the more challenging scenario when the agents are identical and initially scattered within the network. Moreover, we solve the problem with agents that have constant-sized memory and carry a constant number of identical tokens, which can be placed at nodes of the network. In contrast, the only known solutions for the case of scattered agents searching for a black hole, use stronger models where the agents have non-constant memory, can write messages in whiteboards located at nodes or are allowed to mark both the edges and nodes of the network with tokens.

We are interested in the minimum resources (number of agents and tokens) necessary for locating all links incident to the black hole. In fact, we provide matching lower and upper bounds for the number of agents and the number of tokens required for deterministic solutions to the black hole search problem, in oriented or unoriented rings, using movable or unmovable tokens.

Jérémie Chalopin, Shantanu Das, Arnaud Labourel, Euripides Markou

Improving the Optimal Bounds for Black Hole Search in Rings

Abstract

In this paper we re-examine the well known problem of asynchronous black hole search in a ring. It is well known that at least 2 agents are needed and the total number of agents’ moves is at least Ω(n logn); solutions indeed exist that allow a team of two agents to locate the black hole with the asymptotically optimal cost of Θ(n logn) moves.

In this paper we first of all determine the exact move complexity of black hole search in an asynchronous ring. In fact, we prove that 3nlog₃ n − O(n) moves are necessary. We then present a novel algorithm that allows two agents to locate the black hole with at most 3nlog₃ n + O(n) moves, improving the existing upper bounds, and matching the lower bound up to the constant of proportionality. Finally we show how to modify the protocol so to achieve asymptotically optimal time complexity Θ(n), still with 3nlog₃ n + O(n) moves; this improves upon all existing time-optimal protocols, which require O(n ²) moves. This protocol is the first that is optimal with respect to all three complexity measures: size (number of agents), cost (number of moves) and time; in particular, its cost and size complexities match the lower bounds up to the constant.

Balasingham Balamohan, Paola Flocchini, Ali Miri, Nicola Santoro

Probabilistic Methods

The Cover Times of Random Walks on Hypergraphs

Abstract

Random walks in graphs have been applied to various network exploration and network maintenance problems. In some applications, however, it may be more natural, and more accurate, to model the underlying network not as a graph but as a hypergraph, and solutions based on random walks require a notion of random walks in hypergraphs. At each step, a random walk on a hypergraph moves from its current position v to a random vertex in a randomly selected hyperedge containing v. We consider two definitions of cover time of a hypergraph H. If the walk sees only the vertices it moves between, then the usual definition of cover time, C(H), applies. If the walk sees the complete edge during the transition, then an alternative definition of cover time, the inform time I(H) is used. The notion of inform time models passive listening which fits the following types of situations. The particle is a rumor passing between friends, which is overheard by other friends present in the group at the same time. The particle is a message transmitted randomly from location to location by a directional transmission in an ad-hoc network, but all receivers within the transmission range can hear.

In this paper we give an expression for C(H) which is tractable for many classes of hypergraphs, and calculate C(H) and I(H) exactly for random r-regular, s-uniform hypergraphs. We find that for such hypergraph whp C(H)/I(H) = Θ(s) for large s.

Colin Cooper, Alan Frieze, Tomasz Radzik

Routing in Carrier-Based Mobile Networks

Abstract

The past years have seen an intense research effort directed at study of delay/disruption tolerant networks and related concepts (intermittently connected networks, opportunistic mobility networks). As a fundamental primitive, routing in such networks has been one of the research foci. While multiple network models have been proposed and routing in them investigated, most of the published results are of heuristic nature with experimental validation; analytical results are scarce and apply mostly to networks whose structure follows deterministic schedule.

In this paper, we propose a simple model of opportunistic mobility network based on oblivious carriers, and investigate the routing problem in such networks. We present an optimal online routing algorithm and compare it with a simple shortest-path inspired routing and the optimal offline routing. In doing so, we identify the key parameters (the minimum non-zero probability of meeting among the carrier pairs, and the number of carriers a given carrier comes into contact) driving the separation among these algorithms.

Bronislava Brejová, Stefan Dobrev, Rastislav Královič, Tomáš Vinař

On the Performance of a Retransmission-Based Synchronizer

Abstract

Designing algorithms for distributed systems that provide a round abstraction is often simpler than designing for those that do not provide such an abstraction. However, distributed systems need to tolerate various kinds of failures. The concept of a synchronizer deals with both: It constructs rounds and allows masking of transmission failures. One simple way of dealing with transmission failures is to retransmit a message until it is known that the message was successfully received. We calculate the exact value of the average rate of a retransmission-based synchronizer in an environment with probabilistic message loss, within which the synchronizer shows nontrivial timing behavior. The theoretic results, based on Markov theory, are backed up with Monte Carlo simulations.

Thomas Nowak, Matthias Függer, Alexander Kößler

Distributed Algorithms on Graphs

Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth

Abstract

We deterministically compute a Δ + 1 coloring in time O(Δ_5c + 2·(Δ₅)^2/c/(Δ₁)^ε + (Δ₁)^ε + log^* n) and O(Δ_5c + 2·(Δ₅)^1/c/Δ^ε + Δ^ε + (Δ₅)^dlogΔ₅logn) for arbitrary constants d,ε and arbitrary constant integer c, where Δ_i is defined as the maximal number of nodes within distance i for a node and Δ: = Δ₁. Our greedy algorithm improves the state-of-the-art Δ + 1 coloring algorithms for a large class of graphs, e.g. graphs of moderate neighborhood growth. We also state and analyze a randomized coloring algorithm in terms of the chromatic number, the run time and the used colors. If \(\Delta \in \Omega(\log^{1+1/\log^* n} n)\) and \(\chi\in O(\Delta/\log^{1+1/\log^* n} n)\) then our algorithm executes in time O(logχ + log^* n) with high probability. For graphs of polylogarithmic chromatic number the analysis reveals an exponential gap compared to the fastest Δ + 1 coloring algorithm running in time \(O(\log \Delta+\sqrt{\log n})\). The algorithm works without knowledge of χ and uses less than Δ colors, i.e., (1 − 1/O(χ))Δ with high probability. To the best of our knowledge this is the first distributed algorithm for (such) general graphs taking the chromatic number χ into account.

Johannes Schneider, Roger Wattenhofer

Multiparty Equality Function Computation in Networks with Point-to-Point Links

Abstract

In this paper, we study the problem of computing the multiparty equality (MEQ) function: n ≥ 2 nodes, each of which is given an input value from {1, ⋯ ,K}, determine if their inputs are all identical, under the point-to-point communication model. The MEQ function equals to 1 if and only if all n inputs are identical, and 0 otherwise. The communication complexity of the MEQ problem is defined as the minimum number of bits communicated in the worst case. It is easy to show that (n − 1)log₂ K bits is an upper bound, by constructing a simple algorithm with that cost. In this paper, we demonstrate that communication cost strictly lower than this upper bound can be achieved. We show this by constructing a static protocol that solves the MEQ problem for n = 3, K = 6, of which the communication cost is strictly lower than the above upper bound (2log₂ 6 bits). This result is then generalized for large values of n and K.

Guanfeng Liang, Nitin Vaidya

Network Verification via Routing Table Queries

Abstract

We address the problem of verifying the accuracy of a map of a network by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph G = (V,E), and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes of G to be queried so as to univocally identify G. This problem has been faced w.r.t. a couple of query models assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. First, we show that any network of n nodes needs Ω(loglogn) queries to be verified. Then, we prove that there is no o(logn)-approximation algorithm for the problem, unless \(\mbox{\sf P}=\mbox{\sf NP}\), even for networks of diameter 2. On the positive side, we provide an O(logn)-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees, and cycles of even length.

Evangelos Bampas, Davide Bilò, Guido Drovandi, Luciano Gualà, Ralf Klasing, Guido Proietti

Social Context Congestion Games

Abstract

We consider the social context games introduced in [2], where we are given a classical game, an undirected social graph expressing knowledge among the players and an aggregating function. The players and strategies are as in the underlying game, while the players costs are computed from their immediate costs, that is the original payoffs in the underlying game, according to the neighborhood in the social graph and to the aggregation function. More precisely, the perceived cost incurred by a player is the result of the aggregating function applied to the immediate costs of her neighbors and of the player herself. We investigate social context games in which the underlying games are linear congestion games and Shapley cost sharing games, while the aggregating functions are min, max and sum. In each of the six arising cases, we first completely characterize the class of the social network topologies guaranteeing the existence of pure Nash equilibria. We then provide optimal or asymptotically optimal bounds on the price of anarchy of 22 out of the 24 cases obtained by considering four social cost functions, namely, max and sum of the players’ immediate and perceived costs. Finally, we extend some of our results to multicast games, a relevant subclass of the Shapley cost sharing ones.

Vittorio Bilò, Alessandro Celi, Michele Flammini, Vasco Gallotti

Ad-hoc Networks

Network Synchronization and Localization Based on Stolen Signals

Abstract

We consider an anchor-free, relative localization and synchronization problem where a set of n receiver nodes and m wireless signal sources are independently, uniformly, and randomly distributed in a disk in the plane. The signals can be distinguished and their capture times can be measured. At the beginning neither the positions of the signal sources and receivers are known nor the sending moments of the signals. Now each receiver captures each signal after its constant speed journey over the unknown distance between signal source and receiver position. Given these n m capture times the task is to compute the relative distances between all synchronized receivers. In a more generalized setting the receiver nodes have no synchronized clocks and need to be synchronized from the capture times of the stolen signals.

For unsynchronized receivers we can compute in time \({\ensuremath \cal O}(n m)\) an approximation of the positions and the clock offset within an absolute error of \({\ensuremath \cal O}\left(\sqrt{\frac{\log m}{m}}\right)\) with probability 1 − m ^− c − e ^− c′n (for any \(c\in {\ensuremath \cal O}(1)\) and some c′ > 0).

For synchronized receivers we can compute in time O(n m) an approximation of the correct relative positions within an absolute error margin of \( {\cal O}\left(\frac{\log^2 m}{m^2}\right)\) with probability 1 − m ^− c − e ^− c′n. This error bound holds also for unsynchronized receivers if we consider a normal distribution of the sound signals, or if the sound signals are randomly distributed in a surrounding larger disk.

If the receiver nodes are connected via an ad hoc network we present a distributed algorithm which needs at most O(n m logn) messages in total to compute the approximate positions and clock offsets for the network within an absolute error of \({\ensuremath \cal O}\left(\sqrt{\frac{\log m}{m}}\right)\) with probability 1 − n ^− c if m > n.

Christian Schindelhauer, Zvi Lotker, Johannes Wendeberg

Optimal Time Data Gathering in Wireless Networks with Omni–Directional Antennas

Abstract

We study algorithmic and complexity issues originating from the problem of data gathering in wireless networks. We give an algorithm to construct minimum makespan transmission schedules for data gathering when the communication graph G is a tree network, the interference range is any integer m ≥ 2, and no buffering is allowed at intermediate nodes. In the interesting case in which all nodes in the network have to deliver an arbitrary non-zero number of packets, we provide a closed formula for the makespan of the optimal gathering schedule. Additionally, we consider the problem of determining the computational complexity of data gathering in general graphs and show that the problem is NP–complete. On the positive side, we design a simple (1 + 2/m) factor approximation algorithm for general networks.

Jean-Claude Bermond, Luisa Gargano, Stephane Perénnes, Adele A. Rescigno, Ugo Vaccaro

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Invited Talks

Random Walks, Interacting Particles, Dynamic Networks: Randomness Can Be Helpful

SINR Maps: Properties and Applications

Survey Talk

A Survey on Some Recent Advances in Shared Memory Models

Fault Tolerance

Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults

Reconciling Fault-Tolerant Distributed Algorithms and Real-Time Computing

Self-stabilizing Hierarchical Construction of Bounded Size Clusters

The Universe of Symmetry Breaking Tasks

Routing

Determining the Conditional Diagnosability of k-Ary n-Cubes Under the MM* Model

Medium Access Control for Adversarial Channels with Jamming

Full Reversal Routing as a Linear Dynamical System

Partial is Full

Mobile Agents/Robots (I)

Convergence with Limited Visibility by Asynchronous Mobile Robots

Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally

Asynchronous Mobile Robot Gathering from Symmetric Configurations without Global Multiplicity Detection

Mobile Agents/Robots (II)

Gathering Asynchronous Oblivious Agents with Local Vision in Regular Bipartite Graphs

Gathering of Six Robots on Anonymous Symmetric Rings

Tight Bounds for Scattered Black Hole Search in a Ring

Improving the Optimal Bounds for Black Hole Search in Rings

Probabilistic Methods

The Cover Times of Random Walks on Hypergraphs

Routing in Carrier-Based Mobile Networks

On the Performance of a Retransmission-Based Synchronizer

Distributed Algorithms on Graphs

Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth

Multiparty Equality Function Computation in Networks with Point-to-Point Links

Network Verification via Routing Table Queries

Social Context Congestion Games

Ad-hoc Networks

Network Synchronization and Localization Based on Stolen Signals

Optimal Time Data Gathering in Wireless Networks with Omni–Directional Antennas

Backmatter