Convergence time evaluation of a gossip algorithm over signed graphs

Nguyen Thi Hoai Linh; Takayuki Wada; Izumi Masubuchi; Toru Asai; Yasumasa Fujisaki

doi:10.1109/ASCC.2015.7244534

Convergence time evaluation of a gossip algorithm over signed graphs

Nguyen Thi Hoai Linh, Takayuki Wada, Izumi Masubuchi, Toru Asai, Yasumasa Fujisaki

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Convergence time is investigated for a gossip algorithm over a connected signed graph, where each edge of the graph has positive or negative sign. The algorithm is an iterative procedure. At each time, (i) two nodes directly connected with an edge are chosen randomly, (ii) they exchange their values according to the sign of the edge, and (iii) they update their values as the average of each node's value and its received value. It is shown that the values of the algorithm always converge in mean square, where a bipartite consensus or a trivial consensus is achieved. A convergence time is defined as the smallest time such that it takes for the values of the algorithm to get within a given neighborhood of the consensus value with high probability, regardless of initial state. An upper bound of the convergence time is given in terms of a characteristic value of the given graph.

Original language	English
Title of host publication	2015 10th Asian Control Conference
Subtitle of host publication	Emerging Control Techniques for a Sustainable World, ASCC 2015
Editors	Hazlina Selamat, Hafiz Rashidi Haruna Ramli, Ahmad Athif Mohd Faudzi, Ribhan Zafira Abdul Rahman, Asnor Juraiza Ishak, Azura Che Soh, Siti Anom Ahmad
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781479978625
DOIs	https://doi.org/10.1109/ASCC.2015.7244534
Publication status	Published - Sept 8 2015
Externally published	Yes
Event	10th Asian Control Conference, ASCC 2015 - Kota Kinabalu, Malaysia Duration: May 31 2015 → Jun 3 2015

Publication series

Name	2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015

Other

Other	10th Asian Control Conference, ASCC 2015
Country/Territory	Malaysia
City	Kota Kinabalu
Period	5/31/15 → 6/3/15

All Science Journal Classification (ASJC) codes

Control and Systems Engineering

Access to Document

10.1109/ASCC.2015.7244534

Cite this

