We present the δ-Synchronizer, which works in non-synchronous dynamic networks under minimal assumptions. Our model allows for arbitrary topological changes without any guarantee of eventual global or partial stabilization and assumes that nodes are anonymous. This deterministic synchronizer is the first that enables nodes to simulate a dynamic network synchronous algorithm for executions in a semi-synchronous dynamic environment under a weakly-fair node activation scheduler, despite the absence of a global clock, node ids, persistent connectivity or any assumptions about the edge dynamics (in both the synchronous and semi-synchronous environments). We make the following contributions: (1) we extend the definition of synchronizers to networks with arbitrary edge dynamics; (2) we present the first synchronizer from the semi-synchronous to the synchronous model in such networks; and (3) we present non-trivial applications of the proposed synchronizer to existing algorithms. We assume an extension of the Pull communication model by adding a single 1-bit multi-writer atomic register at each edge-port of a node. We show that this extension is needed and that synchronization in our setting is not possible without it. The δ-Synchronizer operates with memory overhead at the nodes that is asymptotically logarithmic on the runtime of the underlying synchronous algorithm being simulated - in particular, it is logarithmic for polynomial-time synchronous algorithms.

Local interactions of uncoordinated individuals produce the collective behaviors of many biological systems, inspiring much of the current research in programmable matter. A striking example is the spontaneous assembly of fire ants into "bridges" comprising their own bodies to traverse obstacles and reach sources of food. Experiments and simulations suggest that, remarkably, these ants always form one bridge - instead of multiple, competing bridges - despite a lack of central coordination. We argue that the reliable formation of a single bridge does not require sophistication on behalf of the individuals by provably reproducing this behavior in a self-organizing particle system. We show that the formation of a single bridge by the particles is a statistical inevitability of their preferences to move in a particular direction, such as toward a food source, and their preference for more neighbors. Two parameters, η and β, reflect the strengths of these preferences and determine the Gibbs stationary measure of the corresponding particle system’s Markov chain dynamics. We show that a single bridge almost certainly forms when η and β are sufficiently large. Our proof introduces an auxiliary Markov chain, called an "occupancy chain," that captures only the significant, global changes to the system. Through the occupancy chain, we abstract away information about the motion of individual particles, but we gain a more direct means of analyzing their collective behavior. Such abstractions provide a promising new direction for understanding many other systems of programmable matter.

Throughput is a main performance objective in communication networks. This paper considers a fundamental maximum throughput routing problem — the All-or-Nothing Multicommodity Flow (ANF) problem — in arbitrary directed graphs and in the practically relevant but challenging setting where demands can be (much) larger than the edge capacities, mandating the need for splittable flows (i.e., flows may not follow a single path). Formally, the input for the ANF problem is an edge-capacitated directed graph where we have a given number of source-destination node-pairs with their respective demands and strictly positive weights. The goal is to route a maximum weight subset of the given pairs (i.e., the weighted throughput), respecting the edge capacities: A commodity is routed if all of its demand is routed from its respective source to destination (this is the all-or-nothing aspect). We present a polynomial-time bi-criteria approximation randomized rounding framework for this NP-hard problem that yields an arbitrarily good approximation on the weighted throughput while violating the edge capacity constraints by at most a sublogarithmic multiplicative factor. We present two non-trivial linear programming relaxations that can be used in the framework; the first uses a novel edge-flow formulation and the second uses a packing formulation. We demonstrate the “equivalence” of these formulations and then highlight the advantages of each of the two approaches. We complement our theoretical results with a proof of concept empirical evaluation, considering a variety of network scenarios.

Individual modules of programmable matter participate in their system's collective behavior by expending energy to perform actions. However, not all modules may have access to the external energy source powering the system, necessitating a local and distributed strategy for supplying energy to modules. In this work, we present a general energy distribution framework for the canonical amoebot model of programmable matter that transforms energy-agnostic algorithms into energy-constrained ones with equivalent behavior and an $\mathcal{O}(n^2)$-round runtime overhead -- even under an unfair adversary -- provided the original algorithms satisfy certain conventions. We then prove that existing amoebot algorithms for leader election (ICDCN 2023) and shape formation (Distributed Computing, 2023) are compatible with this framework and show simulations of their energy-constrained counterparts, demonstrating how other unfair algorithms can be generalized to the energy-constrained setting with relatively little effort. Finally, we show that our energy distribution framework can be composed with the concurrency control framework for amoebot algorithms (Distributed Computing, 2023), allowing algorithm designers to focus on the simpler energy-agnostic, sequential setting but gain the general applicability of energy-constrained, asynchronous correctness.

