Theory of Distributed Systems (TDS)

Alkida Balliu: Local Distribution Verification
Monday, October 17, 2016 - 11:00am to 12:00pm

We are considering distributed network computing, in which computing entities are connected by a network modeled as a connected graph. These entities are located at the nodes of the graph, and they exchange information by message-passing along its edges.

Sergio Rajsbaum: Specifying Concurrent Problems: Beyond Linearizability and up to Tasks
Friday, September 30, 2016 - 1:00pm to 2:30pm

Tasks and objects are two predominant ways of specifying distributed problems. A task specifies for each set of processes (which may run concurrently) the valid outputs of the processes. An object specifies the outputs the object may produce when it is accessed sequentially.

Gopal Pandurangan: Distributed Computation of Large-scale Graph Problems
Thursday, June 16, 2016 - 1:00pm to 2:30pm

Abstract: Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph, biological networks and various social networks, we study a number of fundamental graph problems

Cameron Musco and Hsin-Hao Su: Ant-Inspired Density Estimation via Random Walks
Friday, April 1, 2016 - 1:00pm to 2:30pm
Abstract: I will discuss our recent PODC submission on Ant-Inspired Density Estimation. The work gives a probabilistic analysis of a very simple ant-inspired algorithm for population density estimation.
Tsvi Kopelowitz: A Class of $O(\log\log^* N)$ Problems in Distributed Computing: Contention Resolution, Counting, and Leader Election
Friday, March 18, 2016 - 1:00pm to 2:30pm

For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource.

Mohsen Ghaffari and Hsin-Hao Su: Generalizing the Congested Clique
Friday, February 26, 2016 - 1:00pm to 2:30pm
Abstract: The congested clique model of distributed computing has received increasingly more attention in the past few years.
Jimmy Zhu: A Tight Space Bound for Consensus
Monday, February 15, 2016 - 1:00pm to 2:30pm
Abstract: Existing n-process randomized wait-free (and obstruction-free) consensus algorithms from registers all use at least n registers. In 1993, it was proved that such algorithms need to use at least Omega(sqrt(n)) registers.
Kishori Konwar: Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems
Friday, December 4, 2015 - 1:00pm to 2:30pm

Erasure codes are increasingly being studied in the context of implementing atomic memory objects in large

Hsin-Hao Su: Distributed (Delta+1)-Coloring in Sublogarithmic Rounds
Friday, November 6, 2015 - 1:00pm to 2:30pm

The (Delta+1)-coloring problem and the MIS (maximal independent set) problem are fundamental distributed symmetry-breaking problems.

Mohsen Lesani: Certified Causally Consistent Distributed Key-Value Stores
Friday, October 23, 2015 - 1:00pm to 2:30pm

Today’s Internet services are often expected to stay available and
render high responsiveness even in the face of site crashes and
network partitions. Theoretical results state that causal consistency
is one of the strongest consistency guarantees that is possible under


Subscribe to Theory of Distributed Systems (TDS)