Distributed Computing

We present the CBTree, a new

counting-based

self-adjusting binary search tree that, like

splay trees

, moves more frequently accessed nodes closer to the root. After

m

operations on

n

items,

c

of which access some item

v

, an operation on

v

traverses a path of length

$\mathcal{O}(\log\dfrac{m}{c})$

while performing few if any rotations. In contrast to the traditional self-adjusting splay tree in which each accessed item is moved to the root through a sequence of tree rotations, the CBTree performs rotations infrequently (an amortized subconstant

o

(1) per operation if

m

 ≫ 

n

), mostly at the bottom of the tree. As a result, the CBTree scales with the amount of concurrency. We adapt the CBTree to a multicore setting and show experimentally that it improves performance compared to existing concurrent search trees on non-uniform access sequences derived from real workloads.

A

Fetch&Inc

object stores a non-negative integer and supports a single operation,

fi

, that returns the value of the object and increments it. Such objects are used in many asynchronous shared memory algorithms, such as renaming, mutual exclusion, and barrier synchronization. We present an efficient implementation of a wait-free

Fetch&Inc

object from registers and load-linked/store-conditional (

ll/sc

) objects. In a system with

p

processes, every

fi

operation finishes in

O

(log

2

p

) steps, and only a polynomial number of registers and

O

(log

p

)-bit

ll/sc

objects are needed. The maximum number of

fi

operations that can be supported is limited only by the maximum integer that can be stored in a shared register. This is the first wait-free implementation of a

Fetch&Inc

object that achieves both poly-logarithmic step complexity and polynomial space complexity, but does not require unrealistically large

ll/sc

objects or registers.

Modern programming languages, such as C++ and Java, provide a sequentially consistent (SC) memory model for well-behaved programs that follow a certain synchronisation discipline, e.g., for those that are data-race free (DRF). However, performance-critical libraries often violate the discipline by using low-level hardware primitives, which have a weaker semantics. In such scenarios, it is important for these libraries to protect their otherwise well-behaved clients from the weaker memory model.

In this paper, we demonstrate that a variant of linearizability can be used to reason formally about the interoperability between a high-level DRF client and a low-level library written for the Total Store Order (TSO) memory model, which is implemented by x86 processors. Namely, we present a notion of linearizability that relates a concrete library implementation running on TSO to an abstract specification running on an SC machine. A client of this library is said to be DRF if its SC executions calling the abstract library specification do not contain data races. We then show how to compile a DRF client to TSO such that it only exhibits SC behaviours, despite calling into a racy library.

A set of identical, mobile agents is deployed in a weighted network. Each agent possesses a battery - a power source allowing the agent to move along network edges. Agents use their batteries proportionally to the distance traveled. At the beginning, each agent has its initial information. Agents exchange the actually possessed information when they meet. The agents collaborate in order to perform an efficient

convergecast

, where the initial information of all agents must be eventually transmitted to some agent.

The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast may be achieved. We study the question in the centralized and the distributed settings. In the distributed setting every agent has to perform an algorithm being unaware of the network. We give a linear-time centralized algorithm solving the problem for line networks. We give a 2-competitive distributed algorithm achieving convergecast for tree networks. The competitive ratio of 2 is proved to be the best possible for this problem, even if we only consider line networks. We show that already for the case of tree networks the centralized problem is strongly NP-complete. We give a 2-approximation centralized algorithm for general graphs.

Initial knowledge regarding group size can be crucial for collective performance. We study this relation in the context of the

Ants Nearby Treasure Search (ANTS)

problem [18], which models natural cooperative foraging behavior such as that performed by ants around their nest. In this problem,

k

(probabilistic) agents, initially placed at some central location, collectively search for a treasure on the two-dimensional grid. The treasure is placed at a target location by an adversary and the goal is to find it as fast as possible as a function of both

k

and

D

, where

D

is the (unknown) distance between the central location and the target. It is easy to see that

T

 = Ω(

D

 + 

D

2

/

k

) time units are necessary for finding the treasure. Recently, it has been established that

O

(

T

) time is sufficient if the agents know their total number

k

(or a constant approximation of it), and enough memory bits are available at their disposal [18]. In this paper, we establish lower bounds on the agent memory size required for achieving certain running time performances. To the best our knowledge, these bounds are the first non-trivial lower bounds for the memory size of probabilistic searchers. For example, for every given positive constant

ε

, terminating the search by time

O

(log

1 − 

ε

k

·

T

) requires agents to use Ω(loglog

k

) memory bits.

From a high level perspective, we illustrate how methods from distributed computing can be useful in generating lower bounds for cooperative biological ensembles. Indeed, if experiments that comply with our setting reveal that the ants’ search is time efficient, then our theoretical lower bounds can provide some insight on the memory they use for this task.

It is a challenging and fundamental problem to construct the underlying overlay network to support efficient and scalable information distribution in topic-based publish/subscribe systems. Existing overlay design algorithms aim to minimize the node fan-out while building topic-connected overlays, in which all nodes interested in the same topic are organized in a directly connected dissemination sub-overlay. However, most state-of-the-art algorithms suffer from high computational complexity, such as

O

(|

V

|

4

|

T

|), where

V

is the node set and

T

is the topic set.

We devise a general indexing data structure that provides a significantly faster implementation, with

O

(|

V

|

2

|

T

|) running time, for different state-of-the-art algorithms. The generality of the indexing data structure is due to the fact that it enables edge lookup by both node degree and

edge contribution

