Distributed Computing

The state machine approach is a well-known technique for building distributed services requiring high performance and high availability, by replicating servers, and by coordinating client interactions with server replicas using consensus. Indulgent consensus algorithms exist for realistic eventually partially synchronous models, that never violate safety and guarantee liveness once the system becomes synchronous. Unavoidably, these algorithms may never terminate, even when no processor crashes, if the system never becomes synchronous.

This paper proposes a mechanism similar to state machine replication, called

RC-simulation

, that can always make progress, even if the system is never synchronous. Using RC-simulation, the quality of the service will adjust to the current level of asynchrony of the network — degrading when the system is very asynchronous, and improving when the system becomes more synchronous. RC-simulation generalizes the state machine approach in the following sense: when the system is asynchronous, the system behaves as if

k

 + 1 threads were running concurrently, where

k

is a function of the asynchrony.

In order to illustrate how the RC-simulation can be used, we describe a long-lived renaming implementation. By reducing the concurrency down to the asynchrony of the system, RC-simulation enables to obtain renaming quality that adapts linearly to the asynchrony.

Chemical reaction networks (CRNs) formally model chemistry in a well-mixed solution. Assuming a fixed molecular population size and bimolecular reactions, CRNs are formally equivalent to population protocols, a model of distributed computing introduced by Angluin, Aspnes, Diamadi, Fischer, and Peralta (PODC 2004). The challenge of fast computation by CRNs (or population protocols) is to ensure that there is never a bottleneck “slow” reaction that requires two molecules (agent states) to react (communicate), both of which are present in low (

O

(1)) counts. It is known that CRNs can be fast in expectation by avoiding slow reactions with high probability. However, states may be reachable (with low probability) from which the correct answer may only be computed by executing a slow reaction. We deem such an event a

speed fault

. We show that the problems decidable by CRNs guaranteed to avoid speed faults are precisely the

detection problems

: Boolean combinations of questions of the form “is a certain species present or not?”. This implies, for instance, that no speed fault free CRN could decide whether there are at least two molecules of a certain species, although a CRN could decide this in “fast” expected time – i.e. speed fault free CRNs “can’t count.”

In this paper, we study a variant of the

Ants Nearby Treasure Search

problem, where

n

mobile agents, controlled by finite automata, search collaboratively for a treasure hidden by an adversary. In our version of the model, the agents may fail at any time during the execution. We provide a distributed protocol that enables the agents to detect failures and recover from them, thereby providing robustness to the protocol. More precisely, we provide a protocol that allows the agents to locate the treasure in time

$\mathcal{O}(D + D^2/n + Df)$

where

D

is the distance to the treasure and

$f \in \mathcal{O}(n)$

is the maximum number of failures.

In this paper we propose a mathematical model for studying the phenomenon of division of labor in ant colonies. Inside this model we investigate how simple task allocation mechanisms can be used to achieve an optimal division of labor.

We believe the proposed model captures the essential biological features of division of labor in ant colonies and is general enough to study a variety of different task allocation mechanisms. Within this model we propose a distributed randomized algorithm for task allocation that imposes only minimal requirements on the ants; it uses a constant amount of memory and relies solely on a primitive binary feedback function to sense the current labor allocation. We show that with high probability the proposed algorithm converges to a near-optimal division of labor in time which is proportional to the logarithm of the colony size.

We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary.

We describe a new randomized consensus protocol with expected message complexity

O

(

n

2

log

2

n

) when fewer than

n

/2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(

n

2

) message lower bound. The protocol further ensures that no process sends more than

O

(

n

log

3

n

) messages in expectation, which is again within logarithmic factors of optimal.We also present a generalization of the algorithm to an arbitrary number of failures

t

, which uses expected

O

(

nt

 + 

t

2

log

2

t

) total messages. Our protocol uses messages of size

O

(log

n

), and can therefore scale to large networks.

Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.

This paper investigates the problem of Byzantine Agreement in a synchronous system where malicious agents can move from process to process, corrupting their host. Earlier works on the problem are based on biased models which, as we argue in the paper, give an unfair advantage either to the correct processes or to the adversary controlling the malicious agents. Indeed, the earlier studies of the problem assume that, after a malicious agent has left a process, that process, said to be cured, is able to instantly and accurately detect the fact that it was corrupted in earlier rounds, and thus can take local actions to recover a valid state (Garay’s model). We found no justification for that assumption which clearly favors correct processes. Under that model, an algorithm is known for

n

 > 4

t

, where

n

is the number of processes and

t

