Mixing time is a global property of a network that indicates how fast a random walk gains independence from its starting point. Mixing time is an essential parameter for many distributed algorithms, but especially those based on gossip.

In this talk I will present a completely decentralized algorithm to measure the mixing time of a network. The algorithm is based on an interesting application of a classic control-theoretic algorithm to network communication. In particular, the algorithm models the diffusion of information seen from each node in the network as the impulse response of a particular dynamic system. I will present the essential ideas behind the algorithm, as well as practical aspects of its design and implementation.

About Antonio Carzaniga

Antonio Carzaniga is a Professor in the Faculty of Informatics of Università della Svizzera italiana (USI), Switzerland, which he joined as an Assistant Professor when the Faculty was founded in 2004. From 2001 to 2007 he was an Assistant Research Professor in the Department of Computer Science at the University of Colorado at Boulder, United States. He received the Laurea degree in Electronic Engineering and the Ph.D. degree in Computer Science from Politecnico di Milano, Italy, in 1994 and 1999, respectively. Broadly speaking, Antonio’s research is in the areas of Networking and Software Engineering. Currently, Antonio is working on an ICN architecture that combines push and pull information flows, supports expressive descriptors as well as very efficient locators, features loop-free routing to single or multiple destinations, and does not require per-packet in-network state.

Personal website

This event will be conducted in English