The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction at SPAA 2014, a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model , an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency . Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design . We first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. As a case study, we demonstrate both approaches using a simple algorithm for hexagon formation . Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.

The Edsger W. Dijkstra Prize in Distributed Computing is awarded for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributed computing have been evident for at least a decade. It is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). The prize is presented annually, with the presentation taking place alternately at PODC and DISC.

The foraging problem asks how a collective of particles with limited computational, communication and movement capabilities can autonomously compress around a food source and disperse when the food is depleted or shifted, which may occur at arbitrary times. We would like the particles to iteratively self-organize, using only local interactions, to correctly gather whenever a food particle remains in a position long enough and search if no food particle has existed recently. Unlike previous approaches, these search and gather phases should be self-induced so as to be indefinitely repeatable as the food evolves, with microscopic changes to the food triggering macroscopic, system-wide phase transitions. We present a stochastic foraging algorithm based on a phase change in the fixed magnetization Ising model from statistical physics: Our algorithm is the first to leverage self-induced phase changes as an algorithmic tool. A key component of our algorithm is a careful token passing mechanism ensuring a dispersion broadcast wave will always outpace a compression wave. We also present a highly structured alternative algorithm that gathers by incrementally building a spiral tightly wrapped around the food particle.

The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction (SPAA 2014), a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design. Using hexagon formation as a case study, we first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.

We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16), which can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.

This paper considers the following fundamental maximum throughput routing problem: given a set of k (splittable) multicommodity flows with equal demands in an n-node network, select and route a subset of flows such that the total number of commodities routed that satisfy their demands (i.e., the allor-nothing throughput) is maximized. Our main contribution is the first constant (i.e., independent of k and n) through-putapproximation algorithm for this NP-hard problem, with sublin-ear, namely Õ(√k), edge capacity violation ratio. Our algorithm is based on a clever application of randomized rounding. We also present an interesting application of our result in the context of delay-tolerant network scheduling. We complement our theoretical contribution with extensive simulation in two different scenarios, and find that our algorithm performs significantly better than predicted in theory, achieving an edge capacity violation ratio of at most 3.

The winner of the 2018 Principles of Distributed Computing Doctoral Dissertation Award is Dr. Rati Gelashvili, for his dissertation titled "On the Complexity of Synchronization," written under the supervision of Prof. Nir Shavit at the Massachusetts Institute of Technology.

We consider programmable matter that consists of computationally limited devices (called particles) that are able to self-organize in order to achieve some collective goal without the need for central control or external intervention. We use the geometric amoebot model to describe such self-organizing particle systems, which defines how particles can actively move and communicate with one another. In this paper, we present an efficient local-control algorithm which solves the leader election problem in $$\mathcal {O}(n)$$ asynchronous rounds with high probability, where n is the number of particles in the system. Our algorithm relies only on local information — particles do not have unique identifiers, any knowledge of n, or any sort of global coordinate system — and requires only constant memory per particle.

With the increasing popularity of hand-held mobile devices such as smart phones and smart watches, people are connected more than ever, which enables the information to be created, forwarded, and exchanged at levels that one could not envision just a few years ago. Mobile social networks (MSNs) thrive with the popularity of mobile smart devices and exhibit the properties of social networks. To efficiently disseminate the information within MSNs, there have been research efforts on content-based routing schemes which rely on the network structure and user interest profiles. However, none of these prior works considered the impact of data content during data dissemination in MSNs. However such content is closely related to users' preferences, which have a significant influence on the result of the dissemination. To fill this void, we propose an interest- and content- based dissemination scheme in MSNs, where the contents of the messages, along with the network structural information are taken into consideration. In the proposed scheme, each user is associated with an interest profile and each message is associated with a message content profile. Similarities are measured between the users and the messages given their profiles. We also use PageRank to measure the importance of each user when the network evolves over time. Each piece of information is propagated based on the similarity scores and PageRank selection of relay users. We experimentally show that the proposed scheme achieves higher delivery performance compared to the existing schemes while remaining cost-effective.

We consider programmable matter as a collection of simple computational elements (or particles) with limited (constant-size) memory that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. More specifically, we seek fully distributed, local, and asynchronous algorithms that lead the system to converge to a configuration with small perimeter. We present a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration with no holes. The algorithm takes as input a bias parameter λ, where λ > 1 corresponds to particles favoring inducing more lattice triangles within the particle system. We show that for all λ > 5, there is a constant α > 1 such that at stationarity with all but exponentially small probability the particles are α-compressed, meaning the perimeter of the system configuration is at most α ⋅ pmin, where pmin is the minimum possible perimeter of the particle system. We additionally prove that the same algorithm can be used for expansion for small values of λ in particular, for all 0 < λ < √2, there is a constant β < 1 such that at stationarity, with all but an exponentially small probability, the perimeter will be at least β ⋅ pmax, where pmax is the maximum possible perimeter.