the maximum number of malicious agents. The tightness of the bound is unknown. In contrast, more recent work on the problem remove the assumption on detection and assume instead that a malicious agent may have left corrupted messages in the send queue of a cured process. As a result, the adversary controlling the malicious agents can corrupt the messages sent by cured processes, as well as those sent by the newly corrupted ones, thus doubling the number of effective faults. Under that model, which favors the malicious agents, the problem can be solved if and only if

n

 > 6

t

. In this paper, we refine the latter model to avoid the above biases. While a cured process may send messages (based on a state corrupted by the malicious agent), it will behave correctly in the way it sends those messages: i.e., send messages according to the algorithm. Surprisingly, in this model we could derive a new non-trivial tight bound for Byzantine Agreement. We prove that at least 5

t

 + 1 processors are needed in order to tolerate

t

mobile Byzantine agents and provide a time optimal algorithm that matches this lower bound, altogether with a formal specification of the problem.

The

unbeatability

of a consensus protocol, introduced by Halpern, Moses and Waarts in [15], is a stronger notion of optimality than the accepted notion of early stopping protocols. Using a novel knowledge-based analysis, this paper derives the first practical unbeatable consensus protocols in the literature, for the standard synchronous message-passing model with crash failures. These protocols strictly dominate the best known protocols for uniform and for non-uniform consensus, in some case beating them by a large margin. The analysis provides a new understanding of the logical structure of consensus, and of the distinction between uniform and nonuniform consensus. Finally, the first (early stopping and) unbeatable protocol that treats decision values “fairly” is presented. All of these protocols have very concise descriptions, and are shown to be efficiently implementable.

We study the Reliable Broadcast problem in incomplete networks against a Byzantine adversary. We examine the problem under the

locally bounded adversary model

of Koo (2004) and the

general adversary model

of Hirt and Maurer (1997) and explore the tradeoff between the level of topology knowledge and the solvability of the problem.

We refine the local pair-cut technique of Pelc and Peleg (2005) in order to obtain impossibility results for every level of topology knowledge and any type of corruption distribution. On the positive side we devise protocols that match the obtained bounds and thus, exactly characterize the classes of graphs in which Reliable Broadcast is possible.

Among others, we show that Koo’s Certified Propagation Algorithm (CPA) is

unique

against locally bounded adversaries in

ad hoc

networks, that is, it can tolerate as many local corruptions as any other non-faulty algorithm; this settles an open question posed by Pelc and Peleg. We also provide an adaptation of CPA against general adversaries and show its uniqueness. To the best of our knowledge this is the first optimal algorithm for Reliable Broadcast in generic topology

ad hoc

networks against general adversaries.

Consider

k

mobile robots inside a circular disk of unit radius. The robots are required to evacuate the disk through an unknown exit point situated on its boundary. We assume all robots having the same (unit) maximal speed and starting at the centre of the disk. The robots may communicate in order to inform themselves about the presence (and its position) or the absence of an exit. The goal is for all the robots to evacuate through the exit in minimum time.

We consider two models of communication between the robots: in

non-wireless

(or

local

)

communication

model robots exchange information only when simultaneously located at the same point, and

wireless communication

in which robots can communicate one another at any time.

We study the following question for different values of

k

: what is the optimal evacuation time for

k

robots? We provide algorithms and show lower bounds in both communication models for

k

 = 2 and

k

 = 3 thus indicating a difference in evacuation time between the two models. We also obtain almost-tight bounds on the asymptotic relation between evacuation time and team size, for large

k

. We show that in the local communication model, a team of

k

robots can always evacuate in time

$3 + \frac{2\pi}{k}$

, whereas at least

$3 + \frac{2\pi}{k} - O(k^{-2})$

time is sometimes required. In the wireless communication model, time

$3 + \frac{\pi}{k} + O(k^{-4/3})$

always suffices to complete evacuation, and at least

$3+ \frac{\pi}{k}$

is sometimes required. This shows a clear separation between the local and the wireless communication models.

We present a randomized pattern formation algorithm for asynchronous oblivious (i.e., memory-less) mobile robots that enables formation of any target pattern. As for deterministic pattern formation algorithms, the class of patterns formable from an initial configuration

I

is characterized by the symmetricity (i.e., the order of rotational symmetry) of

I

, and in particular, every pattern is formable from

I

if its symmetricity is 1. The randomized pattern formation algorithm

ψ

PF

we present in this paper consists of two phases: The first phase transforms a given initial configuration

I

into a configuration

I

′ such that its symmetricity is 1, and the second phase invokes a deterministic pattern formation algorithm

ψ

CWM

by Fujinaga et al. (DISC 2012) for asynchronous oblivious mobile robots to finally form the target pattern.

There are two hurdles to overcome to realize

