Back to index

How Useful is Old Information?

Michael Mitzenmacher, UCB/DEC SRC

One-line summary: For systems relying on imperfect/stale/periodic load balancing info to make scheduling decisions, "deterministic" heuristics that choose the lightest loaded server do poorly (even for "continuously updated but stale" load info), but a small amount of randomness (e.g. choosing the lighter loaded of 2 servers determined uniformly at random) suffices to break the symmetry and give performance comparable to that possible with perfect information.

Overview/Main Points


Direct relevance to TranSend and a variety of similar systems that rely on soft/stale (BASE) state for load balancing.


Back to index