Request-based gossiping without deadlocks

DOI10.1016/J.AUTOMATICA.2018.03.001MaRDI QIDQ1797048zbMATH OpenOpenAlexWikidataFDO

Authors Ji Liu, Shaoshuai Mou, A. Stephen Morse, Brian D. O. Anderson, Changbin Yu

Publication date 17 October 2018

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.08463

Mathematics Subject Classification ID

Models of societies, social and urban evolution (91D10) Social networks; opinion dynamics (91D30) Communication networks in operations research (90B18) Decentralized systems (93A14) Discrete-time control/observation systems (93C55) Network protocols (68M12)

Abstract: By the distributed averaging problem is meant the problem of computing the average value of a set of numbers possessed by the agents in a distributed network using only communication between neighboring agents. Gossiping is a well-known approach to the problem which seeks to iteratively arrive at a solution by allowing each agent to interchange information with at most one neighbor at each iterative step. Crafting a gossiping protocol which accomplishes this is challenging because gossiping is an inherently collaborative process which can lead to deadlocks unless careful precautions are taken to ensure that it does not. Many gossiping protocols are request-based which means simply that a gossip between two agents will occur whenever one of the two agents accepts a request to gossip placed by the other. In this paper, we present three deterministic request-based protocols. We show by example that the first can deadlock. The second is guaranteed to avoid deadlocks and requires fewer transmissions per iteration than standard broadcast-based distributed averaging protocols by exploiting the idea of local ordering together with the notion of an agent's neighbor queue; the protocol requires the simplest queue updates, which provides an in-depth understanding of how local ordering and queue updates avoid deadlocks. It is shown that a third protocol which uses a slightly more complicated queue update rule can lead to significantly faster convergence; a worst case bound on convergence rate is provided.

Recommendations

• Convergence rate on periodic gossiping
• Convergence of periodic gossiping algorithms
• Analysis of accelerated gossip algorithms
• Gossip consensus algorithms via quantized communication
• Dynamic gossip

Cites work

• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
• Coordination of groups of mobile autonomous agents using nearest neighbor rules
• Fast linear iterations for distributed averaging
• Request-based gossiping without deadlocks

Cited in

(1)

• Request-based gossiping without deadlocks

This page was built for publication: Request-based gossiping without deadlocks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1797048)