Toward optimal network topology design for fast and secure distributed computation

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.