Schedule for: 16w5152 - Complexity and Analysis of Distributed Algorithms

A welcome drink will be served at the hotel.

A central computing trend over the last decade has been the need to process increasingly larger amounts of data as efficiently as possible. This development is challenging both software and hardware design, and is altering the way data structures and algorithms are constructed, implemented, and deployed. In this talk, I will present some examples of such new data structure design ideas and implementations. In particular, I will discuss some inherent limitations of parallelizing classic data structures, and then focus on approaches to circumvent these limitations. The first approach is to relax the software semantics, to allow for approximation, randomization, or both. The second is to modify the underlying hardware architecture to unlock more parallelism. Time permitting, I will also cover results showing that both approaches can improve real-world performance, and touch upon some of the major open questions in the area.

An immediate snapshot object is a high level communication object, built on top of a read/write distributed system in which all except one processes may crash. It allows each process to write a value and obtains a set of pairs (process id, value)such that, despite process crashes and asynchrony, the sets obtained by the processes satisfy noteworthy inclusion properties. Considering an n-process model in which up to t processes may crash, this paper introduces first the k-resilient immediate snapshot object, which is a natural generalization of the basic immediate snapshot (which corresponds to the case k=t=n-1). In addition to the set containment properties of the basic immediate snapshot, a k-resilient immediate snapshot object requires that each set returned to a process contains at least (n-k) pairs. The paper first shows that, for k,t (TBD)

For all integers $m \geq 2$, we construct an infinite sequence of deterministic objects of consensus number $m$ with strictly increasing computational power. In particular, this refutes the Common2 Conjecture, which claimed that every deterministic object of consensus number 2 has a deterministic, wait-free implementation from 2-consensus objects and registers in a system with any finite number of processes.

Storage systems lie at the heart of essential online services such as email, online shopping, and social networking. Distributing such systems over multiple data centers and geographical regions is technically challenging due to a number of impossibility results arising from asynchrony, computer failures, network failures, as well as the finite propagation speed of light. This tutorial-style talk will discuss the use of randomization to circumvent these impossibility results with a focus on data consistency, which defines what values may be returned by storage operations depending on other operations applied concurrently or previously in the same execution. The talk will survey prior and ongoing work on defining precise notions of probabilistic consistency, computing consistency metrics, and tuning the consistency-latency trade-off.

This talk is a short tutorial of the study of distributed computing through combinatorial topology. This approach is presented through three variants of the well-known gathering problem, in the context of fully asynchronous crash-prone robots that move on a discrete space modeled as a graph. The results resented are research in progress.

The goal of this talk is to raise interest in the connections between distributed computing and formal logic. I will illustrate this relatively unexplored area of research by presenting an equivalence result between two very specific systems. The distributed computing side will be represented by a notion of asynchronous distributed automaton with finite memory, while the formal logic side will be represented by a small fragment of least fixpoint logic (more specifically, a fragment of the modal mu-calculus).

In this talk we revisit the classical problem of randomized exponential backoff on a multiple-access channel. We analyze randomized backoff with respect to throughput, robustness to jamming or failures, and the number of attempts to access the channel.

Lock-free data structures achieve high responsiveness, aid scalability, and avoid deadlocks and livelocks. But providing memory management support for such data structures without foiling their progress guarantees is difficult. Often, designers employ the hazard pointers technique, which may imposes a high performance overhead. In this talk we present the optimistic access scheme that provides efficient reclamation support for lock-free data-structures and also some automatization.

Existing $n$-process randomized wait-free (and obstruction-free) consensus protocols from registers all use at least $n$ registers. In this talk, I will go over a proof showing that every randomized wait-free (or obstruction-free) consensus protocol for $n$ processes must use at least $n − 1$ registers.

The study of dynamic (reconfigurable) shared objects (mostly, atomic registers emulated by a dynamic set of nodes) has been evolving for more than a decade. In this talk I will demonstrate that we are now finally at the point where we can give clean formulations of dynamic tasks, such as a dynamic atomic shared register, a dynamic replicated state machine, and dynamic atomic snapshots. We also have well-defined failure conditions and liveness notions. Given these definitions, it is now possible to compare objects in terms of computability (for example, a dynamic atomic register is implementable in an asynchronous shared memory system where consensus is not solvable), and complexity.

In this talk I will explore the problem of gossip in graphs where edges have latencies, giving near matching upper and lower bounds (within polylog factors). Along the way, we will define a notion of "weighted conductance" to capture the connectivity of a graph with latencies. Weighted conductance determines the performance of gossip protocols (and, perhaps, random walks) in graphs with latencies, much in the way that traditional conductance does in unweighted graphs.

