Combinatorial bounds and scaling laws for noise amplification in networks

Ali Jadbabaie, Alex Olshevsky

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


Motivated by the problem of designing and analyzing clock synchronization protocols for large-scale networks, we provide combinatorial bounds on the mean square disagreement of synchronization dynamics subject to additive noise. While previous work has used eigenvalues to analyze the mean square disagreement when the synchronization dynamics is governed by a normal matrix, in the non-normal case eigenvalues cease to be an adequate measure. We first show that the so-called 2-norm coefficient of ergodicity used in the study of inhomogeneous Markov chains can be used to bound mean square disagreement even when the underlying dynamics is governed by a non-normal matrix. Our main result then demonstrates that the 2-norm coefficient of ergodicity has a natural combinatorial interpretation as a combined measure of matrix non-normality and graph connectivity. We apply this result to yield new performance guarantees for distributed clock synchronization: we show that in a simple (possibly irregular) random graph model, the natural clock synchronization scheme wherein neighboring nodes average their clocks is order-optimal: it drives the expected clock offsets between any two nodes to at most a constant, independently of the total number of nodes.

Original languageEnglish (US)
Title of host publication2013 European Control Conference, ECC 2013
PublisherIEEE Computer Society
Number of pages6
ISBN (Print)9783033039629
StatePublished - 2013
Event2013 12th European Control Conference, ECC 2013 - Zurich, Switzerland
Duration: Jul 17 2013Jul 19 2013

Publication series

Name2013 European Control Conference, ECC 2013


Other2013 12th European Control Conference, ECC 2013

ASJC Scopus subject areas

  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Combinatorial bounds and scaling laws for noise amplification in networks'. Together they form a unique fingerprint.

Cite this