Peter Van Roy

There are three certainties in life, death, taxes, and node failures in distributed systems.  This tutorial will explain some useful but less understood concepts and techniques for designing distributed systems.  The tutorial is not intended to be exhaustive but to improve your knowledge and be entertaining.  I will first go over some of the basic concepts and explain what they are all about.  Then I will present several important problems: replicated data structures, laws of large systems, how to use failure, and self management.  Example systems will be taken from projects that I have worked in.  Prerequisite for this tutorial is some modest experience with concurrent and distributed programming, in particular experience with Erlang will help you get the most from this tutorial.

EXPERTISE

Intermediate

COURSE DURATION

3h30 minutes

• Basic concepts.  We will present partially synchronous systems, the Internet, and eventually perfect failure detectors.  These concepts are ubiquitous but are not always well understood.  We will explain causality and when to use it and not use it.  We will talk about time-outs inside large systems and how to use them correctly.
• Replicated data structures.  An important distributed pattern is the consistent replicated data structure.  We will talk about two important techniques for implementing such: the RSM (Replicated State Machine), which uses consensus to achieve consistency, and the CRDT (Conflict-free Replicated Data Type), which uses clever mathematics to achieve consistency without needing consensus.  As part of the presentation on CRDTs, we will explain different kinds of consistency, including eventual consistency and convergent consistency, and when they are useful.

• Laws of large systems.  Large system design is a general discipline that is especially useful for distributed systems.  We will talk about the CAP theorem and how to use it as a system design tool.  We will talk about Buridan’s theorem and its consequences for big systems.  We will talk about the induction fallacy, where relying on induction gives exactly the opposite effect to the desired result.  We will introduce our good friend Dijkstra’s demon.  We will present the next exponential wave, Internet of Things, and give some ideas on how to ride it.
• Failure is good.  Failure is very familiar to Erlang programmers.  Failure is quite normal, and is even good.  In large systems, if there are thousands of nodes, then there will always be failures.  We will explain how to build systems that survive and even thrive (improve) with failures.  Failures allow to continually renew the system, which is an approach that has been used by biological systems since the beginning of life on Earth, and which is especially useful in distributed systems.  We will present software rejuvenation as one technique that takes advantage of failure.
• Self management.  Large systems must be able to manage themselves.  We will talk about the two basic approaches to self management, namely control-oriented autonomic computing and data-oriented autonomic computing.  We will give a general approach for control autonomy called WIFS (weakly interacting feedback structures).  We will give a general approach for data autonomy called LiRA (LightKone Reference Architecture) and its two data management principles.  Both data and control autonomy are important; different parts of a large system may use one or the other or both together.  We will also present hybrid gossip, which is a sweet spot that combines the advantage of classical distributed algorithms (efficiency) with the advantage of gossip algorithms (resilience).