Distributed systems

Distributed systems

1. Basic tasks

   • Storage
   • Computation

2. Goals

   • Scalability
   • Performance
   • Latency
   • Availability
   • Fault tolerance

3. Constraints

   • Number of nodes
   • Distance between nodes

4. Abstractions and models

   • System model (asynchronous / synchronous)
   • Failure model (crash-fail, partitions, Byzantine)
   • Consistency model (strong, eventual)

5. Design techniques

   • Partitioning
   • Replication

6. System model

   • Nodes
     • execute a program
     • store data into volatile/stable state memory
     • a clock (accurate or not)
   • Communication links
   • Timing / ordering
     • Synchronous system model
       • Processes execute in lock-step; there is a known upper bound on message transmission delay; each process has an accurate clock
     • Asynchronous system model
       • No timing assumptions - e.g. processes execute at independent rates; there is no bound on message transmission delay; useful clocks do not exist
   • The consensus problem
     • Several computers (or nodes) achieve consensus if they all agree on some value.
     • Agreement
       • Every correct process must agree on the same value.
     • Integrity
       • Every correct process decides at most one value, and if it decides some value, then it must have been proposed by some process.
     • Termination
       • All processes eventually reach a decision
     • Validity
       • If all correct processes propose the same value V, then all correct processes decide V.
     • FLP impossibility result
       • there does not exist a (deterministic) algorithm for the consensus problem in an asynchronous system subject to failures, even if messages can never be lost, at most one process may fail, and it can only fail by crashing (stopping executing)
     • The CAP theorem
       • The theorem states that of these three properties only two can be satisfied simultaneously.
       • Consistency
         • all nodes see the same data at the same time
         • Strong consistency models
           • capable of maintaining a single copy
           • Linearizable consistency
           • Sequential consistency
         • Weak consistency models
           • Client-centric consistency models
           • Causal consistency
           • Eventual consistency
       • Availability
         • node failures do not prevent survivors from continuing to operate
       • Partition tolerance
         • the system continues to operate despite message loss due to network and/or node failure