Ayalvadi Ganesh






Rumours, epidemics and consensus on graphs :   Lecture notes              Problem sheet

Research Interests:

I am interested in the mathematical modelling of communication and computer networks, and in decentralised algorithms for such networks. The mathematics used in studying these problems comes from large deviations, random graphs, queueing theory, information theory etc.


Note: Copyright is held by the publishers unless indicated otherwise.


Big Queues (with Neil O'Connell and Damon Wischik). Springer Lecture Notes in Mathematics, Volume 1838, 2004.

Papers (by topic)

Epidemics on networks

Pathogen spread on coupled networks: effect of host and network properties on transmission thresholds (with H.L.Mills and C. Colijn), Journal of Theoretical Biology, 2013.

A random walk model for infection on graphs: spread of epidemics and rumours with mobile agents (with M. Draief), Discrete Event Dynamical Systems, 2011.

How to distribute antidote to control epidemics (with C. Borgs, J. Chayes and A. Saberi), Random Structures and Algorithms, 2010.

Thresholds for virus spread on networks (with M. Draief and L. Massoulie), Annals of Applied Probability, 2008.

On the race of worms, alerts and patches (with M. Vojnovic), IEEE/ACM Trans. Networking, 2008.

Efficient quarantining of scanning worms: Optimal detection and co-ordination (with D. Gunawardena, P. Key, L. Massoulie and J. Scott), Proc. IEEE Infocom, 2006.

The effect of network topology on the spread of epidemics (with L. Massoulie and D. Towsley), Proc. IEEE Infocom, 2005.

Random graphs and stochastic processes on graphs

The robot crawler model on complete k-partite graphs and Erdos-Renyi random graphs (with A. Davidon), Preprint, 2017.

Maximal Steiner trees in the stochastic mean field model of distance (with A. Davidson), Combinatorics, Probability and Computing, 2017.

Exponential random graphs as models of overlay networks (with M. Draief and L. Massoulie), Journal of Applied Probability, 2009.

On the connectivity and diameter of small-world networks (with F. Xue), Advances in Applied Probability, 2007.

Peer counting and sampling in overlay networks based on random walks (with L. Massoulie, E. le Merrer and A.-M. Kermarrec), Distributed Computing, 2007. An earlier version appeared as  Peer counting and sampling in overlay networks: random walk methods in Proc. ACM Symp. Principles of Distributed Computing (PODC), 2006.

Efficient routing in Poisson small-world networks (with M. Draief), Journal of Applied Probability, 2006.

Failure resilience in balanced overlay networks (with L. Massoulie) Proc. 41st Annual Allerton Conference on Communication, Control and Computing, 2003.

Peer-to-peer systems and algorithms

Probabilistic consensus via polling and majority rules (with J. Cruise), Queueing Systems, 2014.

Efficient and adaptive epidemic-style protocols for reliable and scalable multicast (with I. Gupta and A.-M. Kermarrec), IEEE Trans. Parallel and Distributed Systems, 2006.

A compact routing protocol for ad-hoc networks (with M. Chen). Paper presented at SpasWin 2006.

Network awareness and failure resilience in self-organising overlay networks (with L. Massoulie and A.-M. Kermarrec), Proc. Symp. Reliable Distributed Systems (SRDS), 2003.

Peer-to-peer membership management for gossip-based protocols (with A.-M. Kermarrec and L. Massoulie), IEEE Trans. Computers, 2003.

Probabilistic reliable dissemination in large-scale systems (with A.-M. Kermarrec and L. Massoulie), IEEE Trans. Parallel and Distributed Systems, 2003.

Security for structured peer-to-peer overlay networks (with M. Castro, P. Druschel, A. Rowstron and D. S. Wallach), in Proc. Fifth Symposium on Operating Systems Design and Implementation (OSDI), 2002.

HiScamp: self-organizing hierarchical membership protocol (with A.-M. Kermarrec and L. Massoulie), in Proc. Tenth ACM SIGOPS European Workshop, 2002.

SCAMP: Peer-to-peer lighweight membership service for large-scale group communication (with A.-M. Kermarrec and L. Massoulie), in Proc. Third Intl. Workshop on Networked Group Communication (NGC), 2001.

Communication networks

User association for load balancing with uneven user distribution in IEEE 802.11 ax networks (with F Cao, Z Zhong, Z Fan, M Sooriyabandara, S Armour, in Proc. IEEE CCNC, 2016.

On the distribution and mean of received power in a stochastic cellular network (with F. Cao, S. Armour and M. Sooriyabandara), in Proc. Allerton Conf. Communication, Control and Computing, 2015.

Performance analysis of coordinated transmission for a stochastic cellular network (with F. Cao, S. Armour and M. Sooriyabandara), in Proc. IEEE PIMRC, 2015.

Performance analysis of contention based medium access control protocols (with G. Sharma and P. Key), IEEE Trans. Info. Theory, 2009. This is an extended version, with full proofs, of an earlier paper with the same title in Proc. IEEE Infocom, 2006.

Large deviations of the interference in a wireless communication model (with G. L. Torrisi), IEEE Trans. Info. Theory, 2008.

Dynamic decentralized multi-channel MAC protocols (with H. Seferoglu, A. Lakshmikantha and P. Key), in Proc. Information Theory & Applications Workshop, 2008.

Congestion pricing and non-cooperative games in communication networks (with K. Laevens and R. Steinberg), Operations Research, 2007.

Modeling the impact of buffering on 802.11 (with K. Duffy), IEEE Communication Letters, 2007.

Congestion notification and probing mechanisms for endpoint admission control (with P. Key, D. Polis and R. Srikant), IEEE/ACM Trans. Networking, 2006.

Resource allocation with persistent and transient flows (with S. Deb and P. Key). IEEE/ACM Trans. Networking, 2005.

Feedback and bandwidth sharing in networks (with P. Key and L. Massoulie), Proc. 39th Annual Allerton Conference on Communication, Control and Computing, 2001.

Congestion pricing and user adaptation (with K. Laevens and R. Steinberg), Proc. IEEE Infocom, 2001.

Bayes' asymptotics

Bayesian inference for Markov chains (with P. Eichelsbacher), Journal of Applied Probability, 2002.

Moderate deviations for Bayes posteriors (with P. Eichelsbacher), Scandinavian Journal of Statistics, 2002.

A large deviation principle for Dirichlet posteriors (with N. O'Connell). Bernoulli, 2000.

An inverse of Sanov's theorem (with N. O'Connell). Statistics & Probability Letters, 1999.

Bayesian network management (with P. J. Green, N. O'Connell and S. M. Pitts), Queueing Systems, 1998.

Queueing theory

Functional large deviations for Cox processes and Cox/G/infinity queues, with a biological application (with J. Dean and E. Crane), Preprint, 2018.

Latency reduction in communication networks using redundant messages (with J. Hollinghurst and T. Bauge), Proc. IEEE ITC, 2017.

Tolls and welfare optimization for multiclass traffic in multiqueue systems (with T. Bodas and D. Manjunath), Preprint, 2014.

Load Balancing and Routing Games with Admission Prices (with T. Bodas and D. Manjunath), in Proc. IEEE CDC, 2011.

Load balancing via random local search in closed and open systems (with S. Lilienthal, D. Manjunath, A. Proutiere and F. Simatos), in Proc. ACM Sigmetrics, 2010. (Winner of the Best Paper award.)

A class of risk processes with reserve-dependent premium rate: sample path large deviations and importance sampling (with C. Macci and G. L. Torrisi), Queueing Systems, 2007.

A class of risk processes with delayed claims: ruin probability estimates under heavy-tailed conditions (with G. L. Torrisi), Journal of Applied Probability, 2006.

The calculus of Hurstiness (with D. J. Wischik), 2005.

Sample path large deviations principles for Poisson shot noise processes, and applications (with C. Macci and G. L. Torrisi), Electronic Journal of Probability, 2005.

Invariant rate functions for discrete time queues (with N. O'Connell and B. Prabhakar), Annals of Applied Probability, 2003.

A large deviation principle with queueing applications (with N. O'Connell), Stochastics and Stochastic Reports, 2002.

The linear geodesic property is not generally preserved by a FIFO queue (with N. O'Connell), Annals of Applied Probability, 1998.

Large deviations of the sojourn time for queues in series Annals of Operations Research, 1998.

Bias correction in effective bandwidth estimation, Performance Evaluation, 1996.

Stationary tail probabilities in exponential server tandems with renewal arrivals (with V. Anantharam), Queueing Systems, 1996.

Optimal buffer allocation in tandems of last-come-first-served queues (with V. Anantharam), Queueing Systems, 1995.

Optimal buffer allocation in Jackson networks: Correctness within a constant of a rule of thumb (with V. Anantharam), IEEE Trans. Info. Theory, 1994.


Large and moderate deviations for matching and empirical discrepancies (with N. O'Connell), Markov Processes and Related Fields, 2007.

Information loss in riffle shuffling (with D. Stark and N. O'Connell). Combinatorics, Probability and Computing, 2002.

Poissonian behaviour of Ising Spin Systems in an External Field (with B. Hambly, N. O'Connell, D. Stark and P. Upton), Journal of Statistical Physics, 2000.


Non-parametric change point estimation using string-matching algorithms (with O. Johnson, D. Sejdinovic, J. Cruise and R. Piechocki), Methodology and Compuing in Applied Probability, 2014.

Spontaneous emergence of multiple drug resistance in tuberculosis before and during therapy (with C. Colijn, T. Cohen and M. Murray), PLoS ONE, 2011.

A Ca2+-based computational model for NMDA receptor-dependent synaptic plasticity at individual post-synaptic spines in the hippocampus (with O. Rackham, K. Tsaneva-Atanasova and J. Mellor), Frontiers in Synaptic Neuroscience, 2010.