Distributed Systems Cheatsheet

Cheatsheet Content

Distributed File & Naming Systems NFS (Network File System): A distributed file system protocol allowing a user on a client computer to access files over a computer network much like local storage is accessed. AFS (Andrew File System): A distributed networked file system that uses a set of trusted servers to present a homogeneous, location-transparent file name space to all the client workstations. DNS (Domain Name System): A hierarchical and decentralized naming system for computers, services, or other resources connected to the Internet or a private network. It translates domain names to IP addresses. File System Consistency: Ensures that the file system metadata (e.g., directory structure, file sizes) accurately reflects the actual state of the data blocks on disk, especially after crashes or concurrent access. Naming Resolution: The process of translating a human-readable name into a machine-readable address or identifier within a distributed system. Time, Coordination, Agreement & Transactions Logical Clocks: Mechanisms (e.g., Lamport timestamps, Vector clocks) used in distributed systems to order events without relying on synchronized physical clocks, capturing causality. Lamport Timestamps: A scalar value assigned to events; if $a \to b$ (a causally precedes b), then $L(a) Vector Clocks: A vector of integers, one for each process, used to detect causality violations and concurrent events. Snapshots (Global State): A consistent recording of the state of all processes and communication channels in a distributed system at a particular point in time, often used for debugging or checkpointing. Consensus Protocols: Algorithms that allow a group of distributed processes to agree on a single data value, even in the presence of failures. Examples: Paxos, Raft. 2PC (Two-Phase Commit): A distributed algorithm that ensures all participating nodes in a distributed transaction either commit or abort the transaction. Phase 1 (Commit-request or Vote phase): Coordinator sends a prepare message. Participants respond with a vote (commit/abort). Phase 2 (Commit or Rollback phase): If all vote commit, coordinator sends commit. Otherwise, coordinator sends abort. 3PC (Three-Phase Commit): An extension of 2PC designed to be fault-tolerant in the case of a coordinator failure, by adding a "pre-commit" phase to remove blocking situations. Phase 1 (CanCommit?): Coordinator sends "CanCommit?" message. Participants respond "Yes" if ready. Phase 2 (PreCommit): If all respond "Yes", coordinator sends "PreCommit". Participants acknowledge and prepare to commit. Phase 3 (DoCommit): If all acknowledge "PreCommit", coordinator sends "DoCommit". Participants commit and acknowledge.