We envision programmable matter consisting of systems of computationally limited devices (which we call particles) that are able to self-organize in order to achieve a desired collective goal without the need for central control or external intervention. Central problems for these particle systems are shape formation and coating problems. In this paper, we present a universal shape formation algorithm which takes an arbitrary shape composed of a constant number of equilateral triangles of unit size and lets the particles build that shape at a scale depending on the number of particles in the system. Our algorithm runs in O(√n) asynchronous execution rounds, where $n$ is the number of particles in the system, provided we start from a well-initialized configuration of the particles. This is optimal in a sense that for any shape deviating from the initial configuration, any movement strategy would require Ω(√n) rounds in the worst case (over all asynchronous activations of the particles). Our algorithm relies only on local information (e.g., particles do not have ids, nor do they know n, or have any sort of global coordinate system), and requires only a constant-size memory per particle.

We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value α such that any ball in the network can be covered by at most 2 α balls of half radius. There are two variants of routing-scheme design: (i) labeled (name-dependent) routing, in which the designer is allowed to rename the nodes so that the names (labels) can contain additional routing information, for example, topological information; and (ii) name-independent routing, which works on top of the arbitrary original node names in the network, that is, the node names are independent of the routing scheme. In this article, given any constant ϵ ∈ (0, 1) and an n -node edge-weighted network of doubling dimension α ∈ O (loglog n ), we present —a (1 + ϵ)-stretch labeled compact routing scheme with ⌈log n ⌉-bit routing labels, O (log 2 n /loglog n )-bit packet headers, and ((1/ϵ) O (α) log 3 n )-bit routing information at each node; —a (9 + ϵ)-stretch name-independent compact routing scheme with O (log 2 n /loglog n )-bit packet headers, and ((1/ϵ) O (α) log 3 n )-bit routing information at each node. In addition, we prove a lower bound: any name-independent routing scheme with o ( n (ϵ/60) 2 ) bits of storage at each node has stretch no less than 9 − ϵ for any ϵ ∈ (0, 8). Therefore, our name-independent routing scheme achieves asymptotically optimal stretch with polylogarithmic storage at each node and packet headers. Note that both schemes are scale-free in the sense that their space requirements do not depend on the normalized diameter Δ of the network. We also present a simpler nonscale-free (9 + ϵ)-stretch name-independent compact routing scheme with improved space requirements if Δ is polynomial in n .

No abstract available.

Providing healthcare to the remote and isolated communities in the Brazilian Amazon poses a significant challenge. In those places, healthcare examinations are mainly run by sporadic visits from medical teams from the main city in the region, Belém. An alternative would be to have local nurses or technicians perform routine clinical examinations, such as ultrasounds on pregnant women, elec whose records could be sent to the doctors in Belém for evaluation. However, due to the lack of modern communication infrastructure in these communities, we propose the use of regularly scheduled boats as data mules to ensure fast and timely delivery of the examination records from those communities to physicians in the city for remote analysis. Unpredictable boat delays and break-downs, as well as high transmission failures due to the harsh environment in the region, mandate the design of robust delay-tolerant routing algorithms. The main contributions of this paper are two-fold: First, we propose the use of fountain codes in order to improve the robustness of opportunistic data routing. Second, we develop a simulation model that incorporates the high unpredictability of the Amazon riverine scenario, accounting for boat delays/breakdowns environmental conditions and individual packet losses, and present extensive simulations results to evaluate our proposed approaches. While the results in this paper focus on remote healthcare applications in the Brazilian Amazon, we envision that our approach may also be used for other remote applications, such as distance education, and other similar scenarios.

Cloud computing heralded an era where resources can be scaled up and down elastically and in an online manner. This paper initiates the study of cost-effective cloud resource allocation algorithms under price discounts, using a competitive analysis approach. We show that for a single resource, the online resource renting problem can be seen as a 2-dimensional variant of the classic online parking permit problem, and we formally introduce the PPP2problem accordingly. Our main contribution is an online algorithm for PPP2which achieves a deterministic competitive ratio of k (under a certain set of assumptions), where k is the number of resource bundles. This is almost optimal, as we also prove a lower bound of k/3 for any deterministic online algorithm. Our online algorithm makes use of an optimal offline algorithm, which may be of independent interest since it is the first optimal offline algorithm for the 1D and 2D versions of the parking permit problem. Finally, we show that our algorithms and results also generalize to multiple resources (i.e., Multi-dimensional parking permit problems).