ψ

PF

. First, all robots must simultaneously stop and agree on the end of the first phase, to safely start the second phase, since the correctness of

ψ

CWM

is guaranteed only for an initial configuration in which all robots are stationary. Second, the sets of configurations in the two phases must be disjoint, so that even oblivious robots can recognize which phase they are working on. We provide a set of tricks to overcome these hurdles.

To improve performance and meet power constraints, vendors are introducing heterogeneous multicores that combine high performance and low power cores. However, choosing which cores and scheduling applications on them remain open problems. This paper presents a scheduling algorithmthat provably minimizes energy on heterogeneousmulticores and meets latency constraints for interactive applications, such as search, recommendations, advertisements, and games. Because interactive applications must respond quickly to satisfy users, they impose multiple constraints, including average, tail,

and

maximumlatency.We introduce SEM (Slow-to-fast, Energy optimization for Multiple constraints), which minimizes energy by choosing core speeds and how long to execute jobs on each core. We prove SEM minimizes energy without

a priori

knowledge of job service demand, satisfies multiple latency constraints simultaneously, and only migrates jobs from slower to faster cores. We address practical concerns of migration overhead and congestion. We prove optimizing energy for

average

latency requires homogeneous cores,whereas optimizing energy for tail and

deadline

constraints requires heterogeneous cores. For interactive applications,we create a formal foundation for scheduling and selecting cores in heterogeneous systems.

A

fault-tolerant

structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. In this paper, we address the problem of designing a

fault-tolerant

additive spanner, namely, a subgraph

H

of the network

G

such that subsequent to the failure of a single vertex, the surviving part of

H

still contains an

additive

spanner for (the surviving part of)

G

, satisfying dist(

s

,

t

,

H

 ∖ {

v

}) ≤ dist(

s

,

t

,

G

 ∖ {

v

}) + 

β

for every

s

,

t

,

v

 ∈ 

V

. Recently, the problem of constructing fault-tolerant additive spanners resilient to the failure of up to

f

-

edges

has been considered [8]. The problem of handling

vertex

failures was left open therein. In this paper we develop new techniques for constructing additive FT-spanners overcoming the failure of a single vertex in the graph. Our first result is an FT-spanner with additive stretch 2 and

O

(

n

5/3

) edges. Our second result is an FT-spanner with additive stretch 6 and

O

(

n

3/2

) edges. The construction algorithm consists of two main components: (a) constructing an FT-clustering graph and (b) applying a modified path-buying procedure suitably adopted to failure prone settings. Finally, we also describe two constructions for

fault-tolerant multi-source additive spanners

, aiming to guarantee a bounded additive stretch following a vertex failure, for every pair of vertices in

S

×

V

for a given subset of sources

S

 ⊆ 

V

. The additive stretch bounds of our constructions are 4 and 8 (using a different number of edges).

Let

G

 = (

V

,

E

) be an unweighted undirected graph with

n

-vertices and

m

-edges, and let

k

 > 2 be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source

s

and a destination

t

at distance Δ from

s

, routes a message from

s

to

t

on a path whose length is

O

(

k

Δ + 

m

1/

k

). The total space used by our routing scheme is

$\tilde{O}(mn^{O(1/\sqrt{\log n})})$

, which is almost linear in the number of edges of the graph. We present also a routing scheme with

$\tilde{O}(n^{O(1/\sqrt{\log n})})$

header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of

every

v

 ∈ 

V

is at most

$\tilde{O}(kn^{O(1/\sqrt{\log n})}deg(v))$

, where

deg

(

v

) is the degree of

v

in

G

. Our results are obtained by combining a general technique of Bernstein [6], that was presented in the context of dynamic graph algorithms, with several new ideas and observations.

Tree embeddings

are a powerful tool in the area of graph approximation algorithms. Essentially, they transform problems on general graphs into much easier ones on trees. Fakcharoenphol, Rao, and Talwar (FRT) [STOC’04] present a probabilistic tree embedding that transforms

n

-node metrics into (probability distributions over) trees, while

stretching

each pairwise distance by at most an

O

(log

n

) factor in expectation. This

O

(log

n

) stretch is optimal.

Khan et al. [PODC’08] present a distributed algorithm that implements FRT in

O

(SPD log

n

) rounds, where SPD is the

shortest-path-diameter

of the weighted graph, and they explain how to use this embedding for various distributed approximation problems. Note that SPD can be as large as Θ(

n

), even in graphs where the hop-diameter

D

is a constant. Khan et al. noted that it would be interesting to improve this complexity. We show that this is indeed possible.

More precisely, we present a distributed algorithm that constructs a tree embedding that is essentially as good as FRT in

