Service Rates Of Mds Codes & Fractional Matchings In Quasi-Uniform Hypergraphs
summary
Shows that the service-rate region of an [n,k] code equals a linear-image of the fractional-matching polytope of a hypergraph built from the generator matrix and fully characterizes that region for a broad class of MDS codes whose hypergraphs are k,2-quasi-uniform. Tools are hypergraph fractional matching, LP duality and the matching/vertex-cover bounds, plus a greedy-matching reduction that preserves achievable rate points. Examples give concrete numbers (e.g., achievable per-object rates like 2.5 and total-sum bounds like 3) and simulations compare code layouts (replication vs coded placements) showing the method predicts which layouts actually improve service.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:03Distributed service systems
- 6:05Modeling storage with MDS codes
- 13:44Hypergraphs for recovery sets
- 19:11Fractional matchings and service rates
- 26:54Service polytopes for Reed-Solomon
- 33:02Storage schemes for request patterns
- 38:05Replication versus coding
- 42:10Queue stability and future work
- 45:24Open problems and Q&A
related talks
10mQuery, Communication and Discrepancy
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
46mDistributed Graph Techniques in the MPC Model
20mCounting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
27mA Student's View of Locally Repairable Codes