Imagine that we had a piece of matter that can change its physical properties like shape, density, conductivity, or color in a programmable fashion based on either user input or autonomous sensing. This is the vision behind what is commonly known as programmable matter. Many proposals have already been made for realizing programmable matter, ranging from DNA tiles, shape-changing molecules, and cells created via synthetic biology to reconfigurable modular robotics. We are particularly interested in programmable matter consisting of simple elements called particles that can compute, bond, and move, and the feasibility of solving fundamental problems relevant for programmable matter with these particles. As a model for that programmable matter, we will use a general form of the amoebot model first proposed in SPAA 2014, and as examples of fundamental problems we will focus on leader election and shape formation. For shape formation, we investigate the line formation problem, i.e. we are searching for a local-control protocol so that for any connected structure of particles, the particles will eventually form a line.

Fiber-Wireless (FiWi) networks have received considerable attention in the research community in the last few years as they offer an attractive way of integrating optical and wireless technology. As in every other type of networks, routing plays a major role in FiWi networks. Accordingly, a number of routing algorithms for FiWi networks have been proposed. Most of the routing algorithms attempt to find the “shortest path” from the source to the destination. A recent paper proposed a novel path length metric, where the contribution of a link towards path length computation depends not only on that link but also every other link that constitutes the path from the source to the destination. In this paper we address the problem of computing the shortest path using this path length metric. Moreover, we consider a variation of the metric and also provide an algorithm to compute the shortest path using this variation. As multipath routing provides a number of advantages over single path routing, we consider disjoint path routing with the new path length metric. We show that while the single path computation problem can be solved in polynomial time in both the cases, the disjoint path computation problem is NP-complete. We provide optimal solution for the NP-complete problem using integer linear programming and also provide two approximation algorithms with a performance bound of 4 and 2 respectively. The experimental evaluation of the approximation algorithms produced a near optimal solution in a fraction of a second.

This paper considers the problem of how to efficiently share a wireless medium which is subject to harsh external interference or even jamming. While this problem has already been studied intensively for simplistic single-hop or unit disk graph models, we make a leap forward and study MAC protocols for the SINR interference model (a.k.a. the physical model). We make two contributions. First, we introduce a new adversarial SINR model which captures a wide range of interference phenomena. Concretely, we consider a powerful, adaptive adversary which can jam nodes at arbitrary times and which is only limited by some energy budget. The second contribution of this paper is a distributed MAC protocol which provably achieves a constant competitive throughput in this environment: we show that, with high probability, the protocol ensures that a constant fraction of the non-blocked time periods is used for successful transmissions. Our results also highlight an inherent difference between the SINR model and unit disk graph models.

The term programmable matter refers to matter which has the ability to change its physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion, based upon user input or autonomous sensing. This has many applications like smart materials, autonomous monitoring and repair, and minimal invasive surgery, so there is a high relevance of this topic to industry and society in general. While programmable matter has just been science fiction more than two decades ago, a large amount of research activities can now be seen in this field in the recent years. Often programmable matter is envisioned, as a very large number of small locally interacting computational \emph{particles}. We propose the Amoebot model, a new model which builds upon this vision of programmable matter. Inspired by the behavior of amoeba, the Amoebot model offers a versatile framework to model self-organizing particles and facilitates rigorous algorithmic research in the area of programmable matter.

Peer-to-peer systems rely on a scalable overlay network that enables efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This article shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (slightly extended) skip graph, SKIP + , in polylogarithmic time from any given initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, our algorithm handles individual joins and leaves locally and efficiently.

This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or due to jamming). We consider a wireless network consisting of a set of n honest and reliable nodes within transmission (and interference) range of each other, and we model the external disruptions with a powerful adaptive adversary. This adversary may know the protocol and its entire history and can use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-ϵ)-fraction of the timesteps, for an arbitrary constant ϵ > 0 unknown to the nodes. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant (asymptotically optimal) throughput for the nonjammed time periods under any of the aforementioned adversarial strategies. The derived principles are also useful to build robust applications on top of the MAC layer, and we present an exemplary study for leader election, one of the most fundamental tasks in distributed computing.

