Distributed Computing

We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round,

O

(log

n

) bits can be transmitted over each edge (a.k.a. the

CONGEST

model). The first algorithm is based on a simple and new approach for analyzing random edge sampling, which we call the

random layering technique

. For any weighted graph and any

ε

 ∈ (0, 1), the algorithm with high probability finds a cut of size at most

O

(

ε

− 1

λ

) in

$O(D) + \tilde{O}(n^{1/2 + \epsilon})$

rounds, where

λ

is the size of the minimum cut and the

$\tilde{O}$

-notation hides poly-logarithmic factors in

n

. In addition, based on a centralized algorithm due to Matula [SODA ’93], we present a randomized distributed algorithm that with high probability computes a cut of size at most (2 + 

ε

)

λ

in

$\tilde{O}((D+\sqrt{n})/\epsilon^5)$

rounds for any

ε

 > 0.

The time complexities of our algorithms almost match the

$\tilde{\Omega}(D + \sqrt{n})$

lower bound of Das Sarma et al. [STOC ’11], thus leading to an answer to an open question raised by Elkin [SIGACT-News ’04] and Das Sarma et al. [STOC ’11].

To complement our upper bound results, we also strengthen the

$\tilde{\Omega}(D + \sqrt{n})$

lower bound of Das Sarma et al. by extending it to unweighted graphs. We show that the same lower bound also holds for unweighted multigraphs (or equivalently for weighted graphs in which

O

(

w

log

n

) bits can be transmitted in each round over an edge of weight

w

). For unweighted simple graphs, we show that computing an

α

-approximate minimum cut requires time at least

$\tilde{\Omega}(D + \sqrt{n}/\alpha^{1/4})$

.

We consider a number of fundamental statistical and graph problems in the message-passing model, where we have

k

machines (sites), each holding a piece of data, and the machines want to jointly solve a problem defined on the union of the

k

data sets. The communication is point-to-point, and the goal is to minimize the total communication among the

k

machines. This model captures all point-to-point distributed computational models with respect to minimizing communication costs. Our analysis shows that exact computation of many statistical and graph problems in this distributed setting requires a prohibitively large amount of communication, and often one cannot improve upon the communication of the simple protocol in which all machines send their data to a centralized server. Thus, in order to obtain protocols that are communication-efficient, one has to allow approximation, or investigate the distribution or layout of the data sets.

Topology recognition is one of the fundamental distributed tasks in networks. Each node of an anonymous network has to deterministically produce an isomorphic copy of the underlying graph, with all ports correctly marked. This task is usually unfeasible without any a priori information. Such information can be provided to nodes as

advice

. An oracle knowing the network can give a (possibly different) string of bits to each node, and all nodes must reconstruct the network using this advice, after a given number of rounds of communication. During each round each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. The time of completing topology recognition is the number of rounds it takes, and the size of advice is the maximum length of a string given to nodes.

We investigate tradeoffs between the time in which topology recognition is accomplished and the minimum size of advice that has to be given to nodes. We provide upper and lower bounds on the minimum size of advice that is sufficient to perform topology recognition in a given time, in the class of all graphs of size

n

and diameter

D

 ≤ 

αn

, for any constant

α

 < 1. In most cases, our bounds are asymptotically tight. More precisely, if the allotted time is

D

 − 

k

, where 0 < 

k

 ≤ 

D

, then the optimal size of advice is Θ((

n

2

log

n

)/(

D

 − 

k

 + 1)). If the allotted time is

D

, then this optimal size is Θ(

n

log

n

). If the allotted time is

D

 + 

k

, where 0 < 

k

 ≤ 

D

/2, then the optimal size of advice is Θ(1 + (log

n

) /

k

). The only remaining gap between our bounds is for time

D

 + 

k

, where

D

/2 < 

k

 ≤ 

D

. In this time interval our upper bound remains

O

(1 + (log

n

) /

k

), while the lower bound (that holds for any time) is 1. This leaves a gap if

D

 ∈ 

o

(log

n

). Finally, we show that for time 2

D

 + 1, one bit of advice is both necessary and sufficient.

Our results show how sensitive is the minimum size of advice to the time allowed for topology recognition: allowing just one round more, from

D

to

D

 + 1, decreases exponentially the advice needed to accomplish this task.

We present a deterministic obstruction-free implementation of leader election from

$O(\sqrt n)$

atomic