, a central metric in all existing algorithms. When tested on typical pub/sub workloads, the speedup observed was by a factor of over 1 000, thereby rendering the algorithms more suitable for practical use. For example, under a typically Zipf distributed pub/sub workload, with 1 000 nodes and 100 topics, our new implementation completes in 3.823 seconds, while the previous alternative takes over 555 minutes.

Efficient communication in wireless networks is typically challenged by the possibility of interference among several transmitting nodes. Much important research has been invested in decreasing the number of collisions in order to obtain faster algorithms for communication in such networks.

This paper proposes a novel approach for wireless communication, which embraces collisions rather than avoiding them, over an additive channel. It introduces a coding technique called

Bounded-Contention Coding (BCC)

that allows collisions to be successfully decoded by the receiving nodes into the original transmissions and whose complexity depends on a bound on the contention among the transmitters.

BCC enables

deterministic

local broadcast in a network with

n

nodes and at most

a

transmitters with information of ℓ bits each within

O

(

a

log

n

 + 

a

ℓ) bits of communication with full-duplex radios, and

O

((

a

log

n

 + 

a

ℓ)(log

n

)) bits, with high probability, with half-duplex radios. When combined with random linear network coding, BCC gives

global

broadcast within

O

((

D

 + 

a

 + log

n

)(

a

log

n

 + ℓ)) bits, with high probability. This also holds in dynamic networks that can change arbitrarily over time by a worst-case adversary. When no bound on the contention is given, it is shown how to probabilistically estimate it and obtain global broadcast that is adaptive to the true contention in the network.

The Signal-to-Interference-and-Noise-Ratio (SINR) physical model is one of the most popular models of wireless networks. Despite of the vast amount of study done in design and analysis of centralized algorithms supporting wireless communication under the SINR physical model, little is known about distributed algorithms in this model, especially deterministic ones. In this work we construct, in a deterministic distributed way, a backbone structure on the top of a given wireless network, which can be used for efficient transformation of many algorithms designed in a simpler model of ad hoc broadcast networks without interference into the SINR physical model with uniform power of stations. The time cost of the backbone data structure construction is only

$O(\Delta \text{ \!polylog\! } N)$

rounds, where Δ is roughly the network density and {1,…,

N

} is the range of identifiers (IDs) and thus

N

is an upper bound on the number of nodes in the whole network. The core of the construction is a novel combinatorial structure called SINR-selector, which is introduced in this paper. We demonstrate the power of the backbone data structure by using it for obtaining efficient

$O(D+\Delta \text{ \!polylog\! } N)$

round and

$O(D+k+\Delta \text{ \!polylog\! } N)$

round deterministic distributed solutions for leader election and multi-broadcast, respectively, where

D

is the network diameter and

k

is the number of messages to be disseminated.

We consider the problems of online and stochastic packet queuing in a distributed system of

n

nodes with queues, where the communication between the nodes is done via a multiple access channel. In each round, an arbitrary number of packets can be injected into the system, each to an arbitrary node’s queue. Two measures of performance are considered: the total number of packets in the system, called the total load, and the maximum queue size, called the maximum load. In the online setting, we develop a deterministic algorithm that is asymptotically optimal with respect to both complexity measures, in a competitive way. More precisely, the total load of our algorithm is bigger then the total load of any other algorithm, including centralized offline solutions, by only

O

(

n

2

), while the maximum queue size of our algorithm is at most

n

times bigger than the maximum queue size of any other algorithm, with an extra additive

O

(

n

). The optimality for both measures is justified by proving the corresponding lower bounds. Next, we show that our algorithm is stochastically optimal for

any

expected injection rate smaller or equal to 1. To the best of our knowledge, this is the first solution to the stochastic queuing problem on a multiple access channel that achieves such optimality for the (highest possible) rate equal to 1.

The paper investigates efficient distributed computation in

dynamic

networks in which the network topology changes (arbitrarily) from round to round. Random walks are a fundamental primitive in a wide variety of network applications; the local and lightweight nature of random walks is especially useful for providing uniform and efficient solutions to distributed control of dynamic networks. Given their applicability in dynamic networks, we focus on developing fast distributed algorithms for performing random walks in such networks.

Our first contribution is a rigorous framework for design and analysis of distributed random walk algorithms in dynamic networks. We then develop a fast distributed random walk based algorithm that runs in

$\tilde{O}(\sqrt{\tau \Phi})$

rounds (with high probability), where

τ

is the

dynamic mixing time

and Φ is the

dynamic diameter

of the network respectively, and returns a sample close to a suitably defined stationary distribution of the dynamic network.

Our next contribution is a fast distributed algorithm for the fundamental problem of information dissemination (also called as

gossip

) in a dynamic network. In gossip, or more generally,

k

-gossip, there are

k

pieces of information (or tokens) that are initially present in some nodes and the problem is to disseminate the

k

tokens to all nodes. We present a random-walk based algorithm that runs in

$\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3}, nk\})$

rounds (with high probability). To the best of our knowledge, this is the first

o

(

nk

)-time fully-distributed

token forwarding

algorithm that improves over the previous-best

O

(

nk

) round distributed algorithm [Kuhn et al., STOC 2010], although in an oblivious adversary model.

In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense substructures in otherwise sparse graphs (e.g. the World Wide Web or social networks); these might reveal community clusters or dense regions for possibly maintaining good communication infrastructure. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs that the member nodes are aware of. The only knowledge that the nodes need is that of the

dynamic diameter

D

, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that (2 + 

ε

)-approximate the

densest subgraph

and (3 + 

ε

)-approximate the

at-least-k-densest subgraph

(for a given parameter

k

). Our algorithms work for a wide range of parameter values and run in

