Exploring the interdisciplinary connections of gossip-based systems
Open Access
- 1 October 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGOPS Operating Systems Review
- Vol. 41 (5) , 51-60
Abstract
In recent years the labels "gossip" and "gossip-based" have been applied to an increasingly general class of algorithms, including approaches to information aggregation, overlay network management and clock synchronization. These algorithms are intuitively similar, irrespective of their purpose. Their distinctive features include relying on local information, being round-based and relatively simple, and having a bounded information transmission and processing complexity in each round. Our position is that this class can and should be significantly extended to involve algorithms from other disciplines that share the same or similar distinctive features, like certain parallel numerical algorithms, routing protocols, bio-inspired algorithms and cellular automata, to name but a few. Such a broader perspective would allow us to import knowledge and tools to design and understand gossip-based distributed systems, and we could also export accumulated knowledge to re-interpret some of the problems in other disciplines, such as vehicular traffic control. In this position paper we describe a number of areas that show parallels with gossip protocols. These example areas will hopefully serve as inspiration for future research. In addition, we believe that comparisons with other fields also helps clarify the definition of gossip protocols and represents a necessary first step towards an eventual formal definition.Keywords
This publication has 28 references indexed in Scilit:
- A hint-based probabilistic protocol for unicast communications in MANETsAd Hoc Networks, 2006
- SLACER: A Self-Organizing Protocol for Coordination in Peer-to-Peer NetworksIEEE Intelligent Systems, 2006
- Gossip-based aggregation in large dynamic networksACM Transactions on Computer Systems, 2005
- AstrolabeACM Transactions on Computer Systems, 2003
- Synchronous versus asynchronous updating in the “game of Life”Physical Review E, 1999
- Self-stabilizationACM Computing Surveys, 1993
- The self-organizing exploratory pattern of the argentine antJournal of Insect Behavior, 1990
- Optimal clock synchronizationJournal of the ACM, 1987
- A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radiusJournal of the ACM, 1986
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974