Principles of Distributed Systems
Lectures, Wednesday 12:20 - 13:50, S6, Malá Strana, 2025
To be updated
Contact
- Office: Room S203, 2nd floor
-
Mattermost: ulita.ms.mff.cuni.cz/mattermost
- Invite link in SIS/notice-board
- Channel:
2526/nswi035-distrib-en - DM:
@faltin.tomas
- Email: tomas.faltin@matfyz.cuni.cz
Recommended Books
- Van Steen, Tanenbaum - Distributed Systems (Free download)
- A.D. Kshemkalyani, M. Singhal - Distributed Computing, Principles, Algorithms, and Systems
- Chow, Johnson - Distributed Operating Systems & Algorithms
- Antonopoulos - Mastering Bitcoin, Mastering Lightning Network
- Santoro - Design and Analysis of Distributed Algorithms
- Mullender - Distributed Systems
- Wu - Distributed System Design
Lecture Schedule
| Lab | Date | Lecture | Slides | Study |
|---|---|---|---|---|
| 01 | 01.10. |  |
1, 2.1–2.3 | |
| 02 | 08.10. | |
4.2-4.4, 8.3, 8.4 | |
| 03 | 15.10. |  |
Home study | 5.1-5.6 |
| 04 | 22.10. | |
Home study | 7.2, 7.5 |
| 05 | 29.10. | |
slides.04: pages 13-50, slides.08 pages 67-76, slides.05: pages 1-21 | — |
| 06 | 05.11. | |
slides.05: pages 22-88 | 7.3, 7.4, 2.4 |
| 07 | 12.11. |
(Dean’s day) |
— | 8.1, 8.2, 8.5 |
| 08 | 19.11. | |
— | — |
| 09 | 26.11. | |
8.2, 8.5 | — |
| 10 | 03.12. | |
pages: 107-126 | — |
| 11 | 10.12. | |
pages: 46-64 | — |
| 12 | 17.12. | |
pages: 88-105 - Vector clock, Trans, Transis, Vsync/ISIS, Blockchain | |
| 13 | 07.01. | |
pages: 237-270 - CRDT |
Syllabus
Most topics in the syllabus are covered in Distributed Systems. The remainder is addressed in the lecture slides and supplementary readings. If anything is unclear or you notice a topic missing, please let me know.
Distributed Systems - Van Steen, Tanenbaum
| Module | Topic | Key Concepts/Protocols/Algorithms |
|---|---|---|
| 1. Introduction | (skim through entire chapter) | Distributed vs. Decentralized systems, Resource Sharing, Design Goals (Openness, Dependability, Security, Scalability), Distribution Transparency (Access, Location, Concurrency, Failure, Migration, Relocation, Replication), Partial Failure, Scaling Techniques (Partitioning, Replication), Leslie Lamport’s definition, Lack of trust (relevance for decentralized systems). |
| 2. Architectures | [2.1] Architectural styles | Layered Architectures, Service-Oriented Architecture (SOA), RESTful Architecture, Microservices, Shared Data Space, Linda tuple spaces. |
| [2.2] Middleware and distributed systems | Middleware Layer, ZeroMQ, AMQP (Advanced Message Queuing Protocol). | |
| [2.3] Layered-system architectures | Client-Server Architecture, Multitiered Architectures, Thin Client. | |
| [2.4] Symmetrically distributed system architectures | Peer-to-Peer (P2P), Overlay Network, Distributed Hash Tables (DHT), Chord system, Flooding, Random Walk. | |
| [2.5] Hybrid systems architectures | Cloud Computing, Infrastructure-as-a-Service (IaaS), Platform-as-a-Service (PaaS), Blockchain architectures | |
| 4. Communication | [4.2] RPC | Remote Procedure Call (RPC), Marshaling, Interface Definition Language (IDL), Parameter passing (copy/restore), RPC semantics (at-least-once, at-most-once), Orphans, Orphan extermination, Reincarnation, Expiration. |
| [4.4] Multicast communication | Application-level multicasting, Flooding, Gossip-based Data Dissemination (Epidemic protocols), Epidemic models, Anti-entropy. | |
| 5. Coordination | [5.1] Clock synchronization | Physical clocks, NTP, Reference Broadcast Synchronization (RBS), Coordinated Universal Time (UTC). |
| [5.2] Logical clocks | Logical Clocks, Causal Dependency, Lamport’s Logical Clocks (Timestamp), Vector Clocks, Totally Ordered Multicasting. | |
| [5.3] Mutual exclusion | Centralized Algorithm (Sequencer), Ricart-Agrawala Algorithm,Token-Ring Algorithm, Decentralized algorithm, Deadlock, ZooKeeper Locking. | |
| [5.4] Election algorithms - RAFT | Bully Algorithm, Ring Algorithm, RAFT Leader Election, Proof of Work (PoW), Proof of Stake (PoS) | |
| 6. Naming | [6.2.3] Distributed hash tables | Flat Naming, Distributed Hash Tables (DHT), Chord, Forwarding Pointers, Self-Certifying Name. |
| 7. Consistency and Replication | [7.2] Data-centric consistency models | Sequential Consistency, Causal Consistency, Entry Consistency, (Strong) Eventual Consistency, Weak Consistency, Continuous Consistency (Conit), Distributed Shared Memory (DSM), Conflict-Free Replicated Data Type (CRDT), Coherence Model. |
| [7.4] Replica management | Replica placement, Content Distribution Networks (CDN), Permanent/Server-initiated/Client-initiated replicas, Push-based vs. Pull-based Protocols, Content-blind caching. | |
| 8. Fault tolerance | [8.1] Introduction | Failure Models (Crash, Omission, Timing, Arbitrary/Byzantine Failures), Redundancy (Information, Physical, Time), Dependability (Availability, Reliability, Safety). |
| [8.2] Process resilience (Paxos, RAFT, byzantine agreement problem) | Process Groups, Consensus, Paxos (Proposer, Acceptor, Learner), RAFT (Term, Log Replication, AppendEntries), Byzantine Agreement, Practical Byzantine Fault Tolerance (PBFT), Consensus in blockchain systems, CAP Theorem. | |
| [8.3] Reliable client-server communication | Reliable RPC Semantics, Failure detection, At-least-once semantics, At-most-once semantics, Idempotent operation. | |
| [8.4] Reliable group communication (virtual synchrony) | Reliable multicasting, Feedback Implosion, Atomic multicast, Causally ordered multicast, Virtual Synchrony. | |
| [8.5] Distributed commit | Distributed Commit, Two-Phase Commit (2PC), Three-Phase Commit (3PC). | |
| [8.6.2] Checkpointing | Checkpointing, distributed snapshot, independent chackpointing |
Remaining Topics
- Chow, Johnson - Distributed Operating Systems & Algorithms
- PDS-en.pptx - Slides with translated selected topics (topics covered by the book are incrementally translated from czech)
- pds-btc.pptx - Slides on blockchain
| Topic | Concepts/Protocols/Algorithms | Pages | Addition Sources |
|---|---|---|---|
| Mutual exclusion | Maekawa’s Algorithm, Ricard-Agrawala, Naive Voting, Maekawa voting | 46-64 | Maekawa’s Algorithm, wiki |
| Election algorithms | Invitation Algorithm, Ring Algorithms: Chang & Roberts, Hirschback & Sinclair | 65-75 | |
| Distributed paging | Distributed paging with sequestion or causal consistency | 203-209 | Understand single process Memory paging, Virtual memory, … |
| Virtual synchrony | Trans Algorithm, Transis algorithm, VSync/ISIS. | 87-105 | Transis, ISIS+Transis |
| Global state detection | Chandy-Lamport Marker Algorithm (for distributed snapshots/consistent global state), Diffusing Computation (for deadlock/termination detection). | 114-128 | slides |
| Termination detection | Dijsktra-Scholten Algorithm, Huang’s Algorithm | 108-113 | wiki-DS, wiki-Huang |
| Deadlock Detection | TWFG (Transaction-Wait-For Graph), Centralized algorithms: Ho-Ramamoorthy algorith, Path-pushing algorithms: Menasce-Muntz, Obermarck, Edge-chaising algorithms: Mitchell-Merritt, Chandy-Misra-Haas, Diffusing computation: Bracha-Toueg | 216-223 | Edge-chasing Chandy-Misra-Haas, DistrDeadlocks.pdf |
| Blockchain | transactions, UTXO, signatures, mining, consensus, payment channels, lightning network | pds-btc: full | |
| Distributed data structures | CRDT | 237-270 | wiki |