O

(log

n

)-bit registers in the standard asynchronous shared memory system with

n

processes. We provide also a technique to transform any deterministic obstruction-free algorithm, in which any process can finish if it runs for

b

steps without interference, into a randomized wait-free algorithm for the oblivious adversary, in which the expected step complexity is polynomial in

n

and

b

. This transformation allows us to combine our obstruction-free algorithm with the leader election algorithm by Giakkoupis and Woelfel [21], to obtain a fast randomized leader election (and thus test-and-set) implementation from

$O(\sqrt n)$

O

(log

n

)-bit registers, that has expected step complexity

O

(log

 ∗ 

n

) against the oblivious adversary.

Our algorithm provides the first sub-linear space upper bound for obstruction-free leader election. A lower bound of Ω(log

n

) has been known since 1989 [29]. Our research is also motivated by the long-standing open problem whether there is an obstruction-free consensus algorithm which uses fewer than

n

registers.

We do a game-theoretic analysis of leader election, under the assumption that each agent prefers to have some leader than to have no leader at all. We show that it is possible to obtain a

fair

Nash equilibrium, where each agent has an equal probability of being elected leader, in a completely connected network, in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In the asynchronous setting, Nash equilibrium is not quite the right solution concept. Rather, we must consider

ex post

Nash equilibrium; this means that we have a Nash equilibrium no matter what a scheduling adversary does. We show that ex post Nash equilibrium is attainable in the asynchronous setting in all the networks we consider, using a protocol with bounded running time. However, in the asynchronous setting, we require that

n

 > 2. We can get a fair

ε-Nash

equilibrium if

n

 = 2 in the asynchronous setting, under some cryptographic assumptions (specifically, the existence of a pseudo-random number generator and polynomially-bounded agents), using ideas from bit-commitment protocols. We then generalize these results to a setting where we can have deviations by a coalition of size

k

. In this case, we can get what we call a fair

k

-resilient equilibrium if

n

 > 2

k

; under the same cryptographic assumptions, we can a get a

k

-resilient equilibrium if

n

 = 2

k

. Finally, we show that, under minimal assumptions, not only do our protocols give a Nash equilibrium, they also give a

sequential

equilibrium [23], so players even play optimally off the equilibrium path.

This paper focuses on

compact

deterministic self-stabilizing solutions for the leader election problem. When the protocol is required to be

silent

(i.e., when communication content remains fixed from some point in time during any execution), there exists a lower bound of Ω(log

n

) bits of memory per node participating to the leader election (where

n

denotes the number of nodes in the system). This lower bound holds even in rings. We present a new deterministic (non-silent) self-stabilizing protocol for

n

-node rings that uses only

O

(loglog

n

) memory bits per node, and stabilizes in

O

(

n

log

2

n

) time. Our protocol has several attractive features that make it suitable for practical purposes. First, the communication model matches the one that is expected by existing compilers for real networks. Second, the size of the ring (or any upper bound for this size) needs not to be known by any node. Third, the node identifiers can be of various sizes. Finally, no synchrony assumption besides a weak fair scheduler is assumed. Therefore, our result shows that, perhaps surprisingly, trading silence for exponential improvement in term of memory space does not come at a high cost regarding stabilization time, neither it does regarding minimal assumptions about the framework for our algorithm.

In this research, we present the first time-optimal self stabilizing algorithm for synchronous distributed spanning tree construction, assuming the standard shared registers size (

O

(log

n

) bits, where

n

stands for the number of processes in the system), or, similarly, standard message size. Previous algorithms with

O

(

diameter

) stabilization time complexity assumed that a larger message can be sent through each link in one time unit. Hence, when assuming the standard message size, the time complexity of previous algorithms was not

O

(

diameter

). The current algorithm stabilizes in

O

(

diameter

) time without having previous knowledge of the network size or diameter. The only assumption we make is that we have some polynomial (possibly very large) given upper bound on the network size. However, the time complexity of the algorithm does not depend on that upper bound. Using our results, most known distributed global tasks, such as distributed reset, can be performed in a relatively easy way and in optimal time. As a building block, we present a new self stabilizing silent phase clock algorithm for synchronous networks (based on a known non-silent algorithm). It is optimal in time too. We believe it may be an interesting contribution by itself.

