Byzantine Fault Tolerance

Formal Models

Events and Links

Safety and liveness of distributed protocols

Failure Detectors

Reliable Broadcast Primitives

Causal Broadcast

Shared Memory/Data Consistency

Impossibility of Consensus

Consensus Algorithms

Probabilistic Consensus

Fast Consensus

Non-blocking Atomic Commit

Terminating Reliable Broadcast (TRB)

Consensus

Paxos

Replicated State Machines and Reconfiguration

CS 294-91 Distributed Computing UC Berkeley Winter 2013 This course provides basic theoretical and practical foundations of distributed systems. Students learn about system models, safety and liveness of protocols, different failure models, reliable group communication abstractions, and more. It utilizes a textbook and additional research paper-based lectures. In the past decade evermore applications and services, which previously were running on local PCs, have moved to the Internet, in data centers, accessible through the Web. This puts distributed systems at the center of many of s application architectures. Distributed systems (or distributed computing) concerns systems in which many nodes (machines) solve a common problem, using message passing over a network that connects those nodes. The aim of this course is to establish familiarity with the basic theoretical and practical foundations of distributed systems.

Distributed computing is challenging due to two fundamental problems: (i) partial-failures, and (ii) asynchrony. Partial failures means that parts of the system (network or machines) can be faulty, but it is desirable for the rest of the system to function correctly. Asynchrony is due to the variance in the time it takes to send messages between computers and the operating speed of different computers. It is therefore desirable to make the system function correctly while events are happening asynchronously.

Over the years, many recurring problems have been studied with respect to the two aforementioned challenges. Furthermore, many abstractions have been proposed that simplify dealing with these two challenges when building distributed systems. In this course we will study many of these problems and abstractions, including the following: today

- Models of distributed systems
- Safety and liveness of distributed protocols
- Different failure models for distributed systems (fail-stop, fail-noisy, Byzantine)
- Reliable group communication abstractions (reliable, atomic, etc)
- Shared memory and consistency models (linearizable, regular etc)
- Failure detectors and their relationship and implementation in real systems
- Impossibility of Consensus
- Consensus and Paxos
- Replicated State Machines and Reconfiguration
- Byzantine Fault Tolerance   We will loosely follow the following textbook, but also have additional lectures based on research papers:

[Introduction to Reliable and Secure Distributed Programming](http://www.amazon.com/Introduction-Reliable-Secure-Distributed-Programming/dp/3642152597), C. Cachin, R. Guerraoui, L. Rodrigues, Springer, 2011.

CS 294-91 Distributed Computing

Parallelism and Distributed Systems

The Internet

Classical synchronization

Concurrency

Time Synchronization

Distributed Mutual Exclusion

Remote Procedure Call (RPC)

Distributed File Systems

Concurrency Control

Logging and Crash Recovery

Fault Tolerance

RAID (Redundant Array of Inexpensive Disks)

Distributed Replication

Distributed Databases

Spanner

Google File System (GFS)

Apache Hadoop Distributed File System (HDFS)

Data-Intensive Computing

MapReduce

Hadoop

In-memory cluster compute

Apache Spark

Distributed ML

Internet Content Delivery

DNS (Domain Name System)

Content Delivery Network (CDN)

Publish-Subscribe

Kafka

Virtualization

3-tier Web Service Architecture

Security Protocols

P2P Network

Distributed Ledgers

Blockchain

 15-440 Distributed Systems Carnegie Mellon University Fall 2020 A course offering both theoretical understanding and practical experience in distributed systems. Key themes include concurrency, scheduling, network communication, and security. Real-world protocols and paradigms like distributed filesystems, RPC, MapReduce are studied. Course utilizes C and Go programming languages. Most software is now distributed in some sense. This course is meant to serve as an introduction to distributed systems, emphasizing techniques for creating functional, usable, and high-performance distributed systems.

This course aims to: (1) provide students with an understanding of the principles and techniques behind the design of distributed systems, such as locking, concurrency, scheduling, and communication across the network. (2) provide students with practical experience designing, implementing, and debugging real distributed systems.

Major themes covered in this course include scarcity, scheduling, concurrency and concurrent programming, naming, abstraction and modularity, imperfect communication and other types of failure, protection from accidental and malicious harm, optimism, and the use of instrumentation and monitoring and debugging tools in problem solving. As the creation and management of software systems is a fundamental goal of any undergraduate systems course, students will design, implement, and debug large programming projects. After this course, students will have learned to…

- Implement and structure distributed systems programs.
- Write programs that can interoperate using well-defined protocols.
- Debug highly concurrent code that spans multiple programs running on multiple cores and machines.
- Reason about distributed algorithms for locking, synchronization and concurrency, scheduling, and replication.
- Use standard network communication primitives such as UDP and TCP.
- Understand the general properties of networked communication necessary for distributed systems programming in clusters and on the Internet.
- Employ and create common paradigms for easing the task of distributed systems programming, such as distributed filesystems, RPC, and MapReduce. Be able to clearly elucidate their benefits, drawbacks, and limitations.
- Identify the security challenges faced by distributed systems programs.
- Be able to select appropriate security solutions to meet the needs of commonly encountered distributed programming scenarios. Because this course has a big project component, you must be proficient in C and programming on UNIX systems. We will use the [Go programming language](https://golang.org/) throughout the term. It is required that you have taken 15-213 and gotten a “C-“ or higher since many of the programming skills you will need are taught in that course. **However, if you received a C in 15-213, you must meet with your academic advisor to discuss your background before taking 15-440/640, perhaps taking an additional course to sharpen your systems skills. Your advisor must email us approval and an explanation of why you have sufficient background to take 15-440/640.** 

 15-440 Distributed Systems

Byzantine fault

Byzantine Fault Tolerance

2 courses cover this concept

CS 294-91 Distributed Computing

15-440 Distributed Systems