Analysis of distributed systems via quasi-stationary distributions

Abstract

We present a new probabilistic analysis of distributed systems. Our approach relies on the theory of quasi-stationary distributions (QSD) and the results recently developed by the first and third authors. We give properties on the deadlock time and the distribution of the model before deadlock, both for discrete and diffusion models. Our results apply to any finite values of the involved parameters (time, numbers of resources, number of processors, etc.) and reflect the real behavior of these systems, with potential applications to deadlock prevention.

Keywords:

• Distributed algorithms
• deadlock
• quasi-stationary distributions

Acknowledgments

The authors are grateful to the anonymous referee for his comments and suggestions.