Guerraoui and Kapalka defined opacity as a safety criterion for transactional memory algorithms in 2008. Researchers have shown how to prove opacity, while little is known about pitfalls that can lead to non-opacity. In this paper, we identify two problems that lead to non-opacity, we present automatic tool support for finding such problems, and we prove an impossibility result. We first show that the well-known TM algorithms DSTM and McRT don’t satisfy opacity. DSTM suffers from a write-skew anomaly, while McRT suffers from a write-exposure anomaly. We then prove that for direct-update TM algorithms, opacity is incompatible with a liveness criterion called local progress, even for fault-free systems. Our result implies that if TM algorithm designers want both opacity and local progress, they should avoid direct-update algorithms.

We present

Lilac

-TM, the first locality-aware Distributed Software Transactional Memory (DSTM) implementation.

Lilac

-TM is a fully decentralized lease-based replicated DSTM. It employs a novel self-optimizing lease circulation scheme based on the idea of dynamically determining whether to migrate transactions to the nodes that own the leases required for their validation, or to demand the acquisition of these leases by the node that originated the transaction. Our experimental evaluation establishes that

Lilac

-TM provides significant performance gains for distributed workloads exhibiting data locality, while typically incurring little or no overhead for non-data local workloads.

Multiversion software transactional memory (STM) allows a transaction to read old values of a recently updated object, after which the transaction may serialize

before

transactions that committed earlier in physical time. This ability to “commit in the past” is particularly appealing for long-running read-only transactions, which may otherwise starve in many STM systems, because short-running peers modify data out from under them before they have a chance to finish.

Most previous approaches to multiversioning have been designed as an integral part of some larger STM system, and have assumed an object-oriented, garbage-collected language. We describe, instead, how multiversioning may be implemented on top of an almost arbitrary “word-based” STM system. To the best of our knowledge, ours is the first work (for any kind of STM) to combine bounded space consumption with guaranteed wait freedom for read-only transactions (in the form presented here, it may require writers to be blocking). We make no assumptions about data or metadata layout, though we do require that the base system provide a hash function with certain ordering properties. We neither require nor interfere with automatic garbage collection. Privatization safety can be ensured—without compromising wait freedom for readers—either by forcing privatizing writers to wait for all extant readers or by requiring that programmers explicitly identify the data being privatized.

Transactional Memory (TM) provides a strong abstraction to tackle the challenge of synchronizing concurrent tasks that access shared state. Yet, most TMs do not allow a single transaction to contain parallel code. We propose an efficient parallel nesting algorithm to explore existing latent parallelism within a transaction. If this intra-transaction parallelism has reduced conflict probability (compared to the inter-transaction parallelism), then it may be worthy to execute less transactions at a given time, but have each one parallelized and using several available cores.

We provide practical support for parallel nesting in the first lock-free parallel nesting algorithm with support for multi-versions. Our prototype builds over an available multi-version TM, which we outperform on standard benchmarks by up to 2.8×. We show improvements over parallel nesting alternatives of up to 3.6×.

We address the problem of implementing a distributed data-structure that can tolerate process crash failures in an asynchronous message passing system, while guaranteeing correctness (linearizability with respect to a given sequential specification) and resiliency (the operations are guaranteed to terminate, as long as a majority of the processes do not fail). We consider a class of data-structures whose operations can be classified into two kinds:

update

operations that can modify the data-structure but do not return a value and

read

operations that return a value, but do not modify the data-structure. We show that if every pair of update operations commute or nullify each other, then resilient linearizable replication is possible. We propose an algorithm for this class of data-structures with a message complexity of two message round trips for read operations and O(n) round trips for update operations. We also show that if there exists some reachable state where a pair of idempotent update operations neither commute nor nullify each other, resilient linearizable replication is not possible.

Most published concurrent data structures which avoid locking do not provide any fairness guarantees. That is, they allow processes to access a data structure and complete their operations arbitrarily many times before some other trying process can complete a single operation. Such a behavior can be prevented by enforcing fairness. However, fairness requires waiting or helping. Helping techniques are often complex and memory consuming. Does it mean that for enforcing fairness it is best to use locks? The answer is negative. We show that it is possible to automatically transfer any non-blocking or wait-free data structure into a similar data structure which satisfies a strong fairness requirement, without using locks and with limited waiting. The fairness we require is that no beginning process can complete two operations on a given resource while some other process is kept waiting on the same resource. Our approach allows as many processes as possible to access a shared resource at the same time as long as fairness is preserved. To achieve this goal, we introduce and solve a

