Perturbation-resilient sets for dynamic service balancing

A combinatorial trade is a pair of sets of blocks of elements that can be exchanged while preserving relevant subset intersection constraints. The class of balanced and swap-robust minimal trades was proposed in Pan et al. (in: 2022 IEEE International Symposium on Information Theory (ISIT), IEEE, pp 2385–2390, 2022) for exchanging blocks of data chunks stored on distributed storage systems in an access- and load-balanced manner. More precisely, data chunks in the trades of interest are labeled by popularity ranks and the blocks are required to have both balanced overall popularity and stability properties with respect to swaps in chunk popularities. The original construction of such trades relied on computer search and paired balanced sets obtained through iterative combining of smaller sets that have provable stability guarantees. To reduce the substantial gap between the results of prior approaches and the known theoretical lower bound, we present new analytical upper and lower bounds on the minimal disbalance of blocks introduced by limited-magnitude popularity ranking swaps. Our constructive and near-optimal approach relies on pairs of graphs whose vertices are two balanced sets with edges/arcs that capture the balance and potential balance changes induced by limited-magnitude popularity swaps. In particular, we show that if we start with carefully selected balanced trades and limit the magnitude of rank swaps to one, the new upper and lower bound on the maximum block disbalance caused by a swap only differ by a factor of 1.07. We also extend these results for larger popularity swap magnitudes.