$\tilde{O}(\min\{n^{0.5+\varepsilon },\operatorname{SPD}\}+D)$

rounds, for any constant

ε

 > 0. A lower bound of

$\tilde{\Omega}(\min\{n^{0.5},\operatorname{SPD}\}+D)$

rounds follows from Das Sarma et al. [STOC’11], rendering our round complexity near-optimal.

We study deterministic leader election in multi-hop radio networks in the beeping model. More specifically, we address explicit leader election: One node is elected as the leader, the other nodes know its identifier, and the algorithm terminates at some point with the network being quiescent. No initial knowledge of the network is assumed, i.e., nodes know neither the size of the network nor their degree, they only have a unique identifier. Our main contribution is a deterministic explicit leader election algorithm in the synchronous beeping model with a run time of

O

(

D

log

n

) rounds. This is achieved by carefully combining a fast local election algorithm with two new techniques for synchronization and communication in radio networks.

Sybil attacks

occur when malicious users create multiple fake identities to gain an advantage over honest users. Wireless ad hoc networks are particularly vulnerable to these attacks because the participants are not known in advance, and they use an open and shared communication medium. In this paper, we develop algorithms that thwart sybil attacks in multi-channel wireless ad hoc networks using

radio resource testing

strategies. In particular, we describe and analyze new anti-sybil algorithms that guarantee, with high probability, that each honest device accepts a set of trusted and unforgeable identities that include all other honest devices and a bounded number of fake (sybil) identities. The proposed algorithms provide trade-offs between time complexity and sybil bounds. We also note that these algorithms solve, as subroutines, two problems of independent interest in this anonymous wireless setting: Byzantine consensus and network size estimation.

Although any problem in a radio network can be solved using broadcast algorithms, some problems can be solved substantially more efficiently by more specialized algorithms. This paper presents two new approximate algorithms for the

local sum

problem, in which each node computes a (1±

ε

)-approximation to the sum of the values held by its incoming neighbors (nodes that have outgoing edges to the node). We propose algorithms both with and without collision detection, as well as for the beeping model, with round complexity

$O({\log^{2} n + \log n\log m \over \epsilon^2})$

, where

n

is the number of nodes and the value held by each node is a real number in {0} ∪ [1,

m

]. We then show how these algorithms can be used as building blocks to construct applications such as approximate random walk distribution, PageRank, and global sum.

Theoreticians have studied distributed algorithms in the synchronous radio network model for close to three decades. A significant fraction of this work focuses on lower bounds for basic communication problems such as

wake-up

(symmetry breaking among an unknown set of nodes) and

broadcast

(message dissemination through an unknown network topology). In this paper, we introduce a new technique for proving this type of bound, based on reduction from a probabilistic hitting game, that simplifies and strengthens much of this existing work. In more detail, in this single paper we prove new expected time and high probability lower bounds for wake-up and global broadcast in single and multi-channel versions of the radio network model both with and without collision detection. In doing so, we are able to reproduce results that previously spanned a half-dozen papers published over a period of twenty-five years. In addition to simplifying these existing results, our technique, in many places, also improves the state of the art: of the eight bounds we prove, four strictly strengthen the best known previous result (in terms of time complexity and/or generality of the algorithm class for which it holds), and three provide the first known non-trivial bound for the case in question. The fact that the same technique can easily generate this diverse collection of lower bounds indicates a surprising unity underlying communication tasks in the radio network model—revealing that deep down, below the specifics of the problem definition and model assumptions, communication in this setting reduces to finding efficient strategies for a simple game.

We study the correctness of shared data structures under reads-write concurrency. A popular approach to ensuring correctness of read-only operations in the presence of concurrent update, is read-set validation, which checks that all read variables have not changed since they were first read. In practice, this approach is often too conservative, which adversely affects performance. In this paper, we introduce a new framework for reasoning about correctness of data structures under reads-write concurrency, which replaces validation of the entire read-set with more general criteria. Namely, instead of verifying that all read shared variables still hold the values read from them, we verify abstract conditions over the shared variables, which we call

base conditions

. We show that reading values that satisfy some base condition at every point in time implies correctness of read-only operations executing in parallel with updates. Somewhat surprisingly, the resulting correctness guarantee is not equivalent to linearizability, and is instead captured through two new conditions:

validity

and

regularity

. Roughly speaking, the former requires that a read-only operation never reaches a state unreachable in a sequential execution; the latter generalizes Lamport’s notion of regularity for arbitrary data structures, and is weaker than linearizability. We further extend our framework to capture also linearizability. We illustrate how our framework can be applied for reasoning about correctness of a variety of implementations of data structures such as linked lists.