new

synchronization problem, called

fair synchronization

. Solving the new problem enables us to add fairness to existing implementations of concurrent data structures, and to transform any solution to the mutual exclusion problem into a fair solution.

We devise efficient gossip-based protocols for some fundamental distributed tasks. The protocols assume an

n

-node network supporting point-to-point communication, and in every round, each node exchanges information of size

O

(log

n

) bits with (at most) one other node.

We first consider the

renaming

problem, that is, to assign distinct IDs from a small ID space to all nodes of the network. We propose a renaming protocol that divides the ID space among nodes using a natural push or pull approach, achieving logarithmic round complexity with ID space {1,…,(1 + 

ε

)

n

}, for any fixed

ε

 > 0. A variant of this protocol solves the

tight

renaming problem, where each node obtains a unique ID in {1,…,

n

}, in

O

(log

2

n

) rounds.

Next we study the following

sorting

problem. Nodes have consecutive IDs 1 up to

n

, and they receive numerical values as inputs. They then have to exchange those inputs so that in the end the input of rank

k

is located at the node with ID

k

. Jelasity and Kermarrec [20] suggested a simple and natural protocol, where nodes exchange values with peers chosen uniformly at random, but it is not hard to see that this protocol requires Ω(

n

) rounds. We prove that the same protocol works in

O

(log

2

n

) rounds if peers are chosen according to a non-uniform power law distribution.

O

(log

n

) rounds has been a well known upper bound for rumor spreading using

push&pull

in the

random phone call

model (i.e., uniform gossip in the complete graph). A matching lower bound of Ω(log

n

) is also known for this special case. Under the assumptions of this model and with a natural addition that nodes can call a partner once they learn its address (e.g., its IP address) we present a new distributed, address-oblivious and robust algorithm that uses

push&pull

with pointer jumping to spread a rumor to all nodes in only

$O(\sqrt{\log n})$

rounds, w.h.p. This algorithm can also cope with

$F= o(n/2^{\sqrt{\log n}})$

node failures, in which case all but

O

(

F

) nodes become informed within

$O(\sqrt{\log n})$

rounds, w.h.p.

Concurrent data structures are often used with large concurrent software. An

iterator

that traverses the data structure items is a highly desirable interface that often exists for sequential data structures but is missing from (almost all) concurrent data-structure implementations. In this paper we introduce a technique for adding a linearizable wait-free iterator to a wait-free or a lock-free data structure that implements a set. We use this technique to implement an iterator for the wait-free and lock-free linked-lists and for the lock-free skip-list.

This paper introduces new lock-free and wait-free unordered linked list algorithms. The composition of these algorithms according to the fast-path-slow-path methodology, a recently devised approach to creating fast wait-free data structures, is nontrivial, suggesting limitations to the applicability of the fast-path-slow-path methodology. The list algorithms introduced in this paper are shown to scale well across a variety of benchmarks, making them suitable for use both as standalone lists, and as the foundation for wait-free stacks and non-resizable hash tables.

A randomized construction of unbounded snapshots objects from atomic registers is given. The cost of each snapshot operation is

O

(log

3

n

) atomic register steps with high probability, where

n

is the number of processes, even against an adaptive adversary. This is an exponential improvement on the linear cost of the previous best known unrestricted snapshot construction [7,8] and on the linear lower bound for deterministic constructions [9], and does not require limiting the number of updates as in previous sublinear constructions [4]. One of the main ingredients in the construction is a novel

randomized helping

technique that allows out-of-date processes to obtain up-to-date information without running into covering lower bounds.

We give an adaptive algorithm in which processes use multi-writer multi-reader registers to acquire exclusive write access to their own single-writer, multi-reader registers. It is the first such algorithm that uses a number of registers linear in the number of participating processes. Previous adaptive algorithms require at least Θ(

n

3/2

) registers.

We present a new wait-free implementation of a

Fetch

&

Inc

object shared by

n

processes from read-write registers and load-linked/store-conditional (LL/SC) objects. The step complexity of each

FI

operation is

O

(log

n

), which is optimal. Our implementation uses

O

( max {

m

,

n

}) objects, each of which stores

O

(log

m

) bits, where

m

is the number of

FI

operations that are performed. For large

m

, the number of objects can be reduced to

O

(

n

2

). Similar implementations of other objects, such as