Interference constitutes a major challenge to availability for communication networks operating over a shared medium. This paper proposes the medium access (MAC) protocol AntiJam, which achieves a high and fair throughput even in harsh environments. Our protocol mitigates internal interference, requiring no knowledge about the number of participants in the network. It is also robust to intentional and unintentional external interference, e.g., due to coexisting networks or jammers. We model external interference using a powerful reactive adversary that can jam a (1-ε) -portion of the time-steps, where 0 <; ε ≤ 1 is an arbitrary constant. The adversary uses carrier sensing to make informed decisions on when it is most harmful to disrupt communications. Moreover, we allow the adversary to be adaptive and to have complete knowledge of the entire protocol history. AntiJam makes efficient use of the nonjammed time periods and achieves, if ε is constant, a Θ(1)-competitive throughput. In addition, AntiJam features a low convergence time and has excellent fairness properties, such that channel access probabilities do not differ among nodes by more than a small constant factor.

Jamming defense is an important yet challenging problem. In this paper, we study the jamming defense problem in the presence of a smart jammer, who can quickly learn the transmission power of the user and adaptively adjust its transmission power to maximize the damaging effect. We consider both the single-channel model and the multi-channel model. By modeling the problem as a Stackelberg game, we compute the optimal transmission power for the user to maximize its utility, in the presence of a smart jammer. For the single-channel model, we prove the existence and uniqueness of the Stackelberg Equilibrium (SE) by giving closed-form expressions for the SE strategies of both the user and the player. For the multi-channel model, we prove the existence of the SE. We design algorithms for computing the jammer's best response strategy and approximating the user's optimal strategy. Finally, we validate our theoretical analysis through extensive simulations.

Jamming defense is an important yet challenging problem. In this paper, we study the jamming defense problem in the presence of a smart jammer, who can quickly learn the transmission power of the user and adaptively adjust its transmission power to maximize the damaging effect. By modeling the problem as a Stackelberg game, we compute the optimal transmission power for the user to maximize its utility, in spite of the existence of the smart jammer. We prove that the smart jammer is not more damaging than a jammer without the intelligence, provided that the user plays its strategy corresponding to a Stackelberg equilibrium. This nice property is due to the user's ability to predict the jammer's behavior.

This paper initiates the formal study of a fundamental problem: How to efficiently allocate a shared communication medium among a set of K co-existing networks in the presence of arbitrary external interference? While most literature on medium access focuses on how to share a medium among nodes, these approaches are often either not directly applicable to co-existing networks as they would violate the independence requirement, or they yield a low throughput if applied to multiple networks. We present the randomized medium access (MAC) protocol COMAC which guarantees that a given communication channel is shared fairly among competing and independent networks, and that the available bandwidth is used efficiently. These performance guarantees hold in the presence of arbitrary external interference or even under adversarial jamming. Concretely, we show that the co-existing networks can use a Ω(ε2 min{ε, 1 poly(K)})-fraction of the non-jammed time steps for successful message transmissions, where ε is the (arbitrarily distributed) fraction of time which is not jammed.

Intentional interference constitutes a major threat for communication networks operating over a shared medium where availability is imperative. Jamming attacks are often simple and cheap to implement. Today's jammers can perform physical carrier sensing in order to disrupt communication more efficiently, especially in a network of simple wireless devices such as sensor nodes, which usually operate over a single frequency (or a limited frequency band) and which cannot benefit from the use of spread spectrum or other more advanced technologies. This paper proposes the medium access (MAC) protocol ANTIjAM which is provably robust against a powerful reactive adversary who can jam a (1 - ε)-portion of the time steps, where ε is an arbitrary constant. The adversary uses carrier sensing to make informed decisions on when it is most harmful to disrupt communications. Moreover, we allow the adversary to be adaptive and to have complete knowledge of the entire protocol history. Our MAC protocol is able to make efficient use of the nonjammed time periods and achieves a Θ(1) competitive throughput in this harsh scenario, if ε is constant. In addition, ANTIjAM features a low convergence time and has excellent fairness properties in the sense that channel access probabilities among nodes do not differ by more than a small constant factor.

Electing a leader is a fundamental task in distributed computations. Many coordination problems, such as the access to a shared resource, and the resulting inefficiencies, can be avoided by relying on a leader. This paper presents Select, a leader election protocol for wireless networks where nodes communicate over a shared medium. Select is very robust in two respects. First, the protocol is self-stabilizing in the sense that it converges to a correct solution from any possible initial network state (e.g., where no or multiple nodes consider themselves a leader). This is an appealing property, especially for dynamic networks. Second, the described protocol is resilient against a powerful reactive jammer that blocks a significant fraction of all communication rounds. The reactive model is general and of interest beyond jamming (e.g., in the context of co-existing networks). The paper also reports on experimental results obtained from our simulation framework which allows us to study convergence behavior under different types of adversarial jammers.