In this paper we study efficient implementations for deterministic abortable objects. Deterministic abortable objects behave like ordinary objects when accessed sequentially, but they may return a special response

abort

to indicate that the operation failed (and did not take effect) when there is contention.

It is impossible to implement deterministic abortable objects only with read/write registers [3]. Thus, we study

solo-fast

implementations. These implementations use stronger synchronization primitives, e.g., CAS, only when there is contention. We consider interval contention.

We present a non-trivial solo-fast universal construction for deterministic abortable objects. A universal construction is a method for obtaining a concurrent implementation of any object from its sequential code. The construction is

non-trivial

since in the resulting implementation a failed process can cause only a finite number of operations to abort. Our construction guarantees that operations that do not modify the object always return a legal response and do not use CAS. Moreover in case of contention, at least one writing operation succeeds. We prove that our construction has asymptotically optimal space complexity for objects whose size is constant.

We study the space complexity of implementing long-lived and one-shot adaptive renaming from multi-reader multi-writer registers, in an asynchronous distributed system with

n

processes. In an

f

(

k

)

-adaptive renaming algorithm

each participating process gets a distinct name, in the range {1,…,

f

(

k

)} provided

k

processes participate.

We show that any obstruction-free long-lived

f

(

k

)-adaptive renaming object requires

m

registers, where

m

 ≤ 

n

 − 1 is the largest integer such that

f

(

m

) ≤ 

n

 − 1. This implies a lower bound of

n

 − 

c

registers for long-lived (

k

 + 

c

)-adaptive renaming, which is tight. We also prove a lower bound of

$\lfloor \frac{n}{c+1} \rfloor$

registers for implementing any obstruction-free one-shot (

k

 + 

c

)-adaptive renaming.

We also provide one-shot renaming algorithms, e.g., a wait-free one-shot

$(\frac{3k^2}{2})$

-adaptive one from

$\lceil \sqrt{n} \rceil $

registers, and an obstruction-free one-shot

f

(

k

)-adaptive renaming algorithm from only ⌈

f

− 1

(

n

) ⌉ registers.

In this paper, we study lower bounds for randomized solutions to the maximal independent set (MIS) and connected dominating set (CDS) problems in the dual graph model of radio networks—a generalization of the standard graph-based model that now includes unreliable links controlled by an adversary. We begin by proving that a natural geographic constraint on the network topology is required to solve these problems efficiently (i.e., in time polylogarthmic in the network size). In more detail, we prove that in the absence of this constraint, for a network of size

n

: every MIS algorithm now requires Ω(

n

1 − 

ε

) rounds to solve the problem, for any constant

ε

, 0 < 

ε

 ≤ 1, and every CDS algorithm that provides a reasonable approximation of a minimum CDS now requires

$\Omega(\sqrt{n}/\log{n})$

rounds. We then prove the importance of the assumption that nodes are provided advance knowledge of their reliable neighbors (i.e, neighbors connected by reliable links). In more detail, we prove that in the absence of this assumption, for any CDS algorithm that guarantees a

g

(

n

)-approximation of a minimum CDS in

f

(

n

) rounds, it follows that

g

(

n

) + 

f

(

n

) = Ω(

n

). This holds even if we assume the geographic constraint and the weakest possible adversary controlling the unreliable links. Finally, we show that although you can efficiently build an MIS without advance neighborhood knowledge, this omission increases the problem’s dependence on the geographic constraint. When both constraints are missing, every MIS algorithm now requires Ω(

n

) rounds, even if we assume the weakest possible adversary. Combined, these results answer an open question by proving that the efficient MIS and CDS algorithms from [2] are optimal with respect to their dual graph model assumptions. They also provide insight into what properties of an unreliable network enable efficient local computation.

In this paper we consider dynamic networks that can change over time. Often, such networks have a repetitive pattern despite constant and otherwise unpredictable changes. Based on this observation, we introduce the notion of a

ρ-recurring family

of a dynamic network, which has the property that the dynamic network frequently contains a graph in the family, where frequently means at a rate 0<

ρ

 ≤ 1. Using this concept, we reduce the analysis of max-degree random walks on dynamic networks to the case for static networks. Given a dynamic network with a

ρ

-recurring family

$\mathcal{F}$

, we prove an upper bound of

on the hitting and cover times, and an upper bound of

$O\left( \rho^{-1}(1- \hat\lambda(\mathcal{F}))^{-1} \log n \right) $

on the mixing time of random walks, where

n

is the number of nodes,

$\hat t_{hit}(\mathcal{F})$

is upper bound on the hitting time of graphs in

