Home // AP2PS 2011, The Third International Conference on Advances in P2P Systems // View article

Symmetric Push-Sum Protocol for Decentralised Aggregation

Authors:
Francesco Blasa
Simone Cafiero
Giancarlo Fortino
Giuseppe Di Fatta

Keywords: peer-to-peer computing; distributed aggregation algorithms; gossip protocols; extreme scale computing.

Abstract:
Gossip (or Epidemic) protocols have emerged as a communication and computation paradigm for large-scale networked systems. These protocols are based on randomised communication, which provides probabilistic guarantees on convergence speed and accuracy. They also provide robustness, scalability, computational and communication efficiency and high stability under disruption. This work presents a novel Gossip protocol named Symmetric Push-Sum Protocol for the computation of global aggregates (e.g., average) in decentralised and asynchronous systems. The proposed approach combines the simplicity of the push-based approach and the efficiency of the push-pull schemes. The push-pull schemes cannot be directly employed in asynchronous systems as they require synchronous paired communication operations to guarantee their accuracy. Although push schemes guarantee accuracy even with asynchronous communication, they suffer from a slower and unstable convergence. Symmetric Push- Sum Protocol does not require synchronous communication and achieves a convergence speed similar to the push-pull schemes, while keeping the accuracy stability of the push scheme. In the experimental analysis, we focus on computing the global average as an important class of node aggregation problems. The results have confirmed that the proposed method inherits the advantages of both other schemes and outperforms well-known state of the art protocols for decentralized Gossip-based aggregation.

Pages: 27 to 32

Copyright: Copyright (c) IARIA, 2011

Publication date: November 20, 2011

Published in: conference

ISBN: 978-1-61208-173-1

Location: Lisbon, Portugal

Dates: from November 20, 2011 to November 25, 2011