O

(

D

log

1 + 

ε

n

) time. Further, a special case of our results also gives the first fully decentralized approximation algorithms for densest and at-least-

k

-densest subgraph problems for static distributed graphs.

We study lower bounds on information dissemination in adversarial dynamic networks. Initially,

k

pieces of information (henceforth called tokens) are distributed among

n

nodes. The tokens need to be broadcast to all nodes through a synchronous network in which the topology can change arbitrarily from round to round provided that some connectivity requirements are satisfied.

If the network is guaranteed to be connected in every round and each node can broadcast a single token per round to its neighbors, there is a simple token dissemination algorithm that manages to deliver all

k

tokens to all the nodes in

O

(

nk

) rounds. Interestingly, in a recent paper, Dutta et al. proved an almost matching Ω(

n

 + 

nk

/log

n

) lower bound for deterministic token-forwarding algorithms that are not allowed to combine, split, or change tokens in any way. In the present paper, we extend this bound in different ways.

If nodes are allowed to forward

b

 ≤ 

k

tokens instead of only one token in every round, a straight-forward extension of the

O

(

nk

) algorithm disseminates all

k

tokens in time

O

(

nk

/

b

). We show that for any randomized token-forwarding algorithm, Ω(

n

 + 

nk

/(

b

2

log

n

loglog

n

)) rounds are necessary. If nodes can only send a single token per round, but we are guaranteed that the network graph is

c

-vertex connected in every round, we show a lower bound of Ω(

nk

/(

c

log

3/2

n

)), which almost matches the currently best

O

(

nk

/

c

) upper bound. Further, if the network is

T

-interval connected, a notion that captures connection stability over time, we prove that Ω(

n

 + 

nk

/(

T

2

log

n

)) rounds are needed. The best known upper bound in this case manages to solve the problem in

O

(

n

 + 

nk

/

T

) rounds. Finally, we show that even if each node only needs to obtain a

δ

-fraction of all the tokens for some

δ

 ∈ [0,1], Ω(

nkδ

3

/log

n

) are still required.

König’s theorem states that on bipartite graphs the size of a maximum matching equals the size of a minimum vertex cover. It is known from prior work that for every

ε

 > 0 there exists a

constant-time

distributed algorithm that finds a (1 + 

ε

)-approximation of a maximum matching on 2-coloured graphs of bounded degree. In this work, we show—somewhat surprisingly—that no

sublogarithmic-time

approximation scheme exists for the dual problem: there is a constant

δ

 > 0 so that no randomised distributed algorithm with running time

o

(log

n

) can find a (1 + 

δ

)-approximation of a minimum vertex cover on 2-coloured graphs of maximum degree 3. In fact, a simple application of the Linial–Saks (1993) decomposition demonstrates that this lower bound is tight.

Our lower-bound construction is simple and, to some extent, independent of previous techniques. Along the way we prove that a certain cut minimisation problem, which might be of independent interest, is hard to approximate locally on expander graphs.

Let

G

 = (

V

,

E

) be an

n

-vertex graph and

M

d

a

d

-vertex graph, for some constant

d

. Is

M

d

a subgraph of

G

? We consider this problem in a model where all

n

processes are connected to all other processes, and each message contains up to

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

bits. A simple deterministic algorithm that requires

$\mathcal{O}(n^{(d-2)/d}/\log n)$

communication rounds is presented. For the special case that

M

d

is a triangle, we present a probabilistic algorithm that requires an expected

$\mathcal{O}(n^{1/3}/(t^ {2/3}+1))$

rounds of communication, where

t

is the number of triangles in the graph, and

$\mathcal{O}(\min\{n^{1/3}\log^{2/3}n/(t^ {2/3}+1),n^{1/3}\})$

with high probability.

We also present deterministic algorithms that are specially suited for sparse graphs. In graphs of maximum degree Δ, we can test for arbitrary subgraphs of diameter

D

in

$\mathcal{O}(\Delta^{D+1}/n)$

rounds. For triangles, we devise an algorithm featuring a round complexity of

$\mathcal{O}((A^2\log_{2+n/A^2} n)/n)$

, where

A

denotes the arboricity of

G

.

In this paper we consider the problem of matching clients with servers, each of which can process a subset of clients. It is known as the

semi-matching

or

load balancing

problem in a bipartite graph

G

 = (

V

,

U

,

E

), where

U

corresponds to the clients,

V

to the servers, and

E

is the set of available connections between them. The goal is to find a set of edges

M

 ⊆ 

E

such that every vertex in

U

is incident to exactly one edge in

M

. The

load

of a server

v

 ∈ 

V

is defined as

${d_M(v) +1\choose 2}$

where

d

M

(

v

) is the degree of

v

in

M

, and the problem is to find an optimal semi-matching, i.e. a semi-matching that minimizes the sum of the loads of the servers. An optimal solution can be found sequentially in polynomial time but the distributed complexity is not well understood. Our algorithm yields

$(1+\frac{1}{\alpha})$

-approximation (where

$\alpha=\max\left\{1, \frac 12\left(\frac{|U|}{|V|} +1\right)\right\}$

) and has time complexity

$O\left(\Delta^5\right),$

where Δ is the maximum degree of a vertex in

V

. In particular, for Δ = 

O

(1) it gives constant approximation with constant time complexity. We also give a fast algorithm for the case when Δ is large and the degrees in

V

and

U

satisfy some additional properties. Both algorithms are deterministic.

The local broadcast problem assumes that processes in a wireless network are provided messages, one by one, that must be delivered to their neighbors. In this paper, we prove tight bounds for this problem in two well-studied wireless network models: the

