TY - GEN
T1 - Toward optimal network topology design for fast and secure distributed computation
AU - Liu, J.
AU - Başar, Tamer
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - A typical distributed computation problem deals with a network of multiple agents and the constraint that each agent is able to communicate only with its neighboring agents. Two important issues of such a network are the convergence rate of the corresponding distributed algorithm and the security level of the network against external attacks. In this paper, we take algebraic connectivity as an index of convergence rate, which works for consensus and gossip algorithms, and consider certain type of external attacks by using the expected portion of the infected agents to measure the security level. Extremal examples and analysis show that fast convergence rate and high security level require opposite connectivity of the network. Thus, there has to be a trade-off between the two issues in the design of network topology. This paper aims to provide an approach to design a network topology which balances between convergence rate and security. A class of tree graphs, called extended star graphs, are considered. The optimal extended star graph is provided under appropriate assumptions.
AB - A typical distributed computation problem deals with a network of multiple agents and the constraint that each agent is able to communicate only with its neighboring agents. Two important issues of such a network are the convergence rate of the corresponding distributed algorithm and the security level of the network against external attacks. In this paper, we take algebraic connectivity as an index of convergence rate, which works for consensus and gossip algorithms, and consider certain type of external attacks by using the expected portion of the infected agents to measure the security level. Extremal examples and analysis show that fast convergence rate and high security level require opposite connectivity of the network. Thus, there has to be a trade-off between the two issues in the design of network topology. This paper aims to provide an approach to design a network topology which balances between convergence rate and security. A class of tree graphs, called extended star graphs, are considered. The optimal extended star graph is provided under appropriate assumptions.
KW - Algebraic connectivity
KW - Distributed computation
KW - External attack
KW - Topology design
KW - security
UR - http://www.scopus.com/inward/record.url?scp=84910008894&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84910008894&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-12601-2_13
DO - 10.1007/978-3-319-12601-2_13
M3 - Conference contribution
AN - SCOPUS:84910008894
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 234
EP - 245
BT - Decision and GameTheory for Security - 5th International Conference, GameSec 2014, Proceedings
A2 - Poovendran, Radha
A2 - Saad, Walid
PB - Springer
T2 - 5th International Conference on Decision and GameTheory for Security, GameSec 2014
Y2 - 6 November 2014 through 7 November 2014
ER -