We study the compact routing problem in networks whose shortest path metrics are decomposable. Decomposable metrics are more general than doubling metrics, growth-bounded metrics, and metrics induced by graphs excluding Kr,r as a minor. In this work, we present both name-dependent and name-independent constant stretch compact routing schemes for bounded decomposable metrics with polylogarithmic storage requirements at each node and polylogarithmic packet headers. Our work is the first to design compact routing schemes with constant stretch for networks as general as decomposable metrics.

Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions, connect the nodes into a graph that has least possible maximum degree in such a way that for each topict, the graph induced by the nodes interested intis connected. We present the first polynomial-time logarithmic approximation algorithm for this problem and prove an almost tight lower bound on the approximation ratio. Our experimental results show that our algorithm drastically improves the maximum degree of publish/subscribe overlay systems. We also propose a variation of the problem by enforcing that each topic-connected overlay network be of constant diameter while keeping the average degree low. We present three heuristics for this problem that guarantee that each topic-connected overlay network will be of diameter 2 and that aim at keeping the overall average node degree low. Our experimental results validate our algorithms, showing that our algorithms are able to achieve very low diameter without increasing the average degree by much.

Publish/subscribe communication systems where nodes subscribe to many different topics of interest are becoming increasingly more common. Designing overlay networks that connect the nodes subscribed to each distinct topic is hence a fundamental problem in these systems. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. Ideally one would like to be able not only to keep the average degree of the nodes low, but also to ensure that all nodes have equally the same degree, giving rise to the following problem: Given a collection of nodes and their topic subscriptions, connect the nodes into a graph with low average and maximum degree such that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial time parameterized sub linear approximation algorithm for this problem. We also propose two heuristics for constructing topic connected networks with low average degree and constant diameter and validate our results through simulations. In fact, the results in this section are a refinement of the preliminary results by Onus and Richa in INFOCOM'09.

Practitioners agree that unreliable links, which sometimes deliver messages and sometime do not, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set of links and assume that these links are reliable. This gap between theory and practice motivates us to investigate how unreliable links affect theoretical bounds on broadcast in radio networks.

This paper introduces the distributed MAC protocol Jade. We consider a multi-hop wireless network with a single communication channel in which a powerful adversary is able to jam (groups of) nodes individually and during a (1 - ε)-fraction of the entire time, where ε > 0 is an arbitrarily small constant. Despite this harsh environment, Jade exploits the few non-jammed slots effectively and guarantees a high throughput.

Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions connect the nodes into a graph which has least possible maximum degree and in such a way that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial time logarithmic approximation algorithm for this problem and prove an almost tight lower bound on the approximation ratio. Our experimental results show that our algorithm drastically improves the maximum degree of publish/subscribe overlay systems. We also propose a variation of the problem by enforcing that each topic-connected overlay network be of constant diameter, while keeping the average degree low. We present a heuristic for this problem which guarantees that each topic-connected overlay network will be of diameter 2 and which aims at keeping the overall average node degree low. Our experimental results validate our algorithm showing that our algorithm is able to achieve very low diameter without increasing the average degree by much.

Peer-to-peer systems rely on scalable overlay networks that enable efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This paper shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (variant of the) skip graph in polylogarithmic time from any initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, individual joins and leaves are handled locally and require little work.

Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions connect the nodes into a graph which has low average and maximum degree and in such a way that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial time parameterized sublinear approximation algorithm for this problem.

Dealing with interference is one of the primary challenges to solve in the design of protocols for wireless ad-hoc networks. Most of the work in the literature assumes localized or hop-based interference models in which the effect of interference is neglected beyond a certain range from the transmitter. However, interference is a more complex phenomenon that cannot, in general, be captured by localized models, implying that protocols based on such models are not guaranteed to work in practice. This paper is the first to present and rigorously analyze a distributed dominating set protocol for wireless ad-hoc networks with O(1) approximation bound based on the physical interference model, which accounts for interference generated by all nodes in the network. The proposed protocol is fully distributed, randomized, and extensively uses physical carrier sensing to reduce message overhead. It does not need node identifiers or any kind of prior information about the system, and all messages are of constant size (in bits). We prove that, by appropriately choosing the threshold for physical carrier sensing, the protocol stabilizes within a logarithmic number of communication rounds, w.h.p., which is faster than the runtime of any known distributed protocol without prior knowledge about the system under any wireless model that does not abstract away collisions.

In this paper we consider the problem of designing a medium access control (MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes that are within the transmission range of each other. In addition to these nodes there is an adversary. The adversary may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-epsilon)-fraction of the time steps, for an arbitrary constant epsilon>0, but it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant throughput for the non-jammed time steps under any adversarial strategy above. We also show that our protocol is very energy efficient and that it can be extended to obtain a robust and efficient protocol for leader election and the fair use of the wireless channel.

