### Abstract

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 language | English (US) |
---|---|

Title of host publication | 2013 European Control Conference, ECC 2013 |

Publisher | IEEE Computer Society |

Pages | 596-601 |

Number of pages | 6 |

ISBN (Print) | 9783033039629 |

DOIs | |

State | Published - 2013 |

Event | 2013 12th European Control Conference, ECC 2013 - Zurich, Switzerland Duration: Jul 17 2013 → Jul 19 2013 |

### Publication series

Name | 2013 European Control Conference, ECC 2013 |
---|

### Other

Other | 2013 12th European Control Conference, ECC 2013 |
---|---|

Country | Switzerland |

City | Zurich |

Period | 7/17/13 → 7/19/13 |

### 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

*2013 European Control Conference, ECC 2013*(pp. 596-601). [6669429] (2013 European Control Conference, ECC 2013). IEEE Computer Society. https://doi.org/10.23919/ecc.2013.6669429