classical

model, in which links are reliable and collisions consistent, and the more recent

dual graph

model, which introduces unreliable edges. Our results prove that the

Decay

strategy, commonly used for local broadcast in the classical setting, is optimal. They also establish a separation between the two models, proving that the dual graph setting is strictly harder than the classical setting, with respect to this primitive.

We investigate the complexity of basic symmetry breaking problems in multihop radio networks with multiple communication channels. We assume a network of synchronous nodes, where each node can be awakened individually in an arbitrary time slot by an adversary. In each time slot, each awake node can transmit or listen (without collision detection) on one of multiple available shared channels. The network topology is assumed to satisfy a natural generalization of the well-known unit disk graph model.

We study the classic

wake-up

problem and a new variant we call

active wake-up

. For the former we prove a lower bound that shows the advantage of multiple channels disappears for any network of more than one hop. For the active version however, we describe an algorithm that outperforms any single channel solution. We then extend this algorithm to compute a constant approximation for the

minimum dominating set

(MDS) problem in the same time bound. Combined, these results for the increasingly relevant multi-channel model show that it is

often

possible to leverage channel diversity to beat classic lower bounds, but not always.

We consider the problem of reliably broadcasting information in a multihop asynchronous network that is subject to Byzantine failures. Most existing approaches give conditions for perfect reliable broadcast (all correct nodes deliver the authentic message and nothing else), but they require a highly connected network. An approach giving only probabilistic guarantees (correct nodes deliver the authentic message with high probability) was recently proposed for loosely connected networks, such as grids and tori. Yet, the proposed solution requires a specific initialization (that includes global knowledge) of each node, which may be difficult or impossible to guarantee in self-organizing networks – for instance, a wireless sensor network, especially if they are prone to Byzantine failures.

In this paper, we propose a new protocol offering guarantees for loosely connected networks that does not require such global knowledge dependent initialization. In more details, we give a methodology to determine whether a set of nodes will always deliver the authentic message, in any execution. Then, we give conditions for perfect reliable broadcast in a torus network. Finally, we provide experimental evaluation for our solution, and determine the number of randomly distributed Byzantine failures than can be tolerated, for a given correct broadcast probability.

Recent research on mutual exclusion for shared-memory systems has focused on

local spin

algorithms. Performance is measured using the

remote memory references

(RMRs) metric. As common in recent literature, we consider a standard asynchronous shared memory model with

N

processes, which allows atomic read, write and compare-and-swap (short: CAS) operations.

In such a model, the asymptotically tight upper and lower bounds on the number of RMRs per passage through the Critical Section is Θ(log

N

) for the optimal deterministic algorithms [6,22]. Recently, several

randomized

algorithms have been devised that break the Ω(log

N

) barrier and need only

o

(log

N

) RMRs per passage in expectation [7,13,14]. In this paper we present the first randomized

abortable

mutual exclusion algorithm that achieves a sub-logarithmic expected RMR complexity. More precisely, against a weak adversary (which can make scheduling decisions based on the entire past history, but not the latest coin-flips of each process) every process needs an expected number of

O

(log

N

/loglog

N

) RMRs to enter end exit the critical section. If a process receives an abort-signal, it can abort an attempt to enter the critical section within a finite number of its own steps and by incurring

O

(log

N

/loglog

N

) RMRs.

When a process attempts to acquire a mutex lock, it may be forced to wait if another process currently holds the lock. In certain applications, such as real-time operating systems and databases, indefinite waiting can cause a process to miss an important deadline [19]. Hence, there has been research on designing

abortable

mutual exclusion locks, and fairly efficient algorithms of

O

(log

n

) RMR complexity have been discovered [11,14] (

n

denotes the number of processes for which the algorithm is designed).

The abort feature is just as important for a reader-writer lock as it is for a mutual exclusion lock, but to the best of our knowledge there are currently no abortable reader-writer locks that are starvation-free. We show the surprising result that any abortable, starvation-free mutual exclusion algorithm of RMR complexity

t

(

n

) can be transformed into an abortable, starvation-free reader-writer exclusion algorithm of RMR complexity

O

(

t

(

n

)). Thus, we obtain the first abortable, starvation-free reader-writer exclusion algorithm of

O

(log

n

) RMR complexity. Our results apply to the Cache-Coherent (CC) model of multiprocessors.

Read-write locks are one of the most prevalent lock forms in concurrent applications because they allow read accesses to locked code to proceed in parallel. However, they do not offer any parallelism between reads and writes.

This paper introduces

pessimistic lock-elision

(PLE), a new approach for non-speculatively replacing read-write locks with pessimistic (i.e. non-aborting) software transactional code that allows read-write concurrency even for contended code and even if the code includes system calls. On systems with hardware transactional support, PLE will allow failed transactions, or ones that contain system calls, to preserve read-write concurrency.

Our PLE algorithm is based on a novel encounter-order design of a fully pessimistic STM system that in a variety of benchmarks spanning from counters to trees, even when up to 40% of calls are mutating the locked structure, provides up to 5 times the performance of a state-of-the-art read-write lock.

We present an oblivious pattern formation algorithm for anonymous mobile robots in the asynchronous model. The robots obeying the algorithm, starting from any initial configuration

I

, always form a given pattern

F

, if

I

and

F

do not contain multiplicities and

ρ

(

I

) divides

ρ

(

F

), where

ρ

(·) denotes the geometric symmetricity. Our algorithm substantially outdoes an algorithm by Dieudonné et al. proposed in DISC 2010, which is dedicated to