$\mathcal{F}$

, and

$\hat\lambda(\mathcal{F})$

is upper bound on the second largest eigenvalue of the transition matrices of graphs in

$\mathcal{F}$

. These results have two implications. First, they yield a general bound of

$O\left( \rho^{-1} n^3 \log n \right) $

on the hitting time and cover time of a dynamic network (

ρ

is the rate at which the network is connected); this result improves on the previous bound of

$O\left( \rho^{-1} n^5 \log^2 n \right) $

,[3]. Second, the results imply that dynamic networks with recurring families preserve the properties of random walks in their static counterparts. This result allows importing the extensive catalogue of results for static graphs (cliques, expanders, regular graphs, etc.) into the dynamic setting.

The

Push-Pull

protocol is a well-studied round-robin rumor spreading protocol defined as follows: initially a node knows a rumor and wants to spread the rumor to all nodes in a network quickly. In each round, every informed node sends the rumor to a random neighbor, and every uninformed node contacts a random neighbor and gets the rumor from her if she knows it. We analyze the behavior of this protocol on random

k

-trees, a class of power law graphs which are small-world and have large clustering coefficients, built as follows: initially we have a

k

-clique. In every step a new node is born, a random

k

-clique of the current graph is chosen, and the new node is joined to all nodes of the

k

-clique. When

k

 > 2 is fixed, we show that if initially a random node is aware of the rumor, then with probability 1 − 

o

(1) after

$\mathcal{O}\left( (\log n)^{{(k+3)}/{(k+1)}} \cdot \log \log n\cdot f(n) \right)$

rounds the rumor propagates to

n

 − 

o

(

n

) nodes, where

n

is the number of nodes and

f

(

n

) is any slowly growing function. When

k

 = 2, the previous statement holds for

$\mathcal{O} \left( \log ^2n\cdot \log \log n \cdot f(n) \right)$

many rounds. Since these graphs have polynomially small conductance, vertex expansion

$\mathcal{O}(1/n)$

and constant treewidth, these results demonstrate that

Push-Pull

can be efficient even on poorly connected networks.

On the negative side, we prove that with probability 1 − 

o

(1) the protocol needs at least

$\Omega\left(n^{({k-1})/({k^2+k-1})}/f^2(n)\right)$

rounds to inform all nodes. This exponential dichotomy between time required for informing

almost all

and

all

nodes is striking. Our main contribution is to present, for the first time, a natural class of random graphs in which such a phenomenon can be observed. Our technique for proving the upper bound successfully carries over to a closely related class of graphs, the random

k

-Apollonian networks, for which we prove an upper bound of

$\mathcal{O}\left( (\log n) ^{{{(k^2-3)}/{(k-1)^2}}} \cdot \log \log n \cdot f(n) \right)$

rounds for informing

n

 − 

o

(

n

) nodes with probability 1 − 

o

(1), when

k

 > 2 is a constant.

Linearizability, a widely-accepted correctness property for shared objects, is grounded in classical physics. Its definition assumes a total temporal order over invocation and response events, which is tantamount to assuming the existence of a global clock that determines the time of each event. By contrast, according to Einstein’s theory of relativity, there can be no global clock: time itself is relative. For example, given two events

A

and

B

, one observer may perceive

A

occurring before

B

, another may perceive

B

occurring before

A

, and yet another may perceive

A

and

B

occurring simultaneously,with respect to local time.

Here, we generalize linearizability for relativistic distributed systems using techniques that do not rely on a global clock. Our novel correctness property, called

relativistic linearizability

, is instead defined in terms of causality. However, in contrast to standard “causal consistency,” our interpretation defines relativistic linearizability in a manner that retains the important

locality

property of linearizability. That is, a collection of shared objects behaves in a relativistically linearizable way if and only if each object individually behaves in a relativistically linearizable way.

One of the main challenges in stating the correctness of transactional memory (TM) systems is the need to provide guarantees on the system state observed by live transactions, i.e., those that have not yet committed or aborted. A TM correctness condition should be weak enough to allow flexibility in implementation, yet strong enough to disallow undesirable TM behavior, which can lead to run-time errors in live transactions. The latter feature is formalized by

observational refinement

between TM implementations, stating that properties of a program using a concrete TM implementation can be established by analyzing its behavior with an abstract TM, serving as a specification of the concrete one.

We show that a variant of

transactional memory specification (TMS)

, a TM correctness condition, is equivalent to observational refinement for the common programming model in which local variables are rolled back upon a transaction abort and, hence, is the weakest acceptable condition for this case. This is challenging due to the nontrivial formulation of TMS, which allows different aborted and live transactions to have different views of the system state. Our proof reveals some natural, but subtle, assumptions on the TM required for the equivalence result.

