Measuring the mixing time of a network

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. We design, implement, and evaluate a distributed protocol to measure mixing time. The protocol extends an existing algorithm that models the diffusion of information seen from each node in the network as the impulse response of a particular dynamic system. In its original formulation, the algorithm was susceptible to topology changes (or “churn”) and was evaluated only in simulation. Here we present a concrete implementation of an enhanced version of the algorithm that exploits multiple parallel runs to obtain a robust measurement, and evaluate it using a network testbed (Emulab) in combination with a peer-to-peer system (FreePastry) to assess both its performance and its ability to deal with network churn.

I. Introduction

The performance of distributed algorithms often depends on global properties of the network, where the term “network” here refers broadly to a generic interconnection of computational nodes, including wide-area networks, data-center networks, ad hoc networks, and many kinds of overlay networks. One of these critically important properties is the mixing time of the network, a global property that indicates how fast a random walk gains independence from its starting point [1].