Randomization replaces coordination
Randomization can replace coordination.
What it is
Randomization law. Where a structure or system needs a global invariant, a random choice with good concentration properties gives the same expected behaviour with no coordinator. It is paid for in worst-case guarantees, and in a tail that only appears under adversarial or skewed input.
From Core Data Structures › Tries and skip lists
Work stealing is provably good. Randomized work stealing achieves time about T₁/p + O(T∞): the work-span bound within a constant factor, with no central coordinator and no global information. In many places across the platform randomization replaces coordination, and the evidence is empirical. Here there is a theorem. This is the principle randomization instead of coordination at its strongest.
From Execution Engine Runtime › Stealing and speculation
Retry storms. If every client uses the same backoff, the herd stays together and fails together. Jitter is not optional in backoff. Why, and why full jitter wins, is in Retry with exponential backoff and jitter.
From Data Movement › Rate limiting and pacing
Where it appears
In 8 mechanisms. Each says what the mechanism is about, then how this principle shows up there, in its own words.
- Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
Where a structure or system needs a global invariant, a random choice with good concentration properties gives the same expected behaviour with no coordinator.
Read it inTries, ART and skip lists
- Transactions & Concurrency Control
What happens when many users change the same data at the same time, and how do we keep the result correct?
And since the failure is contention rather than lack of capacity, the random waits must be decorrelated, or you rebuild the synchronized-retry stampede: every client waits the same time, then they all come back together.
Read it inRetry semantics and read-only transactionsDesign a commit
- Consistency & Isolation Models
When many users, many objects and many copies exist at once, which histories does the system promise never to show, and who writes the code for the histories it does show?
The tags are worth noticing: a random unique identifier standing in for a coordinated sequence number is randomization substituting for coordination, here inside a data type instead of a load balancer.
- Query Processing
Why can one question be answered by plans whose costs differ by a factor of ten thousand, and what does each operator force the engine to do?
This is randomization replaces coordination: a sample stands in for the exact global computation.
Read it inSkew: the assumption of uniformity, pricedA sort produces a property, not an answer
- Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
Randomness replaces coordination (no node needs to know when the others expire).
Read it inStampede: Little's Law as a count of duplicate workReuse distance and the miss-ratio curve
- Fault Tolerance & Delivery Semantics
What is the cheapest thing that can be safely done twice?
It replaces coordination: instead of the clients talking to each other to spread out, each one picks a random delay.
- Emergent Failure Dynamics
What happens when nothing is broken, every component is healthy, and the system's own response to stress makes the stress worse?
Isolation comes from combinatorics instead of from reservation.
Read it inShuffle shardingLeast-loaded routingThundering herd
- Scheduling & Workload Management
Which work runs now, which work waits, and who pays for the waiting?
So most of the value of a global view can be obtained from a sample of size 2.
Read it inThe four architectures
Related
Made on the same pages most often.