Toward optimal network topology design for fast and secure distributed computation

J. Liu, Tamer Başar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationDecision and GameTheory for Security - 5th International Conference, GameSec 2014, Proceedings
EditorsRadha Poovendran, Walid Saad
PublisherSpringer-Verlag Berlin Heidelberg
Pages234-245
Number of pages12
ISBN (Electronic)9783319126005
DOIs
StatePublished - 2014
Event5th International Conference on Decision and GameTheory for Security, GameSec 2014 - Los Angeles, United States
Duration: Nov 6 2014Nov 7 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8840
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Conference on Decision and GameTheory for Security, GameSec 2014
CountryUnited States
CityLos Angeles
Period11/6/1411/7/14

Keywords

  • Algebraic connectivity
  • Distributed computation
  • External attack
  • Topology design
  • security

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Toward optimal network topology design for fast and secure distributed computation'. Together they form a unique fingerprint.

Cite this