Consistent Hashing and Random Trees: Distributed…

Consistent Hashing and Random Trees asks how a distributed cache can absorb membership changes and flash crowds without throwing away nearly every placement decision. Read it to see how stable item and cache positions localize reassignment, how monotonicity limits movement, and how a different random cache tree for each page spreads hot demand.

Reading focus: Why a conventional hash whose range depends on the cache count can remap almost every object when one cache joins or leaves. How the paper maps items and replicated cache points to a fixed unit interval, then uses monotonicity to prevent movement between two old caches. How balance, spread, load, random cache trees, and explicit model assumptions qualify the paper's theoretical hot-spot guarantees.

STOC 1997. David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. 35 min read, easy difficulty.