Distributed systems

My projects.

I’ve completed a few projects in distributed systems.

• Go implementation of a full Nakamoto blockchain. [github]
• Rust PoC of Tendermint consensus. [github].
• Go PoC of Pod consensus. [github].
• Articles
  • Comparing IPFS and BitTorrent.
  • Google Bigtable as a B-Tree over networked nodes.
  • How does Tendermint consensus work?
• Talks
  • TikTok’s recommendation systems. Presented to distributed systems study group, April 2025. (slides).
  • Google File System. Presented to distributed systems study group, Sept 2024. (slides)

I’m also part of a really cool distributed systems reading group. We’ve done a bunch of sessions on different systems: GFS, Cassandra, Mystceti, TikTok.

Notes.

• Optimal piece size in BitTorrent

• Notes on BitTorrent DHT mutable torrents.

• Notes on Google Bigtable.

• Notes on proof-of-stake Ethereum and FLP impossibility, CAP theorem, BFT

• Notes on TLA

Papers.

• DHT’s
  • Kademlia: A Peer-to-peer Information System Based on the XOR Metric
  • Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
  • Dynamo: Amazon’s Highly Available Key-value Store
  • Sub-Second Lookups on a Large-Scale Kademlia-Based Overlay
• P2P.
  • IPFS
  • Incentives Build Robustness in BitTorrent
• Google search engine
  • The Anatomy of a Large-Scale Hypertextual Web Search Engine
  • The PageRank citation ranking
  • Building Large-Scale Internet Services
  • Storage Architecture and Challenges
  • Building Software Systems at Google and Lessons Learned
• Google
  • The Google File System
    • GFS evolution
    • Cluster-Level Storage @ Google
  • The Chubby lock service for loosely-coupled distributed systems
  • Bigtable: A Distributed Storage System for Structured Data
  • Megastore: Providing Scalable, Highly Available Storage for Interactive Services
  • MapReduce: Simplified Data Processing on Large Clusters
  • Spanner: Google’s Globally-Distributed Database
  • F1: A Distributed SQL Database That Scales
  • Large-scale cluster management at Google with Borg
• Amazon.
  • Building and operating a pretty big storage system called S3
• Misc papers.
  • FoundationDB: A Distributed Unbundled Transactional Key Value Store
  • Taming Consensus in the Wild (with the Shared Log Abstraction)
  • Amazon - The Distributed Computing Manifesto
• Resources.
  • Foundational distributed systems papers
  • Learning about distributed systems: where to start?
  • Designing Data Intensive Applications
  • Consistency Models
• Engineering.
  • The Tail at Scale
  • Microservices and the First Law of Distributed Objects
  • Fallacies of distributed computing
  • gRPC principles
  • The Law of Leaky Abstractions
  • Jane Street - State Machine Replication, and Why You Should Care with Doug Patti - OCaml compiled to FPGA’s, state machine architecture. Fascinating.

Concepts.

• Fallacies of distributed computing
• Databases
  • Log-structured merge trees (LSTM)
    • SSTable - sorted string table
    • Memtable - in-memory table, before they are flushed to disk as SSTable
  • B-Tree
  • B+-Tree
• Clocks
  • Wall clock
  • Logical clock
  • Vector clock
  • “in general, synchronized clocks can be used to avoid communication in a distributed system”

Database systems.

What Goes Around Comes Around… And Around…

Types of databases:

• MapReduce Systems
• Key-value Stores
• Document Databases
• Column Family / Wide-Column,
• Text Search Engines
• Array Databases
• Vector Databases
• Graph Databases

Consensus.

• CAP theorem
• FLP impossibility
• Fault Tolerance
  • Crash
  • Byzantine
    • Comes from Byzantine Generals paper.
    • Funny lore: this was originally called the Albanian Generals (and hence Albanian Fault Tolerance) before they realised that might be a bit touchy..
• Concurrent data structures.
  • conflict-free replicated data types (CRDT’s)
  • operational transform (OT)
• Protocols
  • Paxos
    • Used everywhere at Google.
  • Raft
• Code
  • TLA specs for Raft, Tendermint, hybrid logical clocks

Concurrency.

• multi-version concurrency control

Sharding and scaling.

• Control plane vs. data plane.
• Dividing work into fixed-size units
  • GFS: chunks
  • Bigtable: key spans, tablet servers
• Stripes, replication groups, reed-solomun
  • idea: instead of replicating whole chunks on N nodes, replicate dynamic sized chunks using Reed-Solomun coding
  • used in S3
• Reliable system from unreliable parts:
  • Consensus (Paxos/Tendermint): failure detector (timeouts) + leader-based system from unreliable nodes

Networking.

• Random linear coding is quite interesting.
• Onion routing - used by Tor.

Study.

Systems I’m familiar with / a fan of:

• Bitcoin.
• Ethereum.
  • EVM.
• Tendermint.
• BitTorrent.
  • Comparing IPFS and BitTorrent
  • Mutable torrents
• Google
  • GFS.
  • Bigtable.
  • Chubby.
• Amazon.
  • S3.
• Facebook.
  • Glacier.
• TikTok.
  • Monolith.

Learn more.

• TLA+: Temporal Logic of Actions.
  • TLA+ is a language for formally modelling distributed systems.
  • Notes