Large-scale distributed synchronization systems, using a cancel-on-completion redundancy mechanism

What the paper says

We consider a class of multi-agent distributed synchronization systems, which are modeled as n particles moving on the real line. This class generalizes the model of a multi-server queueing system, considered in Stolyar (Stoch. Syst. 12:340–372, 2022), employing so-called cancel-on-completion (c.o.c.) redundancy mechanism, but is motivated by other applications as well. In the multi-server queueing system a particle location represents a server workload. Under c.o.c. mechanism, when a job of class j arrives, it selects $$d_j$$ d j particles uniformly at random, which try to jump forward, by random distances, but their advance is truncated at the new location of the $$k_j$$ k j -th left-most selected particle ( $$k_j \le d_j$$ k j ≤ d j ). Between jumps all particles move to the left at constant speed, but cannot cross point 0 (workload cannot be less than 0). Thus, the multi-server queueing system is modeled as a particle system, regulated at the left boundary point. The more general model of this paper is such that particles evolve the same way as the in left-regulated system, but we allow regulation boundaries on either side, or both sides, or no regulation at all. We consider the mean-field asymptotic regime, when the number of particles n and the job arrival rates go to infinity, while the job arrival rates per particle remain constant. The system state for a given n is the empirical distribution of the particles’ locations. Our results include: the existence/uniqueness of fixed points of mean-field limits (ML), which describe the limiting dynamics of the system; conditions for the steady-state asymptotic independence (concentration, as $$n \rightarrow \infty $$ n → ∞ , of the stationary distribution on a single state, which is necessarily an ML fixed point); the limits, as $$n \rightarrow \infty $$ n → ∞ , of the average velocity at which unregulated (free) particle system advances. In particular, our results for the left-regulated system unify and generalize the corresponding results in Stolyar (Stoch. Syst. 12:340–372, 2022). Our technical development is such that the systems with different types of regulation are analyzed within a unified framework. In particular, these systems are used as tools for analysis of each other.