Transactional memory (TM) algorithms are subtle and the TM correctness conditions are intricate. Decomposition of the correctness condition can bring modularity to TM algorithm design and verification. We present a decomposition of opacity called markability as a conjunction of separate intuitive invariants. We prove the equivalence of opacity and markability. The proofs of markability of TM algorithms can be aided by and mirror the algorithm design intuitions. As an example, we prove the markability and hence opacity of the TL2 algorithm. In addition, based on one of the invariants, we present lower bound results for the time complexity of TM algorithms.

Priority queues are fundamental abstract data structures, often used to manage limited resources in parallel programming. Several proposed parallel priority queue implementations are based on skiplists, harnessing the potential for parallelism of the

add()

operations. In addition, methods such as Flat Combining have been proposed to reduce contention, batching together multiple operations to be executed by a single thread. While this technique can decrease lock-switching overhead and the number of pointer changes required by the

removeMin()

operations in the priority queue, it can also create a sequential bottleneck and limit parallelism, especially for non-conflicting

add()

operations.

In this paper, we describe a novel priority queue design, harnessing the scalability of parallel insertions in conjunction with the efficiency of batched removals. Moreover, we present a new elimination algorithm suitable for a priority queue, which further increases concurrency on balanced workloads with similar numbers of

add()

and

removeMin()

operations. We implement and evaluate our design using a variety of techniques including locking, atomic operations, hardware transactional memory, as well as employing adaptive heuristics given the workload.

Linearizability is a powerful consistency condition but can be expensive to implement. Recently, reserarchers have suggested gaining performance by relaxing the sequential specification of objects’ data types. We consider, for the first time, linearizable

message-passing

implementations of relaxed Queues and prove upper and lower bounds on the elapsed time for

Dequeue

operations both in the worst case and on average.

Our results imply that worst-case time complexity does not indicate benefit from relaxation. In contrast, we present implementations of relaxed Queues for which the

average time complexity

of

Dequeue

is significantly smaller than both the worst-case lower bound for unrelaxed Queues and a newly-proved lower bound on the average time for unrelaxed Queues. We also prove lower bounds on the average time complexity of

Dequeue

for relaxed Queues that show our algorithms are asymptotically optimal and that there is an inherent complexity gap between different levels of relaxation.

We study the problem of computing the minimum cut in a weighted distributed message-passing networks (the

CONGEST

model). Let

λ

be the minimum cut,

n

be the number of nodes (processors) in the network, and

D

be the network diameter. Our algorithm can compute

λ

exactly in

$O((\sqrt{n} \log^{*} n +D)\lambda^4 \log^2 n)$

time. To the best of our knowledge, this is the first paper that explicitly studies computing the exact minimum cut in the distributed setting. Previously, non-trivial sublinear time algorithms for this problem are known only for unweighted graphs when

λ

 ≤ 3 due to Pritchard and Thurimella’s

O

(

D

)-time and

O

(

D

 + 

n

1/2

log

*

n

)-time algorithms for computing 2-edge-connected and 3-edge-connected components [ACM Transactions on Algorithms 2011].

By using the edge sampling technique of Karger [STOC 1994], we can convert this algorithm into a (1 + 

ε

)-approximation

$O((\sqrt{n}\log^{*} n+D)\epsilon^{-5}\log^3 n )$

-time algorithm for any

ε

 > 0. This improves over the previous (2 + 

ε

)-approximation

$O((\sqrt{n}\log^{*} n+D)\epsilon^{-5}\log^2 n \log \log n)$

-time algorithm and

O

(

ε

− 1

)-approximation

$O(D + n^{\frac{1}{2}+\epsilon}\operatorname{poly}\log n)$

-time algorithm of Ghaffari and Kuhn [DISC 2013]. Due to the lower bound of Ω(

D

 + 

n

1/2

/log

n

) by Das Sarma et al. [SICOMP 2013] which holds for any approximation algorithm, this running time is

tight

up to a polylog

n

factor.

To get the stated running time, we developed an approximation algorithm which combines the ideas of Thorup’s algorithm [Combinatorica 2007] and Matula’s contraction algorithm [SODA 1993]. It saves an

ε

− 9

log

7

n

factor as compared to applying Thorup’s tree packing theorem directly. Then, we combine Kutten and Peleg’s tree partitioning algorithm [J. Algorithms 1998] and Karger’s dynamic programming [JACM 2000] to achieve an efficient distributed algorithm that finds the minimum cut when we are given a spanning tree that crosses the minimum cut exactly once.