ρ

(

I

) = 1. Our algorithm is best possible (as long as

I

and

F

do not contain multiplicities), since there is no algorithm that always forms

F

from

I

when

ρ

(

F

) is not divisible by

ρ

(

I

).

All known pattern formation algorithms are constructed from scratch. We instead use a bipartite matching algorithm (between the robots and the points in

F

) we proposed in OPODIS 2011 as a core subroutine, to make the description of algorithm concise and easy to understand.

A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and remain in there. This problem is known in the literature as the

gathering

. Anonymous and oblivious robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move). Cycles are asynchronous among robots. Moreover, each robot is empowered by the so called

multiplicity detection

capability, that is, it is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one.

The described problem has been extensively studied during the last years. However, the known solutions work only for specific initial configurations and leave some open cases. In this paper, we provide an algorithm which solves the general problem, and is able to detect all the ungatherable configurations. It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration, even those left open by previous works.

A collection of

n

anonymous mobile robots is deployed on a unit-perimeter ring or a unit-length line segment. Every robot starts moving at constant speed, and bounces each time it meets any other robot or segment endpoint, changing its walk direction. We study the problem of

position discovery

, in which the task of each robot is to detect the presence and the initial positions of all other robots. The robots cannot communicate or perceive information about the environment in any way other than by bouncing. Each robot has a clock allowing it to observe the times of its bounces. The robots have no control on their walks, which are determined by their initial positions and the starting directions. Each robot executes the same

position detection algorithm

, which receives input data in real-time about the times of the bounces, and terminates when the robot is assured about the existence and the positions of all the robots.

Some initial configuration of robots are shown to be

infeasible

— no position detection algorithm exists for them. We give complete characterizations of all infeasible initial configurations for both the ring and the segment, and we design optimal position detection algorithms for all feasible configurations. For the case of the ring, we show that all robot configurations in which not all the robots have the same initial direction are feasible. We give a position detection algorithm working for all feasible configurations. The cost of our algorithm depends on the number of robots starting their movement in each direction. If the less frequently used initial direction is given to

k

 ≤ 

n

/2 robots, the time until completion of the algorithm by the last robot is

$\frac{1}{2}\lceil \frac{n}{k} \rceil$

. We prove that this time is optimal. By contrast to the case of the ring, for the unit segment we show that the family of infeasible configurations is exactly the set of so-called

symmetric configurations

. We give a position detection algorithm which works for all feasible configurations on the segment in time 2, and this algorithm is also proven to be optimal.

Renaming and set agreement are two fundamental sub-consensus tasks. In the

M-renaming

task, processes start with names from a large domain and must decide on distinct names in a range of size

M

; in the

k-set agreement

task, processes must decide on at most

k

of their input values. Renaming and set agreement are representatives of the classes of

colored

and

colorless

tasks, respectively.

This paper presents simple proofs for key impossibility results for wait-free computation using only read and write operations:

n

processes cannot solve (

n

 − 1)-set agreement, and, if

n

is a prime power,

n

processes cannot solve (2

n

 − 2)-renaming.

Our proofs consider a restricted set of executions, and combine simple operational properties of these executions with elementary counting arguments, to show the existence of an execution violating the task’s requirements. This makes the proofs easier to understand, verify, and hopefully, extend.

The paper tackles the power of randomization in the context of locality by analyzing the ability to “boost” the success probability of deciding a distributed language. The main outcome of this analysis is that the distributed computing setting contrasts significantly with the sequential one as far as randomization is concerned. Indeed, we prove that in some cases, the ability to increase the success probability for deciding distributed languages is rather limited.

We focus on the notion of a (

p

,

q

)

-decider

for a language

$\mathcal{L}$

, which is a distributed randomized algorithm that

accepts

instances in

$\mathcal{L}$

with probability at least

p

and

rejects

instances outside of

$\mathcal{L}$

with probability at least

q

. It is known that every hereditary language that can be decided in

t

rounds by a (

p

,

q

)-decider, where

p

2

 + 

q

 > 1, can be decided

deterministically

in

O

(

t

) rounds. One of our results gives evidence supporting the conjecture that the above statement holds for all distributed languages and not only for hereditary ones, by proving the conjecture for the restricted case of path topologies.

For the range below the aforementioned threshold, namely,

p

2

 + 

q

 ≤ 1, we study the class

B

k

(

t

) (for

k

 ∈ ℕ

*

 ∪ { ∞ }) of all languages decidable in at most

t

rounds by a (

p

,

q

)-decider, where

$p^{1+\frac{1}{k}}+q>1$

. Since every language is decidable (in zero rounds) by a (

p

,

q

)-decider satisfying

p

 + 

q

 = 1, the hierarchy

B

k

provides a spectrum of complexity classes between determinism (

k

 = 1, under the above conjecture) and complete randomization (

k

 = ∞). We prove that all these classes are separated, in a strong sense: for every integer

k

 ≥ 1, there exists a language

$\mathcal{L}$

satisfying

$\mathcal{L}\in B_{k+1}(0)$

but

$\mathcal{L}\notin B_k(t)$

for any

t

 = 

o

(

n

). In addition, we show that

B

 ∞ 

(

t

) does not contain all languages, for any

t

 = 

o

(

n

). In other words, we obtain the hierarchy

B

1

(

t

) ⊂ 

B

2

(

t

) ⊂ ⋯ ⊂ 

B

 ∞ 

(

t

) ⊂ All.

Finally, we show that if the inputs can be restricted in certain ways, then the ability to boost the success probability becomes almost null, and in particular, derandomization is not possible even beyond the threshold

