Comment by dahart
2 years ago
The most interesting tidbit, I think, is cut off from the right side of the plot -- eventually with enough delay, 1 random choice is the winner, for exactly the same reason that 3 random choices wins for small delay, and 2 random choices wins for medium delay.
I kinda wonder now if the crossover points between best, 3, 2, and 1 are equidistant on a log-scale plot. If I squint a little, I could maybe see 4, 16, and 64 being the approximate crossover points, especially if there was a little less noise.
Yes, it's super interesting when systems move into the regime where stale information becomes worse than no information at all. Part of what makes best-of-2 interesting is how long it resists falling into this pit, but it does eventually happen (as, I suspect, it must with any distributed placement/load balancing algorithm).