We explore the question how well we can color graphs in distributed models, especially in graph classes for which Δ + 1-colorings provide no approximation guarantees. We particularly focus on interval graphs.

In the

$\mathcal{LOCAL}$

model, we give an algorithm that computes a constant factor approximation to the coloring problem on interval graphs in O(log

*

n

) rounds, which is best possible. The result holds also for the

$\mathcal{CONGEST}$

model when the representation of the nodes as intervals is given.

We then consider restricted beep models, where communication is restricted to the aggregate acknowledgment of whether a node’s attempted coloring succeeds. We apply an algorithm designed for the SINR model and give a simplified proof of a

O

(log

n

)-approximation. We show a nearly matching Ω(log

n

/ loglog

n

)-approximation lower bound in that model.

Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and Δ + 1-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in

hypergraphs

. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs.

In this paper, we study the distributed complexity of symmetry breaking in hypergraphs by presenting distributed randomized algorithms for a variety of fundamental problems under a natural distributed computing model for hypergraphs. We first show that MIS in hypergraphs (of arbitrary dimension) can be solved in

O

(log

2

n

) rounds (

n

is the number of nodes of the hypergraph) in the LOCAL model. We then present a key result of this paper — an

O

(Δ

ε

polylog

n

)-round hypergraph MIS algorithm in the CONGEST model where Δ is the maximum node degree of the hypergraph and

ε

 > 0 is any arbitrarily small constant. We also present distributed algorithms for coloring, maximal matching, and maximal clique in hypergraphs.

To demonstrate the usefulness of hypergraph MIS, we present applications of our hypergraph algorithm to solving problems in (standard) graphs. In particular, the hypergraph MIS yields fast distributed algorithms for the

balanced minimal dominating set

problem (left open in Harris et al. [ICALP 2013]) and the

minimal connected dominating set problem

.

Our work shows that while some local symmetry breaking problems such as coloring can be solved in polylogarithmic rounds in both the LOCAL and CONGEST models, for many other hypergraph problems such as MIS, hitting set, and maximal clique, it remains challenging to obtain polylogarithmic time algorithms in the CONGEST model. This work is a step towards understanding this dichotomy in the complexity of hypergraph problems as well as using hypergraphs to design fast distributed algorithms for problems in (standard) graphs.

We develop the first streaming algorithm and the first two-party communication protocol that uses a constant number of passes/rounds and sublinear space/communication for logarithmic approximation to the classic Set Cover problem. Specifically, for

n

elements and

m

sets, our algorithm/protocol achieves a space bound of

O

(

m

·

n

δ

log

2

n

log

m

) using

O

(4

1/

δ

) passes/rounds while achieving an approximation factor of

O

(4

1/

δ

log

n

) in polynomial time (for

δ

 = Ω(1/log

n

)). If we allow the algorithm/protocol to spend exponential time per pass/round, we achieve an approximation factor of

O

(4

1/

δ

). Our approach uses randomization, which we show is necessary: no deterministic constant approximation is possible (even given exponential time) using

o

(

m

n

) space. These results are some of the first on streaming algorithms and efficient two-party communication protocols for approximation algorithms. Moreover, we show that our algorithm can be applied to multi-party communication model.

We study the communication complexity of linear algebraic problems over finite fields in the multi-player message passing model, proving a number of tight lower bounds. We give a general framework for reducing these multi-player problems to their two-player counterparts, showing that the randomized

s

-player communication complexity of these problems is at least

s

times the randomized two-player communication complexity. Provided the problem has a certain amount of algebraic symmetry, we can show the hardest input distribution is a symmetric distribution, and therefore apply a recent multi-player lower bound technique of Phillips

et al

. Further, we give new two-player lower bounds for a number of these problems. In particular, our optimal lower bound for the two-player version of the matrix rank problem resolves an open question of Sun and Wang.

A common feature of our lower bounds is that they apply even to the special “threshold promise” versions of these problems, wherein the underlying quantity, e.g., rank, is promised to be one of just two values, one on each side of some critical threshold. These kinds of promise problems are commonplace in the literature on data streaming as sources of hardness for reductions giving space lower bounds.

This paper presents constant-time and near-constant-time distributed algorithms for a variety of problems in the congested clique model. We show how to compute a 3-ruling set in expected

O

(logloglog

n

) rounds and using this, we obtain a constant-approximation to metric facility location, also in expected

O

(logloglog

n

) rounds. In addition, assuming an input metric space of constant doubling dimension, we obtain constant-round algorithms to compute constant-factor approximations to the minimum spanning tree and the metric facility location problems. These results significantly improve on the running time of the fastest known algorithms for these problems in the congested clique setting.