p

2

 + 

q

 = 1.

The at-most-once problem in shared memory asks for the completion of a number of tasks by a set of independent processors while adhering to “at most once” semantics. At-most-once algorithms are evaluated in terms of

effectiveness

, which is a measure that expresses the total number of tasks completed at-most-once in the worst case. Motivated by the lack of deterministic solutions with high effectiveness, we study the feasibility of (a close variant of) this problem. The

strong at most once

problem is solved by an at-most-one algorithm when all tasks are performed if no participating processes crash during the execution of the algorithm. We prove that the strong at-most-once problem has consensus number 2. This explains, via impossibility, the lack of wait-free deterministic solutions with high effectiveness for the at most once problem using only read/write atomic registers. We then present the first

k

-adaptive effectiveness optimal randomized solution for the strong at-most-once problem, that has optimal expected work for a non-trivial number of participating processes. Our solution also provides the first

k

-adaptive randomized solution for the Write-All problem, a dual problem to at-most-once.

Robot Systems.

This paper considers distributed systems of autonomous robots that can move freely on the two-dimensional Euclidean space, have visibility sensors (to see other robots, obstacles etc.) and can perform computations. One of the fundamental problems in distributed coordination of robots is to gather the robots at a single location. The gathering problem has been studied under various models with the objective of determining the minimal set of assumptions that still allows the robots to gather successfully within a finite time. For example, it is known that gathering can be solved even if the robots are

anonymous

(indistinguishable from each-other),

oblivious

(no persistent memory of the past), and cannot communicate explicitly with each other (except for indirect signaling using movement). Further, the robots may not share a common sense of direction. Robots operate in

cycles

that comprise

look, compute

, and

move

phases. The look phase consists in taking a snapshot of the other robots positions. In the compute phase, a robot computes a target destination, based on the previous observation, using a deterministic algorithm and in the move phase, the robot moves toward the computed destination (although the move may end before reaching the target destination). We consider the semi-synchronous ATOM model [4], where each cycle is considered to be atomic but only a subset of the robots may be active in each cycle. The robots are modeled as points on the Euclidean plane and the objective is to gather all robots at a single point.

We tackle a version of the well known

graph searching

problem where a team of robots aims at capturing an intruder in a graph. The robots and the intruder move between the graph nodes. The intruder is invisible, arbitrary fast, and omniscient. It is caught whenever it stands on a node occupied by a robot, and cannot escape to a neighboring node. We study graph searching in the CORDA model of mobile computing: robots are asynchronous and perform cycles of

Look-Compute-Move

actions. Moreover, motivated by physical constraints and similarly to some previous works, we assume the

exclusivity

property, stating that no two or more robots can occupy the same node at the same time. In addition, we assume that the network and the robots are anonymous. Finally, robots are

oblivious

, i.e., each robot performs its move actions based only on its current “vision” of the positions of the other robots. Our objective is to characterize, for a graph

G

, a set of integers such that for every integer

k

in the set,

perpetual

graph searching can be achieved by a team of

k

robots starting from

any

k

distinct nodes in

G

. One of our main results is a full characterization of this set, for any asymmetric tree. Towards providing a characterization for all trees, including trees with non-trivial automorphisms, we have also provided a set of positive and negative results, including a full characterization for any line. All our positive results are based on the design of graph searching algorithms.

We consider the problem of approximate consensus in mobile ad hoc networks in the presence of Byzantine nodes. Due to nodes’ mobility, the topology is dynamic and unpredictable. We propose an approximate Byzantine consensus protocol which is based on the linear iteration method. In this protocol, nodes are allowed to collect information during several consecutive rounds: thus moving gives them the opportunity to gather progressively enough values. A novel sufficient and necessary condition guarantees the final convergence of the consensus protocol. At each stage of the computation, a single correct node is concerned by the requirement expressed by this new condition.

We develop distributed algorithms for the maximum independent link set problem in wireless networks in a distributed computing model based on the physical interference model with SINR constraints — this is more realistic and more challenging than the traditional graph-based models. Our results give the first distributed algorithm for this problem with polylogarithmic running time with a constant factor approximation guarantee, matching the sequential bound.

We study the

minimum spanning tree

(

MST

) construction problem in wireless networks under the physical interference model based on SINR constraints. We develop the first distributed (randomized)

O

(

μ

)-approximation algorithm for

MST

, with the running time of

O

(

D

log

n

) (with high probability) where

D

denotes the diameter of the disk graph obtained by using the maximum possible transmission range, and

$\mu=\log{\frac{d_{max}}{d_{min}}}$

denotes the “distance diversity” w.r.t. the largest and smallest distances between two nodes. (When

$\frac{d_{max}}{d_{min}}$

is

n

-polynomial,

μ

 = 

O

(log

n

).)

The

beeping channel

model is a multiple access channel (MAC) model where active nodes can only send/hear a “jamming” signal (i.e. a beep) through the communication channel in each time slot [2]. A listening node hears a beep signal if at least one node is beeping; otherwise it hears nothing. The beeping model was recently proposed to model carrier-sensing-based wireless communication [2], and the Delta-Notch signalling mechanism between biological cells [1]. The motivation of our work, however, is to design efficient digital circuits. It turns out that the beeping channel model well characterizes the behaviors of a group of

sequential logic

modules connected by a logical-OR gate. A strictly synchronized global clock is available in such a circuit. In a clock cycle, a high electrical level in each input wire of the OR gate corresponds to the choice to beep made by the module connecting to this input wire while a low level corresponds to the choice not to beep. The output of the OR gate is wired back to each module as the source signal in the next cycle. We focus on deterministic protocols, which is preferred in hardware design and other applications requiring safety guarantee.

