Multi-version Coding and Shared Memory Emulation
summary
Compares ABD replication to a formal multiversion coding model with n servers, V versions, C connectivity and shows coding must store multiple versioned symbols because decoders require enough same-timestamp fragments (example: need 4 matching fragments so quorums intersect in 4). Presents a simple partitioning code and an information‑theoretic lower bound that makes storage scale with concurrency and proves the achievable scheme is near‑optimal (up to about a factor-two optimal gap).
AI-written summary · about
chapters (14)
- 0:00Multi-version coding and Shared Memory Emulation
- 2:35Shared Memory Emulation in Distributed Computing
- 4:49Distributed Storage Model
- 8:10Requirements
- 8:20Atomic Consistency
- 13:16The ABD algorithm (sketch)
- 15:29Erasure Coded Shared Memory
- 16:18Coded Shared Memory - Quorum set up
- 17:09Coded Shared Memory - Why is it challenging?
- 19:58Solutions to erasure coding based atomic shared memory
- 24:22Solution 1: Replication
- 24:46Solution 2: MDS code
- 26:07Achievability
- 27:10Converse: v=2
related talks
01h 14mErasure Coding at Scale
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
51mConvertible codes: Adaptive coding for large-scale data storage
43mCoded matrix computation: numerical stability, partial stragglers and sparse input matrices
57mCoding for Interactive Communication
18mDistributed Causal Memory for Higher-Order Distributed Separation Logic
20mImplementability of Global Distributed Protocols Modulo Network Architectures
10mRevisiting Network Coding for Warm Blob Storage