ARRG

Abstract

Gossiping is an effective way of disseminating information in large dynamic systems. Until now, most gossiping algorithms have been designed and evaluated using simulations. However, these algorithms often cannot cope with several real-world problems that tend to be overlooked in simulations, such as node failures, message loss, non-atomicity ofinformation exchange, and firewalls. We explore the problems in designing and applying gossiping algorithms in real systems. Next to identifying the most prominent real-world problems and their current solutions, we introduce Actualized Robust Random Gossiping (ARRG), an algorithm specifically designed to take all of these real-world problems into account simultaneously. To address network connectivity problems such as firewalls we introduce a novel technique, the Fallback Cache. This cache can be applied to existing gossiping algorithms to improve their resilience against connectivity problems. We introduce a new metric, Perceived Network Size to measure a gossiping algorithm's effectiveness. In contrast to existing metrics, our new metric does not require global knowledge. Evaluation of ARRG and the Fallback Cache in a number of realistic scenarios shows that the proposed techniques significantly improve the performance of gossiping algorithms in networks with limited connectivity. Even in pathological situations, with 50% message loss and with 80% of the nodes behind a NAT, ARRG continues to work well. Existing algorithms fail in these circumstances.