MinMax Sampling: A Near-optimal Global Summary for Aggregation in the Wide Area

Nowadays, wide-area data analyses are pervasive with emerging geo-distributed systems. These analyses often need to do the global aggregation in the wide area. Since scarce and variable WAN bandwidth may degrade the aggregation performance, it is highly desired to design a communication scheme for global aggregation in WAN. Unfortunately, no existing algorithm can meet the three design requirements of communication schemes: fast computation, adaptive transmission, and accurate aggregation. In this paper, we propose MinMax Sampling, a fast, adaptive, and accurate communication scheme for global aggregation in WAN. We first focus on the accuracy and design a scheme, namely MinMax(opt), to achieve optimal accuracy. However, MinMax(opt) does not meet the other two requirements: fast computation and adaptive transmission. Based on MinMax(opt), we propose MinMax(adp), which trades little accuracy for the other two requirements. We evaluate MinMax(adp) with three applications: federated learning, distributed state aggregation, and hierarchical aggregation. Our experimental results show that MinMax(adp) is superior to existing algorithms (8.44x better accuracy on average) in all three applications. The source codes of MinMax Sampling are available at Github [1].