Linh, N. T. H., Wada, T., Masubuchi, I., Asai, T., & Fujisaki, Y. (2015). Convergence time evaluation of a gossip algorithm over signed graphs. In H. Selamat, H. R. H. Ramli, A. A. M. Faudzi, R. Z. A. Rahman, A. J. Ishak, A. C. Soh, & S. A. Ahmad (Eds.), 2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015 Article 7244534 (2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASCC.2015.7244534

Convergence time evaluation of a gossip algorithm over signed graphs. / Linh, Nguyen Thi Hoai; Wada, Takayuki; Masubuchi, Izumi et al.
2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015. ed. / Hazlina Selamat; Hafiz Rashidi Haruna Ramli; Ahmad Athif Mohd Faudzi; Ribhan Zafira Abdul Rahman; Asnor Juraiza Ishak; Azura Che Soh; Siti Anom Ahmad. Institute of Electrical and Electronics Engineers Inc., 2015. 7244534 (2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Linh, NTH, Wada, T, Masubuchi, I, Asai, T & Fujisaki, Y 2015, Convergence time evaluation of a gossip algorithm over signed graphs. in H Selamat, HRH Ramli, AAM Faudzi, RZA Rahman, AJ Ishak, AC Soh & SA Ahmad (eds), 2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015., 7244534, 2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015, Institute of Electrical and Electronics Engineers Inc., 10th Asian Control Conference, ASCC 2015, Kota Kinabalu, Malaysia, 5/31/15. https://doi.org/10.1109/ASCC.2015.7244534

Linh NTH, Wada T, Masubuchi I, Asai T, Fujisaki Y. Convergence time evaluation of a gossip algorithm over signed graphs. In Selamat H, Ramli HRH, Faudzi AAM, Rahman RZA, Ishak AJ, Soh AC, Ahmad SA, editors, 2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015. Institute of Electrical and Electronics Engineers Inc. 2015. 7244534. (2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015). doi: 10.1109/ASCC.2015.7244534

Linh, Nguyen Thi Hoai ; Wada, Takayuki ; Masubuchi, Izumi et al. / Convergence time evaluation of a gossip algorithm over signed graphs. 2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015. editor / Hazlina Selamat ; Hafiz Rashidi Haruna Ramli ; Ahmad Athif Mohd Faudzi ; Ribhan Zafira Abdul Rahman ; Asnor Juraiza Ishak ; Azura Che Soh ; Siti Anom Ahmad. Institute of Electrical and Electronics Engineers Inc., 2015. (2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015).

@inproceedings{4046ee72cb194aea8c17c03b8fdcaf99,

title = "Convergence time evaluation of a gossip algorithm over signed graphs",

abstract = "Convergence time is investigated for a gossip algorithm over a connected signed graph, where each edge of the graph has positive or negative sign. The algorithm is an iterative procedure. At each time, (i) two nodes directly connected with an edge are chosen randomly, (ii) they exchange their values according to the sign of the edge, and (iii) they update their values as the average of each node's value and its received value. It is shown that the values of the algorithm always converge in mean square, where a bipartite consensus or a trivial consensus is achieved. A convergence time is defined as the smallest time such that it takes for the values of the algorithm to get within a given neighborhood of the consensus value with high probability, regardless of initial state. An upper bound of the convergence time is given in terms of a characteristic value of the given graph.",

author = "Linh, {Nguyen Thi Hoai} and Takayuki Wada and Izumi Masubuchi and Toru Asai and Yasumasa Fujisaki",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 10th Asian Control Conference, ASCC 2015 ; Conference date: 31-05-2015 Through 03-06-2015",

year = "2015",

month = sep,

day = "8",

doi = "10.1109/ASCC.2015.7244534",

language = "English",

series = "2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

editor = "Hazlina Selamat and Ramli, {Hafiz Rashidi Haruna} and Faudzi, {Ahmad Athif Mohd} and Rahman, {Ribhan Zafira Abdul} and Ishak, {Asnor Juraiza} and Soh, {Azura Che} and Ahmad, {Siti Anom}",

booktitle = "2015 10th Asian Control Conference",

address = "United States",

}

TY - GEN

T1 - Convergence time evaluation of a gossip algorithm over signed graphs

AU - Linh, Nguyen Thi Hoai

AU - Wada, Takayuki

AU - Masubuchi, Izumi

AU - Asai, Toru

AU - Fujisaki, Yasumasa

PY - 2015/9/8

Y1 - 2015/9/8

N2 - Convergence time is investigated for a gossip algorithm over a connected signed graph, where each edge of the graph has positive or negative sign. The algorithm is an iterative procedure. At each time, (i) two nodes directly connected with an edge are chosen randomly, (ii) they exchange their values according to the sign of the edge, and (iii) they update their values as the average of each node's value and its received value. It is shown that the values of the algorithm always converge in mean square, where a bipartite consensus or a trivial consensus is achieved. A convergence time is defined as the smallest time such that it takes for the values of the algorithm to get within a given neighborhood of the consensus value with high probability, regardless of initial state. An upper bound of the convergence time is given in terms of a characteristic value of the given graph.

AB - Convergence time is investigated for a gossip algorithm over a connected signed graph, where each edge of the graph has positive or negative sign. The algorithm is an iterative procedure. At each time, (i) two nodes directly connected with an edge are chosen randomly, (ii) they exchange their values according to the sign of the edge, and (iii) they update their values as the average of each node's value and its received value. It is shown that the values of the algorithm always converge in mean square, where a bipartite consensus or a trivial consensus is achieved. A convergence time is defined as the smallest time such that it takes for the values of the algorithm to get within a given neighborhood of the consensus value with high probability, regardless of initial state. An upper bound of the convergence time is given in terms of a characteristic value of the given graph.

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

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

U2 - 10.1109/ASCC.2015.7244534

DO - 10.1109/ASCC.2015.7244534

M3 - Conference contribution

AN - SCOPUS:84957651466

T3 - 2015 10th Asian Control Conference: Emerging Control Techniques for a Sustainable World, ASCC 2015

BT - 2015 10th Asian Control Conference

A2 - Selamat, Hazlina

A2 - Ramli, Hafiz Rashidi Haruna

A2 - Faudzi, Ahmad Athif Mohd

A2 - Rahman, Ribhan Zafira Abdul

A2 - Ishak, Asnor Juraiza

A2 - Soh, Azura Che

A2 - Ahmad, Siti Anom

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 10th Asian Control Conference, ASCC 2015

Y2 - 31 May 2015 through 3 June 2015

ER -

Convergence time evaluation of a gossip algorithm over signed graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this