Motivation.

Roughly speaking, a weakly stabilizing system

$\cal S$

executed under a probabilistic scheduler

ρ

is probabilistically self-stabilizing, in the sense that any execution eventually reaches a legitimate execution with probability 1 [1-3]. Here

ρ

is a set of Markov chains, one of which is selected for

$\cal S$

by an

adversary

to generate as its evolution an infinite activation sequence to execute

$\cal S$

. The performance measure is the worst case expected convergence time

$\tau_{{\cal S},M}$

when

$\cal S$

is executed under a Markov chain

M

 ∈ 

ρ

. Let

$\tau_{{\cal S},\rho} = \sup_{M \in \rho} \tau_{{\cal S},M}$

. Then

$\cal S$

can be “comfortably” used as a probabilistically self-stabilizing system under

ρ

only if

$\tau_{{\cal S},\rho} < \infty$

. There are

$\cal S$

and

ρ

such that

$\tau_{{\cal S},\rho} = \infty$

, despite that

$\tau_{{\cal S},M} < \infty$

for any

M

 ∈ 

ρ

. Somewhat interesting is that, for some

$\cal S$

, there is a randomised version

${\cal S}^*$

of

$\cal S$

such that

$\tau_{{\cal S}^*,\rho} < \infty$

, despite that

$\tau_{{\cal S},\rho} = \infty$

, i.e., randomization helps. This motivates a characterization of

$\cal S$

that satisfies

$\tau_{{\cal S}^*,\rho} < \infty$

.

Distributed hierarchical directories are data structures that enable one to access shared objects whenever needed. These directories are used to implement fundamental coordination problems in distributed systems, including distributed transactional memory [4,5], distributed queues [2], and mobile object tracking [1]. These directories support access to the shared objects in a network through three basic operations: (i)

publish

, allowing a shared object to be inserted in the directory so that other nodes can find it; (ii) lookup, providing a read-only copy of the object to the requesting node; and (iii)

move

, allowing the requesting node to write the object locally after getting it.

1. Introduction.

The simplest communication mechanism that implements the broadcast operation is the

flooding

protocol, according to which the source node is initially informed, and, when a not informed node has an informed neighbor, then it becomes informed at the next time step. In this paper we study the flooding

completion time

in the case of dynamic graphs with arbitrary degree sequence, which are a special case of random evolving graphs. A

random evolving graph

is a sequence of graphs (

G

t

)

t

 ≥ 0

with the same set of nodes, in which, at each time step

t

, the graph

G

t

is chosen randomly according to a probability distribution over a specified family of graphs. A special case of random evolving graph is the

edge-Markovian

model (see the definition below), for which tight upper bounds on the flooding completion time have been obtained by using a so-called

reduction lemma

, which intuitively shows that the flooding completion time of an edge-Markovian evolving graph is equal to the diameter of a suitably defined weighted random graph. In this paper, we show that this technique can be applied to the analysis of the flooding completion time in the case of a random evolving graph based on the following generative model. Given a sequence

w

 = 

w

1

, …,

w

n

of non-negative numbers, the graph

G

w

is a random graph with

n

nodes in which each edge (

i

,

j

) exists with probability

$p_{i,j}=\frac{w_iw_j}{\sum_{k=1}^nw_k}$

(independently of the other edges). It is easy to see that the expected degree of node

i

is

w

i

: hence, if we choose

w

to be a sequence satisfying a power law, then

G

w

is a power-law graph, while if we choose

w

i

 = 

pn

, then

G

w

is the

G

n

,

p

Erdös-Rényi random graph.

We propose distributed algorithms for sampling networks based on a new class of random walks that we call

Centrifugal Random Walks

(CRW). A CRW is a random walk that starts at a source and

always

moves

away

from it. We propose CRW algorithms for connected networks with arbitrary probability distributions, and for grids and networks with regular concentric connectivity with distance based distributions. All CRW sampling algorithms select a node with the exact probability distribution, do not need warm-up, and end in a number of hops bounded by the network diameter.

Motivation:

With the prevalence of multi-core multi-processor systems, concurrent data structures are becoming increasingly important. Concurrency is most often managed through locks. However, lock-based implementations of concurrent data structures are vulnerable to problems such as deadlock, priority inversion and convoying. Non-blocking algorithms avoid the pitfalls of locks by using hardware-supported read-modify-write instructions such as load-linked/storeconditional (LL/SC) and compare-and-swap (CAS). In this announcement, we focus on a non-blocking concurrent red-black tree. Red-black tree is a type of selfbalancing binary search tree that provides good worst-case time complexity for search and modify (insert, update and delete) operations. However, red-black trees have been remarkably resistant to parallelization using both lock-based and lock-free techniques. The tree structure causes the root and high level nodes to become the subject of high contention and thus become a bottleneck. This problem is only exacerbated by the introduction of balancing requirements. We present a suite of

wait-free

algorithms for concurrently accessing an external red-black tree, obtained through a progressive sequence of modifications to an existing general framework. In all our algorithms, search operations only execute read and write instructions on shared memory.

A skip list is a probabilistic data structure to store and retrieve in-memory data in an efficient way. In short, it is a linked structure that diminishes the linear big-oh complexity of a linked list with elements having additional shortcuts pointing towards other elements located further in the list [7]. These shortcuts allow operations to complete in

O

(log

n

) steps in expectation. The drawback of employing shortcuts is however to require additional maintenance each time some data is stored or discarded.

