From Classical to Blockchain Consensus: What are the Exact Algorithms?
Organizers: Y. Annie Liu and Scott D. Stoller
Computer Science Department, Stony Brook University
This tutorial will describe well-known algorithms for distributed consensus
problems, from classical consensus to blockchain consensus, and will
discuss exact algorithms that are high-level as in pseudocode and directly
executable at the same time. The tutorial consists of five parts:
- An introduction to different distributed consensus problems, from classical consensus and Byzantine consensus to blockchain consensus.
- An overview of well-known algorithms, from Paxos for classical consensus to the Bitcoin algorithm for blockchain consensus, including important variants such as Viewstamped Replication and Virtual Synchrony, as well as Proof-of-Stake vs. Proof-of-Work.
- An overview of a method and language, DistAlgo, for expressing distributed algorithms precisely at a high-level as pseudocode and having them directly executable at the same time.
- A study of exact algorithms expressed at a high level for the most extensively studied algorithm variants, including Lamport’s Paxos for classical consensus and Nakamoto’s Bitcoin algorithm for blockchain consensus.
- A demo of the direct execution of these exact algorithms by distributed processes.
Additional information and materials for the workshop will be made
available at http://darlab.cs.stonybrook.edu/consensus
Byzantine Fault Tolerant State Machine Replication in Any Programming Language
Organizer: Ethan Buchman
State machine replication is a fundamental primitive in fault tolerant distributed computing, but few production tools exist to support the replication of arbitrary state machines. The tools that do exist, like Apache Zookeeper, CoreOS’s etcd, and Hashicrop’s Consul, include an implementation of a consensus algorithm (eg. ZAB or Raft) for replication, and a service-discovery oriented key-value store as the state machine. While these tools can tolerate crash failures, they cannot tolerate malicious or adversarial (“Byzantine”) faults. We present Tendermint, a production-grade Byzantine Fault Tolerant State Machine Replication engine written in Go. Tendermint supports state machines replication for state machines written in any language by using a socket protocol to communicate between the state machine and the replication engine. Tendermint is being used on the public internet today to secure upwards of $1 Billion USD in value, with deployments supporting hundreds of nodes.
Central Control over Distributed Asynchronous Systems: A Tutorial on Software-Defined Networks and Consistent Network Updates
Organizer: Klaus-Tycho Foerster
University of Vienna
Presentation slides available here
This tutorial will give an introduction to a topic that lies at the intersection of distributed computing and networking, and combines asynchronous distributed systems with central control, namely consistent updates in Software-Defined Networks (SDNs). We will give an overview on current models and algorithms, but also selected related topics, in particular those of potential interest to the PODC community, showcasing avenues for further research.
In more detail, SDNs have been an intensively studied topic in networking over the last years, but much of its focus has been on (logical) central control, abstracting away most of its underlying foundation, namely that a network is still a distributed asynchronous system at its core. Summarized in a simplified way, SDNs come with the promise that the network state can be optimized and updated from a global point of view. However, such a simplification becomes especially problematic when consistency guarantees have to maintained. In asynchronous distributed systems, it is not possible to simultaneously change the state of all nodes, such a naive approach will lead to an inconsistent mix of old and new states, introducing e.g. forwarding loops. Notwithstanding, most approaches tackle these issues from the viewpoints of the networking/systems communities, and we believe could henceforth greatly benefit from connections to relevant works and (new) ideas stemming from the PODC community.
Specifying, Implementing, and Verifying Algorithms for Persistent Memory
Organizer: Wojciech Golab
University of Waterloo
High-density byte-addressable non-volatile memory became a reality earlier this year when Intel® launched the long-awaited Optane™ persistent memory module. This tutorial is intended for researchers interested in using Optane memory to construct fault-tolerant data structures that can maintain state consistently across power outages and system crashes without relying on conventional secondary storage. A number of practical and theoretical topics will be covered including hardware purchasing considerations, operating system and programming language support for persistent memory, correctness properties for fault-tolerant data structures, and techniques for verifying such correctness properties.