TY - GEN

T1 - Combinatorial bounds and scaling laws for noise amplification in networks

AU - Jadbabaie, Ali

AU - Olshevsky, Alex

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893232244&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893232244&partnerID=8YFLogxK

U2 - 10.23919/ecc.2013.6669429

DO - 10.23919/ecc.2013.6669429

M3 - Conference contribution

AN - SCOPUS:84893232244

SN - 9783033039629

T3 - 2013 European Control Conference, ECC 2013

SP - 596

EP - 601

BT - 2013 European Control Conference, ECC 2013

PB - IEEE Computer Society

T2 - 2013 12th European Control Conference, ECC 2013

Y2 - 17 July 2013 through 19 July 2013

ER -