Passive replication is a popular practical approach to fault tolerance [1]. Using the Paxos consensus protocol [4] to implement it is seeing a growing popularity lately, but requires taking care of peculiar constraints. State updates must be applied using the same sequence of generation: if a primary is in state

A

and executes an operation making it transition to state

B

, the resulting state update

δ

AB

must be applied to the state

A

. Applying it to a different state

C

 ≠ 

A

is not safe because it might lead to an incorrect state, which is inconsistent with the history observed by replicas and clients. Paxos does not necessarily preserve the dependency between A and the delivery of

δ

AB

, as observed in [3].

The paper determines the weakest failure detector for consensus in asynchronous, crash prone and anonymous message passing systems.

This paper initiates the study of adversarial topology inference with virtual network (VNet) embeddings in ISP networks. As an example, we sketch how to infer cactus graphs with VNet request complexity

O

(

n

).

We consider a distributed computation setting in which a party, whom we refer to as

the dealer

, has a finite state automaton (FSA)

$\mathcal{A}$

with

m

states,which accepts an (

a priori

unbounded) stream of inputs

x

1

,

x

2

,... received from an external source. The dealer delegates the computation to agents

A

1

,...,

A

n

, by furnishing them with an implementation of

$\mathcal{A}$

. The input stream

x

1

,

x

2

,... is delivered to all agents in a synchronized manner during the online input-processing phase. Finally, given a signal from the dealer, the agents terminate the execution, submit their internal state to the dealer, who computes the state of

$\mathcal{A}$

and returns it as output.

Introduction.

In the area of data integration and middleware, distributed data processing systems create directed workflows to perform data cleansing, consolidation and calculations before emitting results to targets such as data warehouses. To provide fault tolerance, expensive system-wide checkpoints of distributed workflows want to be performed on the level of seconds while commits to transactional target resources must happen much more frequently to satisfy near real-time result latency [1] and small transaction size requirements. When there exists non-determinism in the workflow, the commit against a transactional target is allowed to be issued only when the determinants were saved to stable storage and deterministic replay can assure exactly-once result delivery. That is, there exists a

dependency

: the process

q

(a.k.a. operator or component in the context of data integration) executing the transaction is not allowed to make forward progress unless it has received the notification of the non-deterministic process

p

stating that the results to be committed can be replayed deterministically in the event of a crash.

The design of efficient search structures for peer-to-peer systems has attracted a lot of attention in recent years. In this announcement we address the problem of finding the predecessor in a key set and present an efficient data structure called hashed Predecessor Patricia trie. Our hashed Predecessor Patricia trie supports

PredecessorSearch(x)

and

Insert(x)

in

$\mathcal O(\log \log u)$

and

Delete(x)

in

$\mathcal O(1)$

hash table accesses when

u

is the size of the universe of the keys. That is the costs only depend on

u

and not the size of the data structure. One feature of our approach is that it only uses the lookup interface of the hash table and therefore hash table accesses may be realized by any distributed hash table (DHT).

Contribution.

We study the fundamental naming and counting problems in networks that are anonymous, unknown, and possibly dynamic. Network dynamicity is modeled by the 1-interval connectivity model [KLO10]. We first prove that on static networks with broadcast counting is impossible to solve without a leader and that naming is impossible to solve even with a leader and even if nodes know

n

. These impossibilities carry over to dynamic networks as well. With a leader we solve counting in linear time. Then we focus on dynamic networks with broadcast. We show that if nodes know an upper bound on the maximum degree that will ever appear then they can obtain an upper bound on

n

. Finally, we replace broadcast with

one-to-each

, in which a node may send a different message to each of its neighbors. This variation is then proved to be computationally equivalent to a full-knowledge model with unique names.

This paper initiates the study of self-adjusting distributed data structures or networks. In particular, we present

SplayNets

: a binary search tree based network that is self-adjusting to the routing requests. We derive entropy bounds on the amortized routing cost and show that our splaying algorithm has some interesting properties.

This paper studies the semantics of sets under eventual consistency. The set is a pervasive data type, used either directly or as a component of more complex data types, such as maps or graphs. Eventual consistency of replicated data supports concurrent updates, reduces latency and improves fault tolerance, but forgoes strong consistency (e.g., linearisability). Accordingly, several cloud computing platforms implement eventually-consistent replicated sets [2,4].

Quorum systems are constructions used to ensure consistency and availability of data stored in replicated servers. These systems usually comprise a static set of servers that provide a fault-tolerant read/write (r/w) register accessed by a set of clients. This approach is not adequate for long lived systems since, given a sufficient amount of time, there might be more faulty servers than the threshold tolerated, affecting the system correctness. Moreover, this approach does not allow a system administrator to deploy new machines or replace old ones at runtime and cannot be applied in many systems where, by their very nature, the set of processes that compose the system changes during its execution.

We propose

consistent quorums

to achieve linearizability in scalable and self-organizing key-value stores based on consistent hashing.

In

implicit multicast

, receiving processes delineate the messages they wish to receive by specifying predicates, also called

filters

, on the message’s content. In

weighted partial

message matching, distributed applications using implicit multicast protocols do not require that a message match all the elementary constraints constituting the filter. Typically, receiving processes in such applications associate a non-negative weight to each constraint and require that the

match score

, i.e., sum of the weights of matching constraints, exceeds a threshold value. In this paper, we consider top-

k

weighted partial matching, where a process is interested in multicasting a message only to

k

 < 

n

other processes corresponding to the top-

k

match scores. This is a fundamental problem underlying online advertising platforms, mobile social networks, online dating, etc.