Tag Archives: consensus

Faster Randomized Consensus with an Oblivious Adversary

James Aspnes

Posted on by
Reply

Abstract: Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with constant probability. The first conciliator assumes unit-cost snapshots and achieves agreement among n processes with probability 1-ε in O(log* n + log(1/ε)) steps for each process. The second uses ordinary multi-writer registers, and achieves agreement with probability 1-ε in O(log log n + log(1/ε)) steps. Combining these constructions with known results gives randomized consensus for arbitrarily many possible input values using unit-cost snapshots in O(log* n) expected steps and randomized consensus for up to O(log n log log n) possible input values using ordinary registers in O(log log n) expected steps.

Guest: James Aspnes
Host: Zvi Lotker

Podcast: Play in new window | Download

Randomized Consensus in Expected O(n^2) Total Work using Single-Writer Registers

James Aspnes

Posted on by
Reply

Abstract:
A new weak shared coin protocol yields a randomized wait-free shared-memory consensus protocol that uses an optimal expected total work with single-writer registers despite asynchrony and process crashes. Previously, no protocol was known that achieved this bound without using multi-writer registers.

Guest: James Aspnes
Host: Yvonne-Anne Pignolet

Podcast: Play in new window | Download

Coordinated Consensus in Dynamic Networks

Fabian Kuhn, Yoram Moses and Rotem Oshman

Posted on by
Reply

Abstract:
We study several variants of coordinated consensus in dynamic networks. We assume a synchronous model, where the communication graph for each round is chosen by a worst-case adversary. The network topology is always connected, but can change completely from one round to the next. The model captures mobile and wireless networks, where communication can be unpredictable. In this setting we study the fundamental problems of eventual, simultaneous, and ∆-coordinated consensus, as well as their relationship to other distributed problems, such as determining the size of the network. We show that in the absence of a good initial upper bound on the size of the network, eventual consensus is as hard as computing deterministic functions of the input, e.g., the minimum or maximum of inputs to the nodes. We also give an algorithm for computing such functions that is optimal in every execution.

Guest: Rotem Oshman
Host: Chen Avin

Podcast: Play in new window | Download

New Challenges and Algebraic Topology

Maurice Herlihy

Posted on by
Reply

Maurice Herlihy discusses his view on the challenges distributed computing faces in the future, describes some of his work on programming abstractions and how he uses algebraic topology as a tool to reason about distributed protocols.

Guest: Maurice Herlihy
Host: Zvi Lotker and Yvonne-Anne Pignolet

Podcast: Play in new window | Download