Distributed storage, or shared data, is a vital mechanism for communication among processors in distributed systems, and facilitates the development of higher-level applications. Although shared data is a convenient abstraction, it is not generally provided directly in large-scale distributed systems but must be implemented on top of message-passing. In this talk, I will present an overview of some recent results by my colleagues and myself on the time complexity of operations on linearizable shared objects that are implemented on top of a partially synchronous message-passing system. First, we extend previous efforts to develop classifications of operations on shared objects based on axioms describing how the operations interact with each other. One classification facilitates the development of a general algorithm for implementing objects of any type in which the latency of operations improves on that of prior folklore algorithms. Using another classification, we prove lower bounds on several classes of operations which show that in a number of common cases, our algorithm is tight or almost tight. Second, we consider the popular idea of relaxing the specifications of data types in order to improve performance, in the context of message-passing implementations. We focus on a shared queue with a level of relaxation indicated by a parameter k, proposed by Henzinger et al. We show that, unfortunately, the worst-case time for a dequeue on this relaxed queue is almost as bad as in the unrelaxed case. However, there is an algorithm in which the amortized time for a dequeue decreases linearly as k increases, behavior which we prove is not attainable in the unrelaxed case. We also show that improved amortized performance as k increases is inherent.

Most CONGEST lower bounds are proven by reduction from two-party communication complexity. In this tutorial/talk we will discuss some limitations of existing reductions, and ways in which they might potentially be overcome. In particular, we'll cover: - The two-party pointer-chasing lower bound of Nisan-Widgerson - A connection between the broadcast congested clique and number-on-forehead communication complexity - The basics of multi-party number-in - hand communication complexity.

The Atomic Commit Problem is fundamental in distributed transactional processing systems. It consists for a set of processes to decide whether to abort or commit a transaction, based on the initial votes of the processes. The processes can commit only if their votes are positive and need to commit if all votes are positive and there is no failure in the system. The talk with recall the problem, survey fundamental (computability and complexity) results about it from the 80's to 2016, and highlight open related questions.

Several new and existing components and techniques are used to achieve two new results. - A obstruction-free implementation of test&set from O(log n) registers, thus establishing that the existing lower bound is asymptotically tight. - A randomized wait-free implementation of test and set from O(log n) registers and having O(log*n) solo step complexity under the oblivious adversary. I will describe these techniques, present details of 3 of them, and show how they are combined to provide these two algorithms.

Covering arguments are often used to derived space complexity lower bounds in the shared memory model, but it is often much more difficult to use them for obtaining time complexity lower bounds. The backtracking covering technique, introduced by Ellen, Hendler and Shavit in 2005 and used a few times since then, allows obtaining time lower bounds in some such situations. In this talk, I will describe the technique and will go through an extended example that shows how it is applied.

Over the last several years, I have worked with Jared Saia and other collaborators on Byzantine agreement in the full information model; first we found fast algorithms for the case where an adversary chooses the processors to corrupt at the start and then we found the first polynomial time algorithm for asynchronous Byzantine agreement in the general case. Given the recent interest in maintaining a public ledger, a natural question is whether our techniques can be made more practical. I'll explain the techniques and point out possible directions.

We consider models of computations expressed via sets of runs bounding the concurrency level: the number of processes that can be concurrently active. The model of k-concurrency is equivalent to the read-write shared-memory systems equipped with k-set-agreement objects. We show that every such model can be characterized by an affine task: a simple combinatorial structure (a simplicial complex), defined as a subset of simplices in the second degree of the standard chromatic subdivision. Our result implies the first combinatorial representation of models equipped with abstractions other than read-write registers.

Lock-free implementations of shared data structures guarantee that some operation eventually completes. However, individual operations may not complete, as long as other operations continue to be completed. Thus, worst-case time complexity of individual operations may not be defined. Thus, an amortized analysis of the time complexity is more suitable. This talk will survey some results and techniques used to analyse the average time required to perform operations on lock-free implementations in shared-memory systems.

This talk will discuss the most fundamental notion in distributed computing. I will present and prove a universal property for distributed computing, and discuss implications and applications.

Obstruction-free consensus, ensuring that a process running solo will eventually terminate, is at the core of practical ways to solve consensus, e.g., by using randomization or failure detectors. An obstruction-free consensus algorithm may not terminate in many executions, but it must terminate whenever a process runs solo. Such an algorithm can be evaluated by its solo step complexity, which bounds the worst case number of steps taken by a process running alone, from any configuration, until it decides. We will present a lower bound of $\Omega(\log n)$ on the solo step complexity of obstruction-free binary anonymous consensus. The proof constructs a sequence of executions in which more and more distinct variables are about to be written to, and then uses the backtracking covering technique to obtain a single execution in which many variables are accessed.

In this talk, I will explain a technique for memory reclamation. I will go over some applications including a new framework for tagging, which uses only a bounded number of tags of bounded size.