Power-of-two Policies in Redundancy Systems: the Impact of Assignment Constraints

In classical power-of-two load balancing any server pair is sampled with equal probability. This does not cover practical settings with assignment constraints which force non-uniform server sampling. While intuition suggests that non-uniform sampling adversely impacts performance, this was only supported through simulations, and rigorous statements have remained elusive. Building on product-form distributions for redundancy systems, we prove the stochastic dominance of uniform sampling for a four-server system as well as arbitrary-size systems in light traffic.