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.44× better accuracy on average) in all three applications. The source codes of MinMax Sampling are available at Github [1].