No abstract available.

We consider the problem of designing a distributed algorithm that, given an arbitrary connected graph G of nodes with unique labels, converts G into a sorted list of nodes. This algorithm should be as simple as possible and, for scalability, should guarantee a polylogarithmic runtime as well as at most a polylogarithmic increase in the degree of each node during its execution. Furthermore, it should be self-stabilizing, that is, it should be able to eventually construct a sorted list from any state in which the graph is connected. It turns out that satisfying all of these demands at the same time is not easy. Our basic approach towards this goal is the so-called linearization technique: each node v repeatedly does the following with its neighbors: for its left (i.e., smaller) neighbors u1, …, uk in the order of decreasing labels, v replaces {v, u1}, …, {v, uk} by {v, u1}, {u1,u2},…, {uk − 1,uk}, and for its right (i.e., larger) neighbors w1, …, wℓ in the order of increasing labels, v replaces {v, w1}, …, {v, wℓ} by {v, w1}, {w1, w2}, …, {wℓ − 1, wℓ}. As shown in this paper, this technique transforms any connected graph into a sorted list, but there are graphs for which this can take a long time. Hence, we propose several extensions of the linearization technique and experimentally evaluate their performance. Our results indicate that some of these have a polylogarithmic performance, so there is hope that there are distributed algorithms that can achieve all of our goals above.

We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek name-independent routing schemes with (1+ε) stretch and polylogarithmic storage at each node: since existing lower bound precludes such a scheme, we relax our guarantees to allow for (i) a small fraction of nodes to have large storage, say size of O(n log n) bits, or (ii) a small fraction of source-destination pairs to have larger, but still constant, stretch.

We consider the problem of name-independent routing in doubling metrics. A doubling metric is a metric space whose doubling dimension is a constant, where the doubling dimension of a metric space is the least value α such that any ball of radius r can be covered by at most 2 α balls of radius r/2. Given any δ> 0 and a weighted undirected network G whose shortest path metric d is a doubling metric with doubling dimension α, we present a name-independent routing scheme for G with (9+δ)-stretch, (2+ 1 δ)O(α) (log ∆) 2 (log n)bit routing information at each node, and packet headers of size O(log n), where ∆ is the ratio of the largest to the smallest shortest path distance in G. In addition, we prove that for any ǫ ∈ (0, 8), there is a doubling metric network G with n nodes, doubling dimension α ≤ 6 − log ǫ, and ∆ = O(2 1/ǫ n) such that any name-independent routing scheme on G with routing information at each node of size o(n (ǫ/60)2)-bits has stretch larger than 9 − ǫ. Therefore assuming that ∆ is bounded by a polynomial on n, our algorithm basically achieves optimal stretch for name-independent routing in doubling metrics with packet header size and routing information at each node both bounded by a polylogarithmic function of n.