Fetch

&

Inc

and

Swap

, are also obtained.

Our implementation uses a new object, called an

Aggregator

. It supports an operation which, if successful, puts a value into its in-buffer that can depend on the value that is currently there, an operation that copies the value in its in-buffer to its out-buffer, provided its out-buffer is empty, and an operation that empties its out-buffer. We show how to implement an

Aggregator

from a small constant number of LL/SC objects so that all three operations have constant step complexity.

Active replication is commonly built on top of the atomic broadcast primitive. Passive replication, which has been recently used in the popular ZooKeeper coordination system, can be naturally built on top of the primary-order atomic broadcast primitive. Passive replication differs from active replication in that it requires processes to cross a

barrier

before they become primaries and start broadcasting messages. In this paper, we propose a barrier function

τ

that explains and encapsulates the differences between existing primary-order atomic broadcast algorithms. We also show that implementing primary-order atomic broadcast on top of a generic consensus primitive and

τ

inherently results in higher time complexity than atomic broadcast, as witnessed by existing algorithms. We overcome this problem by presenting an alternative, primary-order atomic broadcast implementation that builds on top of a generic consensus primitive and uses consensus itself to form a barrier. This algorithm is modular and matches the time complexity of existing

τ

-based algorithms.

Consider a group of nodes connected through multiple-access channels and the only observable feedback on the channel is a binary value: either one or more nodes have transmitted (busy), or no node has transmitted (idle). The channel model thus described is called

Beeping Model

and captures computation in hardware using a group of sequential circuit modules connected by a logic-OR gate. It has also been used to study chemical signaling mechanisms between biological cells and carrier-sensing based wireless communication.

In this paper, we study the distributed complexity of two fundamental problems in the Beeping Model. In both problems, there is a set of nodes each with a unique identifier

i

 ∈ {1,2,…,

n

}. A subset of the nodes

A

 ⊆ {1,2,…,

n

} is called

active nodes

. In the

Membership Problem

, every node needs to find out the identifiers of all active nodes. In the

Conflict Resolution Problem

, the goal is to let every active node use the channel alone (without collision) at least once.

We derive two results that characterize the distributed complexity of these problems. First, we prove that in the Beeping Model the two above problems are equally hard. This is in stark contrast to traditional channel models with ternary feedback in which the membership problem is strictly harder than conflict resolution. The equivalence result also leads to a randomized lower bound for conflict resolution, which shows a relative powerlessness of randomization in the beeping model. Secondly, we give a new deterministic algorithm for the problems that achieves the best known parallelization among all practical algorithms.

Frequency hopping is a central method in wireless communication, offering improved resistance to adversarial interference and interception attempts, and easy non-coordinated control in dynamic environments. In this paper, we introduce a new model that supports a rigorous study of frequency hopping in adversarial settings. We then propose new frequency hopping protocols that allow a sender-receiver pair to essentially use the full communication capacity, despite a powerful adversary that can scan and jam a significant amount of the ongoing transmissions.

We consider capacity maximization algorithms for wireless networks with changing availabilities of spectrum. There are

n

sender-receiver pairs (called

links

) and

k

channels. We consider an iterative round-based scenario, where in each round the set of channels available to each link changes. Each link independently decides about access to one available channel in order to implement a successful transmission. Transmissions are subject to interference and noise, and we use a general approach based on affectance to define which attempts are successful. This includes recently popular interference models based on SINR.

Our main result is that efficient distributed algorithms from sleeping-expert regret learning can be used to obtain constant-factor approximations if channel availability is stochastic and independently distributed among links. In general, sublinear approximation factors cannot be obtained without the assumption of stochastic independence among links. A direct application of the no-external regret property is not sufficient to guarantee small approximation factors.

An increasing amount of attention is being turned toward the study of distributed algorithms in wireless network models based on calculations of the

signal to noise and interference ratio

(SINR). In this paper we introduce the

ad hoc SINR

model, which, we argue, reduces the gap between theory results and real world deployment. We then use it to study upper and lower bounds for the canonical problem of broadcast on the graph induced by both

strong

and

weak

links. For strong connectivity broadcast, we present a new randomized algorithm that solves the problem in

O

(

D

log(

n

)polylog(

R

)) rounds in networks of size

n

, with link graph diameter

D

, and a ratio between longest and shortest links bounded by

R

. We then show that for

