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

Beginning on Sunday, November 27 and ending Friday December 2, 2016

All times in Oaxaca, Mexico time, CST (UTC-6).

Sunday, November 27 | |
---|---|

14:00 - 23:59 | Check-in begins - open 24 hours (Front desk at your assigned hotel) |

19:00 - 22:00 | Dinner (Restaurant Hotel Hacienda Los Laureles) |

20:30 - 21:30 |
Informal gathering ↓ A welcome drink will be served at the hotel. (Hotel Hacienda Los Laureles) |

Monday, November 28 | |
---|---|

07:30 - 08:45 | Breakfast (Restaurant at your assigned hotel) |

08:45 - 09:00 | Introduction and Welcome (Conference Room San Felipe) |

09:00 - 10:00 |
Dan Alistarh: Data Structures of the Future: Concurrent, Optimistic, and Relaxed ↓ 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. (Conference Room San Felipe) |

10:00 - 10:30 |
Michel Raynal: t-Resilient k-Immediate Snapshot and its Relation with Agreement Problems ↓ 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 |

10:30 - 11:00 | Coffee Break (Conference Room San Felipe) |

11:00 - 11:45 | Fabian Kuhn: Complexity of Distributed Graph Algorithms in the LOCAL model (Conference Room San Felipe) |

11:45 - 12:30 |
Faith Ellen: Deterministic Objects: Life Beyond Consensus ↓ 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. (Conference Room San Felipe) |

12:30 - 13:15 |
Wojciech Golab: Supporting and Analyzing Probabilistic Consistency in Distributed Storage Systems ↓ 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. (Conference Room San Felipe) |

13:15 - 13:30 | Group Photo (Hotel Hacienda Los Laureles) |

13:30 - 15:00 | Lunch (Restaurant Hotel Hacienda Los Laureles) |

15:00 - 16:00 |
Armando Castañeda: Asynchronous Robot Gathering ↓ 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. (Conference Room San Felipe) |

16:00 - 17:00 | Maurice Herlihy: A Tutorial on Applying Combinatorial Topology to Byzantine Tasks (Conference Room San Felipe) |

19:00 - 21:00 | Dinner (Restaurant Hotel Hacienda Los Laureles) |

Tuesday, November 29 | |
---|---|

07:30 - 09:00 | Breakfast (Restaurant at your assigned hotel) |

09:00 - 10:00 | Dahlia Malkhi: PODC - Practice of Distributed Computing (Conference Room San Felipe) |

10:00 - 10:30 | Avery Miller: Communicating with Beeps (Conference Room San Felipe) |

10:30 - 11:00 | Coffee Break (Conference Room San Felipe) |

11:00 - 11:45 |
Fabian Reiter: Asynchrony and Least Fixpoint Logic ↓ 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). (Conference Room San Felipe) |

11:45 - 12:30 |
Michael Bender: Three Backoff Dilemmas ↓ 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. (Conference Room San Felipe) |

12:30 - 13:15 | Eli Gafni: 3 Original Sins + (Conference Room San Felipe) |

13:30 - 15:00 | Lunch (Restaurant Hotel Hacienda Los Laureles) |

15:00 - 16:00 |
Erez Petrank: Memory Management for Lock-Free Data-Structures ↓ 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. (Conference Room San Felipe) |

16:00 - 16:30 |
Leqi Zhu: Space Lower Bound for Consensus ↓ 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. (Conference Room San Felipe) |

16:30 - 17:00 | Rati Gelashvili: Space-based Hierarchy, Buffered Read-Write and Multi-Assignment (Conference Room San Felipe) |

19:00 - 21:00 | Dinner (Restaurant Hotel Hacienda Los Laureles) |

Wednesday, November 30 | |
---|---|

07:30 - 09:00 | Breakfast (Restaurant at your assigned hotel) |

09:00 - 10:00 |
Idit Keidar: Dynamic Memory - It's Time to Talk About Complexity ↓ 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. (Conference Room San Felipe) |

10:00 - 10:30 | Anne-Marie Kermarrec: Sketching Your Way Toward Greater Efficiency (Conference Room San Felipe) |

10:30 - 11:00 | Coffee Break (Conference Room San Felipe) |

11:00 - 11:30 |
Seth Gilbert: Gossip, Latency, and Weighted Conductance ↓ 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. (Conference Room San Felipe) |

11:30 - 12:00 |
Jennifer Welch: Message-Passing Implementations of Shared Data Structures ↓ 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. (Conference Room San Felipe) |

12:00 - 13:30 | Lunch (Restaurant Hotel Hacienda Los Laureles) |

13:30 - 19:00 | Excursion (TBD) |

19:00 - 21:00 | Dinner (Restaurant Hotel Hacienda Los Laureles) |

Thursday, December 1 | |
---|---|

07:30 - 09:00 | Breakfast (Restaurant at your assigned hotel) |

09:00 - 10:00 |
Rotem Oshman: CONGEST lower bounds : beyond two-party reductions ↓ 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. (Conference Room San Felipe) |

10:00 - 10:30 |
Rachid Guerraoui: The Atomic Commit Problem: A Brief History ↓ 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. (Conference Room San Felipe) |

10:30 - 11:00 | Coffee Break (Conference Room San Felipe) |

11:00 - 11:45 |
Lisa Higham: Test and Set in Optimal Space ↓ 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. (Conference Room San Felipe) |

11:45 - 12:30 | George Giakkoupis: Randomized Adversary Models (Conference Room San Felipe) |

12:30 - 13:15 |
Danny Hendler: The Backtracking Covering Proof Technique ↓ 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. (Conference Room San Felipe) |

13:30 - 15:00 | Lunch (Restaurant Hotel Hacienda Los Laureles) |

15:00 - 16:00 |
Valerie King: Byzantine Agreement with Full Information: Towards a Practical Algorithm ↓ 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. (Conference Room San Felipe) |

16:00 - 16:30 |
Petr Kuznetsov: Concurrency as an Iterated Affine Task ↓ 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. (Conference Room San Felipe) |

16:30 - 17:00 |
Eric Ruppert: Analysing the Average Time Complexity of Lock-Free Data Structures ↓ 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. (Conference Room San Felipe) |

19:00 - 21:00 | Dinner (Restaurant Hotel Hacienda Los Laureles) |

Friday, December 2 | |
---|---|

07:30 - 09:00 | Breakfast (Restaurant at your assigned hotel) |

09:00 - 10:00 |
Yoram Moses: Indistinguishability, Duality and Necessary Conditions ↓ 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. (Conference Room San Felipe) |

10:00 - 10:30 |
Ohad Ben Baruch: Lower Bound on the Step Complexity of Anonymous Binary Consensus ↓ 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. (Conference Room San Felipe) |

10:30 - 11:00 | Coffee Break (Conference Room San Felipe) |

11:00 - 12:00 |
Zahra Aghazadeh: Boundless tagging with applications to wait-free memory reclamation ↓ 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. (Conference Room San Felipe) |

12:00 - 14:30 | Lunch (Restaurant Hotel Hacienda Los Laureles) |