  A major impediment towards the industrial adoption of decentralized
distributed systems comes from the difficulty to theoretically prove that these
systems exhibit the required behavior. In this paper, we use probability theory
to analyze a decentralized auto-scaling algorithm in which each node
probabilistically decides to scale in or out. We prove that, in the context of
dynamic workloads, the average load of the system is maintained within a
variation interval with a given probability, provided that the number of nodes
and the variation interval length are higher than certain bounds. The paper
also proposes numerical algorithms for approximating these minimum bounds.
