In peer-to-peer networks, mobile ad-hoc networks and wireless sensor networks it can be useful, at run time, to reactively agree over choices that cannot be taken at design time: global consensus over one choice among a set of possible predefined alternatives, can emerge from the self-organization of a population of distributed agents connected through some communication network and interacting only locally, by means of a gossiping based information dissemination. However the standard gossiping used in many overlay networks, represented by a short-memory Self-Avoiding Random Walk, is very sensitive to topological bottlenecks: as a consequence different areas of an unstructured network can settle into different local consensus states. In this paper we study the performance of a class of gossiping algorithms, based on Neighbor Avoiding Random walks, that improve the mutual reachability of any pair of nodes in an unstructured network of arbitrary topology, so that each agent can potentially disseminate its own state more uniformly, so as to favor the attainment of global consensus.
Gianini, G., Damiani, E., Lena Cota, G., Danielius, P. (2010). Gossiping solutions for distributed consensus on unstructured overlays. In 4th IEEE International Conference on Digital Ecosystems and Technologies - Conference Proceedings of IEEE-DEST 2010, DEST 2010 (pp.246-251). IEEE [10.1109/DEST.2010.5610638].
Gossiping solutions for distributed consensus on unstructured overlays
Gianini, G;
2010
Abstract
In peer-to-peer networks, mobile ad-hoc networks and wireless sensor networks it can be useful, at run time, to reactively agree over choices that cannot be taken at design time: global consensus over one choice among a set of possible predefined alternatives, can emerge from the self-organization of a population of distributed agents connected through some communication network and interacting only locally, by means of a gossiping based information dissemination. However the standard gossiping used in many overlay networks, represented by a short-memory Self-Avoiding Random Walk, is very sensitive to topological bottlenecks: as a consequence different areas of an unstructured network can settle into different local consensus states. In this paper we study the performance of a class of gossiping algorithms, based on Neighbor Avoiding Random walks, that improve the mutual reachability of any pair of nodes in an unstructured network of arbitrary topology, so that each agent can potentially disseminate its own state more uniformly, so as to favor the attainment of global consensus.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