Routing algorithms with time and message complexities that are provably low and independent of the total number of nodes in the network are essential for the design and operation of very large scale wireless mobile ad hoc networks (MANETs). In this paper, we develop and analyze Cluster Overlay Broadcast (COB), a low-complexity routing algorithm for MANETs. COB runs on top of a one-hop cluster cover of the network, which can be created and maintained using, for instance, the Least Cluster Change (LCC) algorithm. We formally prove that the LCC algorithm maintains a cluster cover with a constant density of cluster leaders with minimal update cost. COB discovers routes by flooding (broadcasting) route requests through the network of cluster leaders with a doubling radius technique. Building on the constant density property of the network of cluster leaders, we formally prove that, if there exists a route from a source to a destination node with a minimum hop count of A, then COB discovers a route with at most O(/spl Delta/) hops from the source to the destination node in at most O(/spl Delta/) time and by sending at Most O(/spl Delta//sup 2/) messages. We prove this result for arbitrary node distributions and mobility patterns and also show that COB adapts asymptotically optimally to the mobility of the nodes. In our simulation experiments, we examine the network layer performance of COB, compare it with Dynamic Source Routing, and investigate the impact of the MAC layer on COB routing.

Task to resource mapping problems are encountered during (i) hardware-software co-design and (ii) performance optimization of Network Processor systems. The goal of the first problem is to find the task to resource mapping that minimizes the design cost subject to all design constraints. The goal of the second problem is to find the mapping that maximizes the performance, subject to all architectural constraints. To meet the design goals in performance, it may be necessary to allow multiple packets to be inside the system at any given instance of time and this may give rise to the resource contention between packets. In this paper, a Randomized Rounding (RR) based solution is presented for the task to resource mapping and scheduling problem. We also proposed two techniques to detect and eliminate the resource contention. We evaluate the efficacy of our RR approach through extensive simulation. The simulation results demonstrate that this approach produces near optimal solutions in almost all instances of the problem in a fraction of time needed to find the optimal solution. The quality of the solution produced by this approach is also better than often used list scheduling algorithm for task to resource mapping problem. Finally, we demonstrate with a case study, the results of a Network Processor design and scheduling problem using our techniques.

An important problem for wireless ad hoc networks has been to design overlay networks that allow time- and energy-efficient routing. Many local-control strategies for maintaining such overlay networks have already been suggested, but most of them are based on an oversimplified wireless communication model. In this paper, we suggest a model that is much more general than previous models. It allows the path loss of transmissions to significantly deviate from the idealistic unit disk model and does not even require the path loss to form a metric. Also, our model is apparently the first proposed for algorithm design that does not only model transmission and interference issues but also aims at providing a realistic model for physical carrier sensing. Physical carrier sensing is needed so that our protocols do not require any prior information (not even an estimate on the number of nodes) about the

We describe logarithmic approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage--time product. This improves upon the best previous approximation bounds of Even, Naor, Rao, and Schieber [J. ACM, 47 (2000), pp. 585--616] for these problems by a factor of $\Omega$(log log n). We use the lower bound provided by the volume W of a spreading metric for each of the ordering problems above (as defined by Even et al.) in order to find a solution with cost at most a logarithmic factor times W for these problems. We develop a divide-and-conquer strategy where the cost of a solution to a problem at a recursive level is C plus the cost of a solution to the subproblems at this level, and where the spreading metric volume on the subproblems is less than the original volume by $\Omega$(C log n), ensuring that the resulting solution has cost O(log n) times the original spreading metric volume. We note that this is an existentially tight bound on the relationship between the spreading metric volume and the true optimal values for these problems. For planar graphs, we combine a structural theorem of Klein, Plotkin, and Rao [Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 682--690] with our new recursion technique to show that the spreading metric cost volumes are within an O(log log n) factor of the cost of an optimal solution for the minimum linear arrangement, and the minimum containing interval graph problems.

Consider an arbitrary distributed network in which large numbers of objects are continuously being created, replicated, and destroyed. A basic problem arising in such an environment is that of organizing a data tracking scheme for locating object copies. In this paper, we present a new tracking scheme for locating nearly copies of replicated objects in arbitrary distributed environments.

This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within $O(\Delta / \alpha)$ steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most $O((d^2 \log n)/\alpha)$, where $\Delta$ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and $\alpha$ is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion $\alpha$, and for any value $\Delta$, there exists an initial distribution of tokens with imbalance $\Delta$ for which the time to reduce the imbalance to even $\Delta/2$ is at least $\Omega(\Delta/\alpha)$. The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains $\Omega((d^2 \log n) / \alpha)$. Furthermore, we show that upon reaching a state with a global imbalance of $O((d^2 \log n)/\alpha)$, the time for this algorithm to locally balance the network can be as large as $\Omega(n^{1/2})$. We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step.

In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup time. Our algorithms are based on the idea of having each message choose a route from two possibilities, a technique that has previously proven successful in simpler load balancing settings. As an application of our techniques, we propose a novel design for a data server.

Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time.To ensure both fast access to the objects as well as efficient utilization of network resources, it is desirable that each access request be satisfied by a copy "close" to the requesting node.Unfortunately, it is not clear how to efficiently achieve this goal in a dynamic, distributed environment in which large numbers of objects are continuously being created, replicated, and destroyed,In this paper, we design a simple randomized algorithm for accessing shared objects that tends to satisfy each access request with a nearby copy.The algorithm is based on a novel mechanism to maintain and distribute information about object locations, and requires only a smaIl amount of additional memory at each node.We analyze our access scheme for a class of cost functions that captures the hierarchical nature of wide-area networks.We show that under the particular cost model considered: (i) the expected cost of an individual access is asymptotically optimal, and (ii) if objects are sufficiently large, the memory used for objects dominates the additional memory used by our algorithm with high probability.We also address dynamic changes in both the network as well as the set of object copies.

. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d + 1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(\\Delta=ff) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d 2 log n)=ff), where \\Delta is the maximum difference between the number tokens at any node initially and the average number of tokens, n is the number of nodes in the network, and ff is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion ff, and for any value \\Delta, there exists an initial distribution of tokens with imbalance \\Delta for which the time to reduce the imbalance to even \\Delta=2 is at least \\Omega\\Gammaa =ff). The bound on the final imbalance is tight in the sense that there exists a cl...