back-off

style algorithms (a common type of algorithm where nodes do not explicitly coordinate with each other) and

compact

networks (a practice-motivated model variant that treats the distance from very close nodes as equivalent), there exist networks in which centralized algorithms can solve broadcast in

O

(1) rounds, but distributed solutions require Ω(

n

) rounds. We then turn our attention to weak connectivity broadcast, where we show a similar Ω(

n

) lower bound for all types of algorithms, which we (nearly) match with a back-off style

O

(

n

log

2

n

)-round upper bound. Our broadcast algorithms are the first known for SINR-style models that do not assume synchronous starts, as well as the first known not to depend on power control, tunable carrier sensing, geographic information and/or exact knowledge of network parameters.

In the advent of large-scale multi-hop wireless technologies, such as MANET, VANET, iThings, it is of utmost importance to devise efficient distributed protocols to maintain network architecture and provide basic communication tools. One of such fundamental communication tasks is broadcast, also known as a 1-to-all communication. We present a randomized algorithm that accomplishes broadcast in

O

(

D

 + log(1/

δ

)) rounds with probability at least 1 − 

δ

on

any

uniform-power network of

n

nodes and diameter

D

, when each station is equipped with its coordinates and local estimate of network density. Next, we develop algorithms for the model where no estimate of local density is available, except of the value

n

of the size of a given network. First, we provide a simple and almost oblivious algorithm which accomplishes broadcast in

O

(

D

log

n

(log

n

 + log(1/

δ

))) rounds with probability at least 1 − 

δ

. We further enhance this algorithm with more adaptive leader election routine and show that the resulting protocol achieves better time performance

O

((

D

 + log(1/

δ

))log

n

) with probability at least 1 − 

δ

. Our algorithms are the first provably efficient and well-scalable randomized distributed solutions for the (global) broadcast task in the ad hoc setting with coordinates. This could be also contrasted with the complexity of broadcast by weak devices, for which such scalable algorithms (with respect to

D

and log

n

) cannot be obtained [11].

Secure multiparty computation (MPC) allows a set of

n

parties to securely compute a function of their private inputs against an adversary corrupting up to

t

parties. Over the previous decade, the communication complexity of

synchronous

MPC protocols could be improved to

$\mathcal{O}(n)$

per multiplication, for various settings. However, designing an

asynchronous

MPC (AMPC) protocol with linear communication complexity was not achieved so far. We solve this open problem by presenting two AMPC protocols with the corruption threshold

t

 < 

n

/ 4. Our first protocol is

statistically

secure (i.e. involves a negligible error) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Θ(

n

). Our second protocol is

perfectly

secure (i.e. error free) in a

hybrid

setting, where one round of communication is assumed to be synchronous, and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Θ(

n

2

).

Like other efficient MPC protocols, we employ Beaver’s circuit randomization approach (Crypto ’91) and prepare shared random multiplication triples. However, in contrast to previous protocols where triples are prepared by first generating two random shared values which are then multiplied distributively, in our approach each party prepares its own multiplication triples. Given enough such shared triples (potentially partially known to the adversary), we develop a method to extract shared triples unknown to the adversary, avoiding communication-intensive multiplication protocols. This leads to a framework of independent interest.

We demonstrate the feasibility of end-to-end communication in highly unreliable networks. Modeling a network as a graph with vertices representing nodes and edges representing the links between them, we consider two forms of unreliability: unpredictable edge-failures, and deliberate deviation from protocol specifications by corrupt and maliciously controlled nodes.

We present a routing protocol for end-to-end communication that is simultaneously resilient to both forms of unreliability. In particular, we prove that our protocol is

secure

against arbitrary actions of the corrupt nodes controlled by a polynomial-time adversary, achieves

correctness

(Receiver gets

all

of the messages from Sender, in-order and without modification), and enjoys provably optimal throughput performance, as measured using

competitive analysis

. Competitive analysis is utilized to provide protocol guarantees again malicious behavior without placing limits on the number of the corrupted nodes in the network.

Furthermore, our protocol does not incur any asymptotic memory overhead as compared to other protocols that are unable to handle malicious interference of corrupt nodes. In particular, our protocol requires

O

(

n

2

) memory per processor, where

n

is the size of the network. This represents an

O

(

n

2

) improvement over all existing protocols that have been designed for this network model.

We present a distributed asynchronous algorithm that, for every undirected weighted

