Loading Events

« All Events

  • This event has passed.

Special GRASP Seminar: Shreyas Sundaram, University of Illinois at Urbana-Champaign, “Linear Iterative Strategies for Information Dissemination and Processing in Distributed Systems”

May 22, 2009 @ 11:00 am - 12:00 pm

Abstract: A core requirement in distributed systems and networks is the ability
to disseminate information from some or all of the nodes in the network
to the other nodes.  In this talk, we discuss a linear iterative
strategy for information dissemination, where each node repeatedly
updates its value to be a weighted linear combination of its previous
value and those of its neighbors.  We show that this strategy can be
compactly modeled as a linear dynamical system, and use
control-theoretic tools (such as observability theory, structured
system theory, and linear system theory) to characterize its

First, we show that in connected networks with time-invariant
topologies, the linear iterative strategy allows every node to obtain
the values of all other nodes after a finite number of iterations (or
time-steps).  The number of time-steps required is determined by the
network topology and, in fact, may be minimal over all possible
strategies for information dissemination. 

Next, we demonstrate the ability of the linear iterative strategy to
handle a set of malicious (and possibly coordinated) nodes that update
their values arbitrarily at each time-step.  It has been established in
the literature that when there are up to f malicious nodes, the network
connectivity must be at least 2f+1 in order to accurately transmit
information (with any protocol).  Surprisingly, we show that the linear
iterative strategy achieves this lower bound.  Specifically, after
running the linear iteration for a finite number of time-steps, each
node in the network will have enough information (and a checking
scheme) to correctly determine the values of the other nodes despite
the actions of up to f malicious nodes.  We thus establish linear
iterative strategies as viable and effective means of disseminating
information in networks.


- Learn More

Shreyas Sundaram received the Ph.D. degree
in electrical engineering from the University of Illinois at
Urbana-Champaign in 2009. He received the BASc. degree in computer
engineering from the University of Waterloo in 2003, and the M.S.
degree in electrical engineering from the University of Illinois at
Urbana-Champaign in 2005. His research interests lie in the areas of
secure and fault-tolerant control of distributed systems and networks,
linear system and estimation theory, and the application of algebraic
graph theory to system analysis. He received the M. E. Van Valkenburg
Graduate Research Award and the Robert T. Chien Memorial Award from the
ECE department at the University of Illinois at Urbana-Champaign, both
for excellence in research. He was a finalist for the Best Student
Paper Award at the 2007 and 2008 American Control Conferences.


May 22, 2009
11:00 am - 12:00 pm
Event Category: