Impacts of Asynchrony on Epidemic-Style Aggregation Protocols

The large scale and dynamic nature of a distributed system makes it difficult to collect the attributes of the individual nodes in the network. In these systems, often an aggregate (e.g. AVG, COUNT, MIN, MAX, SUM etc) of these attributes is adequate. Epidemic-style protocols are one of the popular approaches to estimate aggregates in such systems. In existing epidemic-style aggregation protocols the accuracy of the estimated aggregate at local nodes heavily depends upon synchronization of aggregation rounds. To enforce synchronization in these protocols, length of aggregation round should be long enough so that all the nodes in the system complete their aggregation information exchange. In this paper, we study the impacts of asynchrony in epidemic-style aggregation protocols. We present a simple asynchronous technique to estimate system aggregates in a distributed system. Based upon this technique, we analyze two popular existing epidemic-style aggregation protocols, Push-Pull and Push-Sum. Through detailed simulations, we evaluate accuracy and cost of asynchronous version of these protocols. We found that to obtain an estimate of the true system aggregate, aggregation protocols do not need to be synchronized and hence an efficient estimate can be obtained in lesser time.