n

-node graph

G

, constructs name-independent routing tables for

G

. The size of each table is

$\tilde{O}(\sqrt{n}\,)$

, whereas the length of any route is stretched by a factor of at most 7 w.r.t. the shortest path. At any step, the memory space of each node is

$\tilde{O}(\sqrt{n}\,)$

. The algorithm terminates in time

O

(

D

), where

D

is the hop-diameter of

G

. In synchronous scenarios and with uniform weights, it consumes

$\tilde{O}(m\sqrt{n} + n^{3/2}$

min

${D,\sqrt{n}\,})$

messages, where

m

is the number of edges of

G

.

In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is

$\tilde{O}(n^{3/2})$

, improves by a factor of

$\sqrt{n}$

the communication complexity of

any

shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.

We study the convergence of influence networks, where each node changes its state according to the majority of its neighbors. Our main result is a new Ω(

n

2

/log

2

n

) bound on the convergence time in the synchronous model, solving the classic “Democrats and Republicans” problem. Furthermore, we give a bound of Θ(

n

2

) for the sequential model in which the sequence of steps is given by an adversary and a bound of Θ(

n

) for the sequential model in which the sequence of steps is given by a benevolent process.

Population protocols have been introduced by Angluin

et al.

as a model in which passively mobile anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. Stably computable predicates under this model have been characterized as exactly semi-linear predicates, that is to say exactly those definable in Presburger’s arithmetic.

We consider several variants of the models. In all these variants, the agents are called

trustful

: agents with a similar opinion that meet do not change their common opinion. We provide a characterization of the computational power of the obtained models, considering both the case when agents have finitely many states, and when agents can possibly be arbitrary Turing machines. We also provide some time complexity considerations.

In a cognitive radio network, a Primary User (PU) may vacate a channel for intermissions of an unknown length. A substantial amount of research has been devoted to minimizing the disturbance a Secondary User (SU) may cause the PU. We take another step and optimize the throughput of an SU, even when assuming that the disturbance to the PU is indeed avoided using those other methods.

We suggest new optimization parameters the lengths of SU packets. That is, the SU fills up the intermission with consecutive packets. Each packet is associated with some fixed overhead. Hence, using a larger number of smaller packets increases the overhead ratio for each SU packet. On the other hand, it reduces the loss of throughput the SU suffers with the loss of a packet in a collision at the end of the intermission.

As opposed to previous studies, we optimize also the case where the distribution of the channel intermission is unknown. That is, we develop optimal competitive protocols. Those seek to minimize the ratio of the SU’s profit compared to a hypothetical optimal algorithm that knows the intermission length in advance. We show how to compute the optimal present packets’ sizes for the case that the distribution

is

known (for a

general

distribution). Finally, we show several interesting properties of the optimal solutions for several popular distributions.

When comparing new wireless technologies, it is common to consider the effect that they have on the capacity of the network (defined as the maximum number of simultaneously satisfiable links). For example, it has been shown that giving receivers the ability to do interference cancellation, or allowing transmitters to use power control, never decreases the capacity and can in certain cases increase it by

$\Omega(\log (\varDelta \cdot P_{\max}))$

, where

$\varDelta$

is the ratio of the longest link length to the smallest transmitter-receiver distance and

P

max

is the maximum transmission power. But there is no reason to expect the optimal capacity to be realized in practice, particularly since maximizing the capacity is known to be NP-hard. In reality, we would expect links to behave as self-interested agents, and thus when introducing a new technology it makes more sense to compare the values reached at game-theoretic equilibria than the optimum values.

In this paper we initiate this line of work by comparing various notions of equilibria (particularly Nash equilibria and no-regret behavior) when using a supposedly “better” technology. We show a version of Braess’s Paradox for all of them: in certain networks, upgrading technology can actually make the equilibria

worse

, despite an increase in the capacity. We construct instances where this decrease is a constant factor for power control, interference cancellation, and improvements in the SINR threshold (

β

), and is

$\Omega(\log \varDelta)$

when power control is combined with interference cancellation. However, we show that these examples are basically tight: the decrease is at most

O

(1) for power control, interference cancellation, and improved

β

, and is at most

$O(\log \varDelta)$

when power control is combined with interference cancellation.

