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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$d_j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>d</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> particles uniformly at random, which try to jump forward, by random distances, but their advance is truncated at the new location of the <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$k_j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>k</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation>-th left-most selected particle (<InlineEquation ID="IEq3"> <EquationSource Format="TEX">$k_j \le d_j$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>k</mi> <mi>j</mi> </msub> <mo>≤</mo> <msub> <mi>d</mi> <mi>j</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>). 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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$n \rightarrow \infty $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo stretchy="false">→</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>, of the stationary distribution on a single state, which is necessarily an ML fixed point); the limits, as <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$n \rightarrow \infty $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo stretchy="false">→</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>, 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.

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

期刊论文
出版模式：

开放获取
发表日期：

2026年2月9日

查看全文

Alexander L. Stolyar

摘要

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} \leq 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 \to \infty$ , of the stationary distribution on a single state, which is necessarily an ML fixed point); the limits, as $n \rightarrow \infty $ $n \to \infty$ , 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.