TY - JOUR

T1 - Convergence of periodic gossiping algorithms

AU - Anderson, Brian D.O.

AU - Yu, Changbin

AU - Morse, A. Stephen

PY - 2010

Y1 - 2010

N2 - In deterministic gossiping, pairs of nodes in a network holding in general different values of a variable share information with each other and set the new value of the variable at each node to the average of the previous values. This occurs by cycling, sometimes periodically, through a designated sequence of nodes. There is an associated undirected graph, whose vertices are defined by the nodes and whose edges are defined by the node pairs which gossip over the cycle. Provided this graph is connected, deterministic gossiping asymptotically determines the average value of the initial values of the variables across all the nodes. The main result of the paper is to show that for the case when the graph is a tree, all periodic gossiping sequences including all edges of the tree just once actually have the same rate of convergence. The relation between convergence rate and topology of the tree is also considered.

AB - In deterministic gossiping, pairs of nodes in a network holding in general different values of a variable share information with each other and set the new value of the variable at each node to the average of the previous values. This occurs by cycling, sometimes periodically, through a designated sequence of nodes. There is an associated undirected graph, whose vertices are defined by the nodes and whose edges are defined by the node pairs which gossip over the cycle. Provided this graph is connected, deterministic gossiping asymptotically determines the average value of the initial values of the variables across all the nodes. The main result of the paper is to show that for the case when the graph is a tree, all periodic gossiping sequences including all edges of the tree just once actually have the same rate of convergence. The relation between convergence rate and topology of the tree is also considered.

KW - Gossiping algorithms

KW - Graphs

KW - Multi-agent systems

UR - http://www.scopus.com/inward/record.url?scp=77950211376&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-93918-4_12

DO - 10.1007/978-3-540-93918-4_12

M3 - Article

SN - 0170-8643

VL - 398

SP - 127

EP - 138

JO - Lecture Notes in Control and Information Sciences

JF - Lecture Notes in Control and Information Sciences

ER -