We introduce collision free layerings as a powerful way to structure radio networks. These layerings can replace hard-to-compute BFS-trees in many contexts while having an efficient randomized distributed construction. We demonstrate their versatility by using them to provide near optimal distributed algorithms for several multi-message communication primitives.

Designing efficient communication primitives for radio networks has a rich history that began 25 years ago when Bar-Yehuda et al. introduced fast randomized algorithms for broadcasting and for constructing BFS-trees. Their BFS-tree construction time was

O

(

D

log

2

n

) rounds, where

D

is the network diameter and

n

is the number of nodes. Since then, the complexity of a broadcast has been resolved to be

$T_{BC} = \Theta(D \log \frac{n}{D} + \log^2 n)$

rounds. On the other hand, BFS-trees have been used as a crucial building block for many communication primitives and their construction time remained a bottleneck for these primitives.

We introduce collision free layerings that can be used in place of BFS-trees and we give a randomized construction of these layerings that runs in nearly broadcast time, that is, w.h.p. in

$T_{Lay} = O(D \log \frac{n}{D} + \log^{2+\epsilon} n)$

rounds for any constant

ε

 > 0. We then use these layerings to obtain: (1) A randomized algorithm for gathering

k

messages running w.h.p. in

O

(

T

Lay

 + 

k

) rounds. (2) A randomized

k

-message broadcast algorithm running w.h.p. in

O

(

T

Lay

 + 

k

log

n

) rounds. These algorithms are optimal up to the small difference in the additive poly-logarithmic term between

T

BC

and

T

Lay

. Moreover, they imply the first optimal

O

(

n

log

n

) round randomized gossip algorithm.

We address the problem of in-network analytics for data that is generated by sensors at the edge of the network. Specifically, we consider the problem of summarizing a continuous physical phenomenon, such as temperature or pollution, over a geographic region like a road network. Samples are collected by sensors placed alongside roads as well as in cars driving along them. We divide the region into sectors and find a summary for each sector, so that their union is a continuous function that minimizes some global error function. We designate a node (either virtual or physical) that is responsible for estimating the function in each sector. Each node computes its estimate based on the samples taken in its sector and information from adjacent nodes.

The algorithm works in networks with bounded, yet unknown, latencies. It accommodates the addition and removal of samples and the arrival and departure of nodes, and it converges to a globally optimal solution using only pairwise message exchanges between neighbors. The algorithm relies on a weakly-fair scheduler to implement these pairwise exchanges, and we present an implementation of such a scheduler. Our scheduler, which may be of independent interest, is

locally quiescent

, meaning that it only sends messages when required by the algorithm. It achieves quiescence on every link where the algorithm ceases to schedule pairwise exchanges; in particular, if the algorithm converges, it globally quiesces.

The

facility location

problem consists of a set of

facilities

$\mathcal{F}$

, a set of

clients

$\mathcal{C}$

, an

opening cost

f

i

associated with each facility

x

i

, and a

connection cost

D

(

x

i

,

y

j

) between each facility

x

i

and client

y

j

. The goal is to find a subset of facilities to

open

, and to connect each client to an open facility, so as to minimize the total facility opening costs plus connection costs. This paper presents the first expected-sub-logarithmic-round distributed

O

(1)-approximation algorithm in the

$\mathcal{CONGEST}$

model for the

metric

facility location problem on the complete bipartite network with parts

$\mathcal{F}$

and

$\mathcal{C}$

. Our algorithm has an expected running time of

O

((loglog

n

)

3

) rounds, where

$n = |\mathcal{F}| + |\mathcal{C}|$

. This result can be viewed as a continuation of our recent work (ICALP 2012) in which we presented the first sub-logarithmic-round distributed

O

(1)-approximation algorithm for metric facility location on a

clique

network. The bipartite setting presents several new challenges not present in the problem on a clique network. We present two new techniques to overcome these challenges.

We consider the problem of managing a dynamic heterogeneous storage system in a distributed way so that the amount of data assigned to a host in that system is related to its capacity. Two central problems have to be solved for this: (1) organizing the hosts in an overlay network with low degree and diameter so that one can efficiently check the correct distribution of the data and route between any two hosts, and (2) distributing the data among the hosts so that the distribution respects the capacities of the hosts and can easily be adapted as the set of hosts or their capacities change. We present distributed protocols for these problems that are self-stabilizing and that do not need any global knowledge about the system such as the number of nodes or the overall capacity of the system. Prior to this work no solution was known satisfying these properties.