Convergence Detection in Epidemic Aggregation

Abstract

Emerging challenges in ubiquitous networks and computing include the ability to extract useful information from a vast amount of data which are intrinsically distributed. Epidemic protocols are a bio-inspired approach that provide a communication and computation paradigm for large and extreme-scale networked systems. These protocols are based on randomised communication which provides robustness scalability and probabilistic guarantees on convergence speed and accuracy. This work investigates the convergence detection problem in epidemic aggregation which is critical to minimise the execution time for a given approximation error of the estimated aggregate. Global and local convergence criteria are presented and compared. The experimental analysis shows that a local convergence criterion can be adopted to minimise and adapt the number of cycles in epidemic aggregation protocols.