Resetting-based designated information distribution

Resetting-based designated information distribution Xiaojuan Ma,1, ∗ Yan Wang,2, 3, ∗ and Indranil Gupta1 1

Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign, Champaign, Illinois 61820, USA 2 Department of Mathematics, Wayne State University, Detroit, Michigan 48202, USA 3 Institute for AI and Data Science (AIDaS), Wayne State University, Detroit, Michigan 48202, USA

arXiv:2611.12485v1 [cs.DC] 9 Nov 2026

For a network of n nodes under random gossip dynamics, we show that by introducing the additional resetting mechanism (with rate β) to a designated subset of r nodes, the expected sum of all node values is asymptotically equal to nr times the sum of the initial values of the r designated nodes, in the small-β and long-time limit. We also analyze the convergence speed to this asymptotic state and provide an approximate high-probability confidence interval for the expected sum at finite time t and finite β. Operationally, we propose a protocol that distributes the initial node values over the designated subset evenly (up to a prescribed precision), by appropriately turning on and off the resetting dynamics. Our work not only offers insights into classical problems such as distributed computing and network control, but also serves as a potential foundation for designing quantum algorithms that prepare desired states in quantum networks using only local operations.

I.

INTRODUCTION

Consider a connected network with n nodes. At each time t ≥ 0, the network carries some information, which is characterized by a state vector xt with xt (i) being the state value of the ith node. This state vector can, for example, describe the spin configuration of a physical system, where xt (i) ∈ {±1} [1, 2]; the voting pattern in a consensus model, where xt (i) may take values in one of possible states or even be a general probability distribution [3–8]; the sensor readings in a sensor network [9–11]; or a statistic of model weights in decentralized federated learning, where xt (i) ∈ R [12–15]. In such settings, adjacent nodes typically exchange their individual information over time, and this process can be effectively captured by the gossip dynamics [16–20] where each node updates its value at time t, xt (i), based on interactions with its neighbors. Under fairly general update rules of the gossip dynamics, conformity among components will emerge, giving rise to the ferromagnetic phase in spin systems, consensus in social systems, and synchronization in dynamical systems [21–25]. In the setting where xt (i) ∈ R, it is well established that the network will eventually achieve the synchronized state [16], which is given by the average of the initial state of all nodes: n

x∞ (1) = · · · = x∞ (n) =

1X x0 (i) n i=1

(by gossip).

(1)

This result of average consensus also has important implications for distributed computing. It shows that global information sharing can emerge from purely local dynamics [16, 26, 27]. In particular, average consensus is sufficient for evaluating any linear function that does not depend on node labels. If F : Rn → R is linear and invariant under permutations of the node values, then there exists a coefficient vector a = (a1 , . . . , an )⊤ ∈ Rn such that F (x) = a⊤ x for all x ∈ Rn , and swapping any two coordinates i and j gives (ai − aj )(xi − xj )P= 0 for all x. Therefore, ai = aj n for all i, j, and F (x) ∝ i=1 x(i) is a scalar multiple of the

∗ These authors contributed equally to this work and are listed al-

phabetically.

sum. Hence, thereP exists a scalar function f : R → R such
n that F (x) = f n1 i=1 x(i) . Thus, once nodes agree on the mean, no further internode communication is needed to evaluate such an F [28]. Average consensus and its variants have been widely studied; see, for example, [16, 23, 29]. These methods naturally arise in fully decentralized settings, where no centralized or privileged nodes exist and communication is restricted to local interactions. They underpin applications such as clock synchronization [30, 31], decentralized learning [13], and distributed optimization [32, 33]. A distinctive feature of the consensus state, as shown in Eq. (1), is that every node in the network contributes equally to the final average. In practice, however, many distributed computing tasks concern only a designated subset of node values. In such settings, all nodes may still participate in the communication process, while the computed result should depend only on the initial values of the designated subset. This distinction between communication and contribution arises naturally in distributed information processing. For example, in sensor networks, one may wish to average readings only from sensors satisfying a prescribed condition, such as sensors in a certain region or sensors detecting a particular event, while other nodes merely relay the information through the network [34]. Another example is federated learning, where, in each communication round, model updates from a selected subset of participating clients are aggregated [35]. This naturally raises the question of whether information within a designated subset of nodes, embedded in a larger network, can be shared solely through local operations. Note that the nodes in this designated subset are not necessarily directly connected and form a cluster, and one is not allowed to create new shortcuts between them or to remove existing links in the network. In such cases, the gossip dynamics alone is not enough (though it remains essential for disseminating information across the network and should be kept as one ingredient of the protocol), and another mechanism is needed to “amplify” the signal originating from the designated subset of nodes. We show that this role is played by a local resetting operation applied only to the designated nodes. Our protocol relies on a crucial observation from Eq. (1): if the goal is to distribute some quantity uniformly across

2 the network (computing the average), it is the sum of the initial values x0 (i), rather than the initial state vector x0 itself, that really matters under the gossip dynamics. In this work, we consider the case where an ambient network undergoes the gossip dynamics, and we only have access to a given subset of nodes, i.e., we can perform local operations on them. We do not make any assumptions about the underlying topology or the locations of the designated nodes in the network. Without loss of generality, we let such nodes be indexed by {1, . . . , r}, where 1 ≤ r ≤ n is the size of the subset. Recall that our goal is to drive the designated subset of nodes to reach a state primarily determined by their own initial states, with only a secondary (ideally vanishing) influence from the rest of the network. That is, r

x∞ (1) = · · · = x∞ (r) ≈

1X x0 (i) r i=1

(our goal).

(2)

Based on the observation above, our goal (2) can essentially be achieved by requiring that n X

r

nX x0 (i). xt (i) ≈ r i=1 i=1

(3)

In other words, the problem Pncan be formulated as controlling the component sum i=1 xt (i) via appropriate operations. Once the sum is brought sufficiently close to the desired value specified in Eq. (3), the operation is then discontinued. The whole network will subsequently evolve under the gossip dynamics alone to a state that satisfies condition (2), as is well known. In this work, x0 (i)’s are fixed quantities, but all xt (i)’s for t > 0 are random as a result of our protocol. To achieve (3), we require by the protocol, Pn that at some time t specified P r the sum i=1 xt (i) is sufficiently close to nr i=1 x0 (i) with high probability. The precise meaning of (3) is given in Sec. III C. One major contribution of our work is that we uncover resetting as the crucial mechanism to achieve Eq. (3). Resetting has been shown to lead to nontrivial dynamical consequences in various situations, including random search [36–38], Bernoulli trials [39, 40], first-passage problems in diffusion processes [41], and generative machine learning [42]. In the study of opinion dynamics, this mechanism has been used to model a zealot in the voter model [2], where the presence of a single node with the resetting mechanism (a special case of our work) suffices to drive the whole system into the consensus state determined by its own initial state. In the Friedkin-Johnsen (FJ) model [43–46], each node may persistently hold its initial opinion to some extent. The resetting mechanism modifies the long-time limit of the system state, resulting in a final state in which each node converges to a weighted sum of the stubborn nodes’ initial values, with the weights determined by factors such as the network structure and the placement and stubbornness of the stubborn nodes. Intuition of the protocol. Our protocol can be represented in part by a specific randomized FJ model. However, there are three fundamental differences between our work and prior work on the FJ model. First, our ultimate goal is to

find a local operation (which turns out to be resetting) such that the system can be approximately driven to a desired state, rather than to investigate the outcome of the given resetting operation on the opinion dynamics. Second, as will be shown below, the relevant region of the resetting rate β (defined in Sec. II as the probability that a designated node is reset to its initial value at each time step) in our work is β ≪ 1. Even when β is vanishingly small, the effect of the seemingly weak resetting dynamics still has a profound impact on the long-time behavior of the system, based on which Eq. (3) is established. Third, our protocol includes operational guidance as to the intensity and duration of the resetting dynamics, which is beyond the scope of the FJ model. In the following sections, we provide a self-contained analysis of the resetting-modified gossip dynamics. (i) We first derive the long-time limit the mean sum Pof n of the state vector components E[ i=1 x∞ (i)], which Pr is well approximated by nr i=1 x0 (i), and the difference is proportional to β. Physically, this result shows that, for small β, the whole network will eventually be dominated by the designated subset of nodes. (ii) We also showP that the convergence of the finite-time n mean sum E[ i=1 xt (i)] to its limit is exponentially fast and obtain an approximate rate in terms of β. (iii) Finally, conditional on a given network, we establish an approximate high-probability bound for a random realization of the process, where with probability at least P 1 − δ [δ ∈ (0, 1) is prescribed], the (random) n sum i=1 xt (i) at or beyond some Pr critical time t∗ is close to the desired value of nr i=1 x0 (i) within a prescribed precision ε, as long as we set β ≤ β ∗ , where β ∗ is a critical value of the resetting rate. Both t∗ and β ∗ can be calculated from our theory. Based on these results, our protocol proceeds Pn in two steps. First, we generate the desired sum of i=1 xt (i) by running the resetting dynamics (together with the gossip dynamics) at a proper rate for an appropriate duration. Then, we turn off the resetting dynamics, and the sum is distributed over the whole network by the gossip Pndynamics alone. We stress that controlling the sum i=1 xt (i) to the vicinity of the target, rather than a specific state value distribution over the network, is sufficient for the twostep protocol to achieve uniform value distribution across all nodes. This is because the gossip dynamics in the second step guarantees that every node converges to the same value, regardless of how values are distributed across nodes at the start of the second step. Since the gossip dynamics has been extensively studied and well understood, we only focus on the first step of our protocol to achieve Eq. (3). From a broader perspective, our results are also pertinent to quantum settings where it is desirable to prepare a common quantum state among subsystems in a controllable and distributed way. Due to the no-cloning theorem and the destructive nature of measurements, admissible protocols should avoid information replication or value inspection. The classical counterpart investigated in this work may thus serve as a foundation for developing a fully quantum protocol. We leave this for future work.

3 uniformly randomly picked such that nodes it and jt will (partially) exchange their information by swapping their states (xt (jt ), xt (it )) ← (xt (it ), xt (jt )).

FIG. 1. Model illustration: In an underlying connected network with arbitrary topology, a randomly selected pair of connected nodes probabilistically swap their states at each time step (with rate α). Subsequently, one node from the designated set (highlighted in orange) probabilistically resets its state to its initial value (with rate β). Note that the designated nodes may be arbitrarily distributed across the network and do not necessarily form a cluster.

We present the details of our dynamical model in Sec. II. Theoretical results and numerical verifications are given in Secs. III and IV, respectively. We discuss applications of our protocol in more general settings in Sec. V, and conclude our work in Sec. VI.

II.

The intensity of this swapping process is denoted by some α ∈ (0, 1). Physically, this can be interpreted as the coupling intensity between nodes it and jt ; probabilistically, one may understand that swapping happens with probability α, and the system is unchanged with probability 1 − α. In the matrix form, this process is given by x̃t = (1 − α)xt + αWt xt

Wt = In − (eit − ejt )(eit − ejt )T is a random matrix with (it , jt ) ∈ E being the edge selected at time t, In is the n × n identity matrix, ei is ith standard orthonomral basis vector in the n-dimensional Euclidean space Rn , and the operation of transpose is denoted by the superscript T . The swapping process serves as the core of classical gossip dynamics and its properties are well known [16]. First, we know that E[Wt ] = In −

E = {(i, j)}. The cardinality of E is denoted as m. The adjacency matrix of the network is a symmetric n × n matrix A with Aij = 1 if (i, j) ∈ E and Aij = 0 if (i, j) ∈ / E. For all i ∈ [n], we have Aii = 0. (We use [n] to denote the set {1, . . . , n}.) At time t = 0, 1, 2, . . ., a vector xt of length n is used to represent the state of the network, and the state of the ith node is xt (i). Without loss of generality, we let [r] with 1 ≤ r ≤ n be the index set of designated nodes to which the additional resetting dynamics is applied. The set [n]\[r] is the index set of s = n − r remaining nodes in the network that are not subject to resetting. Aside from requiring the graph to be connected, we make no assumptions about its topology or the locations of the designated nodes. As illustrated in Fig. 1, there are two ingredients of the dynamical process in our model: swapping and resetting. (1) Swapping. This gives rise to the gossip dynamics. At time t, a uniformly randomly selected pair of nodes will exchange their states. That is, some edge (it , jt ) ∈ E is

(4)

where x̃t denotes the intermediate state after the swapping process and

DYNAMICAL MODEL

Suppose we are given a connected network with n nodes. The set of edges consists of unordered pairs (i, j), which means there is a direct link between nodes i and j:

(swapping),

L , m

(5)

where L = D − A is the Laplacian matrix of the network and Pn D = diag{d1 , . . . , dn } is the degree matrix with di = j=1 Aij . The expectation is with respect to the random edge selection process. Second, swapping does not change the sum of the state vector components. That is, for all t, T 1T n Wt xt = 1n xt ,

where 1n is the n-dimensional vector with all entries being 1. (2) Resetting. After the swapping process, an independent resetting process is triggered. The state of a uniformly randomly selected node indexed in [r] will be reset to its initial state at rate β. That is, for the selected node kt ∈ [r], we update its state as xt+1 (kt ) = (1 − β)x̃t (kt ) + βx0 (kt )

(resetting).

(6)

The remaining nodes keep their states unchanged. We stress that kt is not necessarily equal to it or jt in the swapping process. The edge and node selections are independent. With the help of an ancillary state vector that always stays at x0 , we rewrite the resetting dynamics as

  T (1 − β)Ir + β(Ir − ekt |r eT kt |r ) 0r×s βekt |r ekt |r 0r×s         x̃t xt+1 x̃ 0 I 0 0 s×r s s×r s×s   = := Pt t , x0 x0 0r×r 0r×s Ir 0r×s  x0 0s×r 0s×s 0s×r Is

(7)

4 where ek|r denotes the kth standard orthonormal basis vector in the r-dimensional Euclidean space Rr and 0s×r is an s × r matrix with all entries being 0. Combining the two processes (4) and (7) together yields the complete state update rule at time t: 

    xt+1 (1 − α)In + αWt 0n×n xt = Pt x0 0n×n In x0   x := Pt Qt t . x0

(8)

Applying Eq. (8) iteratively yields     xt+1 x = Pt Qt . . . P0 Q0 0 := x0 x0

t Y τ =0

!  x0 Pτ Qτ . x0

Note that Pτ is a block upper triangular matrix and Qτ is a block-diagonal matrix. The product Pτ Qτ thus is also a block upper triangular matrix and we denote it as  Aτ Bτ , 0n×n In

A.

Asymptotic mean state

Starting from a given initial state vector x0 and network Laplacian L, each realization of the process leads to a random final state vector xt . We first analyze the mean of xt , denoted as E[xt ], where the expectation is taken over all the randomness in the process but conditional on x0 and L. To this end, we will derive a closed-form expression for E[xt ]. Since the swapping and resetting dynamics are independent and identically distributed at each round, we might omit the subscript in Wτ , Aτ , Bτ , Pτ , and Qτ when calculating their means. By independence, we have E[P Q] = E[P ]E[Q]. By the definition of Q,   (1 − α)In + αE[W ] 0n×n E[Q] = . 0n×n In Inserting Eq. (5) to the expression above yields (1 − α)In + αE[W ] = In −

α L. m

 Pτ Qτ =

T where Aτ = (In − βekτ eT kτ )[In − α(eiτ − ejτ )(eiτ − ejτ ) ], Bτ = βekτ eT kτ , and ei is the ith standard basis vector in the Euclidean space Rn . Therefore, t−1 Y

! Pτ Qτ

τ =0



 At−1 Bt−1 = , 0n×n In

where At−1 = At−1 . . . A0 and

Hence we conclude   α L 0n×n In − m E[Q] = . 0n×n In Similarly, by the definition of P in Eq. (7), one of the r nodes is selected uniformly random at each round. That is, kt is uniformly randomly distributed in [r], i.e., kt ∼ Unif([r]). Taking expectation with respect to k yields ! r 1 1 X T T ek|r ek|r = Ir , Ekt ∼Unif([r]) [ekt |r ekt |r ] = r r k=1

Bt−1 = At−1 . . . A1 B0 + . . . + At−1 Bt−2 + Bt−1 .

and we thus have 

  1 − βr Ir 0r×s βr Ir 0r×s   0s×r Is 0s×r 0s×s  E[P ] =   0 0r×s Ir 0r×s  r×r 0s×r 0s×s 0s×r Is   β In − r U U T βr U U T , := 0n×n In

We finally have an expression for xt as xt = (At−1 + Bt−1 )x0 = (At−1 . . . A0 + At−1 . . . A1 B0 + · · · + Bt−1 )x0 . (9) This equation serves as the foundation for our analysis, as detailed below. We treat x0 as fixed, and xt is a random vector due to the randomness in the matrix sequences {Aτ } and {Bτ }.

III.

RESULTS

In this section, we first derive the asymptotic mean of the sum of state values under the swapping and resetting dynamics in Sec. III A. We then establish an approximate convergence rate of the finite-time mean sum to its asymptotic value in Sec. III B. Finally, in Sec. III C, based on an effective dynamics, we investigate how the finite-time sum of state values from a random realization deviates from the asymptotic mean, and establish a high-probability bound for this deviation, which provides guidance on the choice of key parameters for our protocol.

where U = [e1 , . . . , er ] is an n × r matrix. The explicit expressions for E[A] and E[B] can be obtained based on E[P ] and E[Q] as   β α  T E[A] = In − U U (10) In − L , r {zm } | {z }| :=T2

:=T1

and E[B] =

β U U T. r

(11)

Again, by the independence of the dynamics at different times, we have E[At−1 ] = E[A]t

5 and E[Bt−1 ] = (E[A]t−1 + · · · + In )E[B]. Taking the expectation to Eq. (9) gives the mean state vector at time t as E[xt ] = E[A]t x0 + (E[A]t−1 + · · · + In )E[B]x0 .

Equation (14) shows that the global state will eventually be influenced by a designated subset of nodes with resetting dynamics. For small β, the main contribution is just from the subset of selected nodes, and the contribution from all other nodes in the network is secondary and vanishes as β → 0 by Eq. (14): r

(12)

nX x0 (i). r i=1

lim lim 1T n E[xt ] =

β→0 t→∞

We are interested in the t → ∞ limit of yt := 1T n E[xt ], which is the mean sum of the state vector xt . We first establish in Appendix A that the operator norm of E[A] is strictly less than 1 for β ∈ (0, 1). Hence,

Intuitively, the whole network seems to “consist of” n/r copies of the subset of nodes when it comes to the state sum. However, if we let β = 0 first, then the dynamics only contains the swapping process, which preserves the sum of xt at any t, i.e., for β = 0, we have at any time t that

lim E[A]t = 0n×n

T 1T n x(t) = 1n x0 (t).

t→∞

The two different scenarios imply that the t → ∞ and β → 0 limits do not commute:

and lim E[A]t−1 + · · · + In = (In − E[A])−1 ,

T lim lim 1T n E[x0 ] ̸= lim lim 1n E[x0 ].

t→∞

β→0 t→∞

which lead to the result that T −1 y∞ := lim 1T E[B]x0 . n E[xt ] = 1n (In − E[A]) t→∞

(13)

The first main result of this work is about the asymptotic mean sum of xt . For given network Laplacian L, swapping rate α, and the subset size r, we have for sufficiently small resetting rate β that

This noncommutativity of the limits arises because the resetting dynamics breaks the conservation of the value sum that holds under the swapping dynamics. If β is first set to 0, then E[B] becomes 0n×n and E[A] reduces to T2 = In −αL/m. The operator norm of E[A] thus becomes 1, and the influence of the initial state will not decay over time. In fact, in this case, we have at any time t that E[A]t x0 = (In − αL/m)t x0 =

r

nX x0 (i) + O(β). y∞ = r i=1

t→∞ β→0

where λ2 is the spectral gap, or the second smallest eigenvalue of the network Laplacian L. The details to derive this condition are also given in Appendix B. In general, a “small” β is easier to achieve in well connected networks (large λ2 ) than in poorly connected ones. However, Eq. (14) indicates that the influence of the network structure is of secondary importance. Specifically, when β is fairly small, our result holds irrespective of the network details. This is verified by our numerical simulations below in Sec. IV.

(1 − αλi /m)t vi viT x0

i=1

(14)

The big O notation is understood in the standard way. In general, the O(β) term remains present and the small β condition is essential for the approximation to hold. An exception is when x0 (k) is constant for all k ∈ [r], i.e., all designated nodes share the same initial value, in which case the O(β) term vanishes exactly for any β ∈ (0, 1). We show the detailed steps to derive Eq. (14) and discuss the special case in Appendix B. It is worth noting that in such an expression for y∞ , we highlight the role played by the resetting dynamics while keeping other factors fixed (such as the network structure as encoded in L and the swapping rate α). The exact expression for y∞ is given by Eq. (B7), and the dependence of y∞ on β is explicitly shown in Eq. (B8) to leading order in β. A sufficient condition under which β can be considered small is   m 1 1 + ≪ 1, (15) β r αr λ2

n X

= v1 v1T x0 +

n X

(1 − αλi /m)t vi viT x0

i=2

Pn =

i=1 x0 (i)

n

1n +

n X

(1 − αλi /m)t vi viT x0 ,

i=2

where 0 = λ1 < λ2 ≤ · · · ≤ λn are eigenvalues of L and vi ’s are the corresponding orthonormal eigenvectors. In partic√ ular, v1 = 1n / n represents the steady-state mode of the dynamics. For all other modes, the corresponding coefficient (1 − αλi /m)t will converge to 0 as t → ∞. (Detailed discussions on the spectra of E[A] are given in Appendix A.) Hence, the dynamics indeed preserves the sum of the state vector for β = 0: t lim 1T n E[A] x0 =

t→∞

n X

x0 (i).

i=1

This is consistent with the understanding that swapping only (partially) exchanges the state at each node, and the sum should not be changed. Nonetheless, the introduction of resetting dynamics leads to a nontrivial effect, even if the rate β is small. In the context of social influence, our result thus predicts that a group of persistent influencers, even if not directly connected, will reach consensus, with the opinions of others playing only a secondary role. While from the distributed computing perspective, this result paves the way for establishing the resetting mechanism as a tool for computing the mean of a subsample, which is our ultimate goal.

6 B.

Finite-time mean state and convergence rate

A natural and highly relevant question for the application of our approach is how quickly the mean sum yt converges to y∞ . Our result is practically useful Pnonly if the convergence from the initial state sum y = 0 i=1 x0 (i) to Pr the small-β long-time limit nr i=1 x0 (i) is sufficiently fast. We are thus interested in quantifying the difference between yt and y∞ at a finite t (and for a small β). We denote the difference as ∆t := yt − y∞ . Clearly, ∆t consists of two parts. The first part ∆t1 origit nates from the difference between 1T n E[A] x0 and its longtime limit: t T T t t ∆t1 = 1T n E[A] x0 − lim 1n E[A] x0 = 1n E[A] x0 . t→∞

|

{z

}

=0

As discussed above, the long-time limit vanishes since the operator norm ∥E[A]∥ < 1. Similarly, the other part ∆t2 is t−1 +· · ·+In )E[B]x0 and its the difference between 1T n (E[A] T corresponding long-time limit 1n (In −E[A])−1 E[B]x0 . This difference is again closely related to the spectral property of E[A]. As the operator norm ∥E[A]∥ is strictly less than 1, the convergence to the limiting state is exponentially fast. However, for operational purposes, an approximate but informative convergence rate might be more preferred. We obtain such a rate by first noticing that E[A] almost commutes with L at small β and then using matrix perturbation theory. Details are given in Appendix C. Here, we report our second main result of this work: For large t and small β, we have  t β ∆t ≈ 1 − ∆0 , (16) n where the initial gap ∆0 is approximately n X

Probabilistic bounds for a single trajectory

So far, we have analyzed the mean sum both in the long-time limit and at finite times. We have shown that, asymptotically, the mean sum is approximately driven to Pr n i=1 x0 (i), with an average convergence rate of roughly r (1 − nβ )t . From a practical standpoint, however, there remains one important question: Since the process is random, what can we say about the behavior of a single realization of the process? To this end, we now examine the behavior of a single random trajectory. We let Yt := 1T n xt be a random realization of the state sum at time t and yt = E[Yt ] is the expectation. We want to answer this question: How far is Yt from yt ? Operationally, if one can observe a single trajectory of the process, and can quantify the difference between Yt and yt (with high probability), then it is possible to control the process to a given precision ε > 0. Our third main result is   ε2 , (18) P (|Yt − yt | > ε) ≲ 2 exp − nβσr2 where σr = [maxk∈[r] x0 (k) − mink∈[r] x0 (k)]/2 is half the range of the node values in the designated subset. Technically, we establish that Yt is a sub-Gaussian random variable and nontrivially bound its tail probability using Hoeffding’s inequality [47]. This high-probability bound is based on an informative sub-Gaussian parameter associated with Yt , which results from an effective dynamics of the process where the randomness of Yt is mainly contributed by Bτ at each time step. We defer the detailed derivation of (18) to Appendix D. Combining (17) and (18) together, an important corollary can be obtained that, for ε > 0 and δ ∈ (0, 1), we have

r

nX x0 (i). ∆0 ≈ x0 (i) − r i=1 i=1

P (|Yt − y∞ | ≤ ε) ≳ 1 − δ

ln(ε/|∆0 |) . ln(1 − β/n)

(19)

if β ≤ β ∗ and t ≥ t∗ , where

Roughly speaking, this result shows that the mean sum is changed from the initial value to the desired limit exponentially fast for any fixed small β. Therefore, for a given precision, yt converges sufficiently close to y∞ in finite time. Operationally, this result defines a critical time beyond which the absolute difference |∆t | is smaller than the given precision. That is, for some fixed ε > 0, we have |∆t | ≲ ε, as long as t≥

C.

(17)

Suppose we know |∆0 |, β, and n, then an estimate of how long the resetting dynamics should be applied can be calculated such that the finite-time mean state sum yt is close to its long-time limit y∞ . Even if |∆0 | is unknown, we may still estimate the critical time needed to achieve a prescribed relative error (for example, ε = 0.1|∆0 |), provided that an upper bound of the network size n and a lower bound of the resetting rate β are available.

β∗ =

ε2 ln(ε/2|∆0 |) and t∗ = . 2 4n ln(2/δ)σr ln(1 − β/n)

(20)

This result is a consequence of the fact that   ε ε P(|Yt − y∞ | > ε) ≤ P |Yt − yt | > + P |yt − y∞ | > . 2 2 The first term on the right-hand side characterizes the intensity of the random fluctuation of Yt around its mean yt , and can be bounded by (18). The second term is either 0 or 1, depending on whether the time is long enough so that the difference between yt and y∞ is sufficiently small. This term is controlled by (17) and equals 0 for t > t∗ . This result is of great relevance in protocol design. Practically, if the necessary information of n, r, x0 is known, then we can set the values of β and t based on prescribed ε and δ, and the resulting state of a single stochastic trajectory will have a random sum Yt close to the deterministic limit y∞ with a statistical guarantee.

7 TABLE I. Notation used in the plots. Symbol xt (i) Yt = 1Tn xt yt = E[Yt ] y∞ = limt→∞ yt ∆t = y t − y ∞

IV.

Meaning State of node i at time t (random) State sum of a single random realization Mean state sum Long-time limit of the mean sum Gap to the limiting mean

NUMERICAL EXPERIMENTS

In this section, we present systematic numerical experiments to validate our theoretical findings. By Eq. (20): for a given precision ε and miscoverage rate δ, the resetting rate β ∗ required to guarantee convergence depends on the network size n and the half-range of the designated node values σr . The convergence time t∗ further depends on β ∗ and the initial gap ∆0 . Importantly, the convergence behavior under the parameters prescribed by our formula typically does not depend on the network topology or spectral properties, provided the small-β condition (15) holds. Our theoretical results hold for general connected networks, and we design the numerical experiments to test the protocol across representative network structures. We use Erdős-Rényi (ER), lattice, and Barabási-Albert (BA) networks as canonical examples of homogeneous random, regular spatial, and heterogeneous hub-dominated topologies, respectively. In the controlled ER experiments, we use connection probabilities p ∈ [0.3, 0.5] to obtain connected homogeneous random graphs, and vary one factor at a time, such as the range of designated values, the size of the designated set, the network size, or the initial sum gap ∆0 , while all other factors are held fixed. In Fig. 9, we further include a sparse ER network (p = 0.08) together with a lattice and a BA network, to compare the influence of different structural regimes and edge densities. Throughout, Yt = 1T n xt denotes the state sum of a single random realization, while yt = E[Yt ] denote its mean and y∞ = limt→∞ yt denote the long-time limit of yt . This, alongside other key notation, is summarized in Table I. Further, each of the following figures shows 50 independent realizations of the evolution of Yt . We begin with an illustrative example that introduces the key metrics and demonstrates the core convergence result in Sec. IV A. We then show the dynamical consequence when the resetting rate β is large and falls outside the regime predicted by our formula in Sec. IV B. We next investigate the impact of different designated node configurations in Sec. IV C. In Sec. IV D, we study the effect of network size n on convergence, and in Sec. IV E we explore how the initial sum gap ∆0 shapes convergence behavior. Finally, we demonstrate in Sec. IV F that, under the prescribed parameters, the convergence behavior is universal across network topologies with distinct spectral gaps, confirming the result of Eq. (14) that the spectral gap’s influence on y∞ via β serves as a first order correction.

FIG. 2. An ER network with n = 30 and p = 0.5. Nodes 1 through 5 undergo resetting dynamics with initial states indeiid pendently and identically distributed (iid) as x0 (1), . . . , x0 (5) ∼ iid

N (−1, 12 ). The initial states for nodes with i > 5 are x(i) ∼ N (0, 102 ). The two blue dashed lines correspond to yt ± ε/2, respectively (with ε = 1). The orange lines represent 50 realizations of the evolution of Yt . We use Eq. (20) to calculate the critical parameters β ∗ and t∗ , and then let β = β ∗ be the resetting rate and stop the process at time t∗ . Our theory guarantees that the coverage rate is approximately at least 1−δ = 0.9. That is, with high probability (approximately greater than 90%), a random realization of Yt∗ will lie within the interval y∞ ± ε. For this specific experiment, we numerically observe that the empirical coverage rate is cov = 98%.

A.

Illustrative example

We first use a concrete example to show the main findings of this work. We construct an ER network [48] with n = 30 and the connection probability for each pair of nodes is p = 0.5. The index set for the designated nodes is [r] with r = 5. The initial values of x0 (k), k ∈ [r] are drawn independently from the Gaussian distribution N (−1, 12 ) with mean −1 and variance 12 . Initial values for other nodes are independently drawn from N (0, 102 ). The swapping rate is α = 0.5. We numerically calculate y∞ and yt based on Eqs. (13) and (12), respectively. The process stops at t = t∗ and the resetting rate β is set to be β ∗ . Both t∗ and β ∗ are calculated based on Eq. (20) with precision ε = 1 and miscoverage rate δ = 0.1. In Fig. 2, we plot yt as well as the band yt ± ε/2, y∞ , and 50 independent realizations of the process from t = 0 to t∗ . Our theory predicts that when the process stops at t = t∗ , at least roughly 90% of the trajectories will end up within the interval y∞ ±ε. Note that the probability bound is derived from Hoeffding’s inequality, which can be quite conservative. We define the empirical coverage rate as cov := P̂ (|Yt∗ − y∞ | < ε), where P̂ denotes the empirical distribution. That is, cov is the proportion of independent runs whose terminal value Yt∗ falls within ε of y∞ at the stopping time t∗ . Numerically, 98% trajectories are within this interval at t = t∗ for this example.

8 B.

Influence of a large resetting rate β ≫ β ∗

Intuitively, one may want to speed up the dynamics by adopting a larger β than the theoretically predicted β ∗ from Eq. (20). However, if a substantially larger β is used, the statistical guarantee (19) will be lost. In Fig. 3, we plot how a large resetting rate β, which could be much larger than β ∗ , affects the dynamics. The settings are similar to those in Fig. 2 except that n = 50. All three panels use the same ER network, hence, the same t∗ and β ∗ . The first panel adopts β ∗ as the resetting rate, the second uses 50 × β ∗ , and the third uses 100×β ∗ . A larger β accelerates the initial convergence speed: trajectories under 50 × β ∗ and 100 × β ∗ resetting rates reach the vicinity of y∞ much faster than under β ∗ . However, this comes at a cost. First, we observe that individual trajectories exhibit larger variations when β is large, as frequent resetting introduces more noise into the dynamics. Second, and more critically, the trajectories fail to settle. Instead, they maintain persistent fluctuations around y∞ , with the amplitude of oscillations growing with β. As a result, coverage degrades significantly, dropping to 0.76 at 50 × β ∗ and further to 0.58 at 100 × β ∗ , and the trajectories fail to remain within y∞ ± ε even as t → ∞. In fact, once the network structure, the designated set, initial values, precision ε, and miscoverage rate δ are given, β ∗ is determined, and t∗ is also consequently determined. Increasing β will drive the finite-time mean sum yt to y∞ faster, but leaving the fluctuation of a random Yt around yt uncontrolled. Hence, there is a tradeoff between how fast the mean dynamics converges to its limit and how tightly a finite-time realization concentrates around its mean. The results in Fig. 3 confirm that, when ε and δ are prescribed, β ∗ achieves a balance between bias (the deterministic difference |yt − y∞ |) and variance (characterized by the random fluctuation |Yt − yt |) and it plays an essential role in ensuring both convergence and stability of our protocol.

these differences, all three settings achieve cov = 1.00 at t∗ , confirming the statistical guarantee of our theory.

2.

We in Fig. 5 examine how the number of designated nodes affects the convergence behavior. We use an ER network for demonstration with three choices of r ∈ {5, 10, 15}. To evaluate the impact of r, we apply two control strategies in the experiment to keep σr and ∆0 fixed. (1) To fix σr , the designated node initial values are always evenly spaced within [−1, 1]. For example, for r = 5 the initial values are {−1, −0.5, 0, 0.5, 1}. In this case, the half-range ∗ σr = 1 for all r, which, by Eq. (20), Pr keeps β identical across the three cases. Moreover, k=1 x0 (k) = 0 and thus a common target y ≈ 0 for all r. (2) To fix ∆0 = ∞ Pn Pr x0 (i) − nr i=1 x0 (i), it suffices to fix the total initial i=1P n sum i=1 x0 (i). For r = 5, the initial values for the n − 5 nondesignated nodes are iid draws from N (0, 102 ) and their sum is recorded as S. For r ∈ {10, 15}, a fresh set of n − r values {g̃(j)}nj≥r+1 is independently drawn from the same distribution and then rescaled multiplicatively as P the nondesignated node initial values: x0 (j) = g̃(j) × S/ k g̃(k). One readily finds that they sum exactly to S. Since the designated values sum to zero in every case, the total sum Pn x (i) = S, and hence the initial gap ∆0 is identical for i=1 0 all r, which further leads to the same t∗ by Eq. (20). With σr and ∆0 now both fixed, all three cases share the same β ∗ and t∗ , so that any observed difference in the convergence behavior is due to r alone. As shown in Fig. 5, all three trajectories are nearly indistinguishable and all achieve cov = 1.00 at their respective t∗ . Thus, with β = β ∗ , the convergence guarantee holds across different numbers of designated nodes.

3. C.

Number of designated nodes

Degrees of designated nodes

Influence of designated nodes

We explore the effects of different configurations of the designated nodes below, including the range of their initial values, the number of designated nodes, and their degrees.

1.

Range of initial values

We examine how the range of designated node initial values affects convergence behavior in Fig. 4. The setup is the same as that in Fig. 3, except for the initial values of designated nodes. We consider three sets of such values, all with the same mean, so the asymptote y∞ is identical across all three cases. However, we consider three different ranges: 1.0 (tight), 2.0 (medium), and 4.0 (wide). Since β ∗ depends inversely on the squared range of {x0 (k)}k∈[r] [Eq. (20)], a wider range yields a smaller β ∗ and consequently a longer stopping time t∗ . This is reflected in Fig. 4: for the tight range case, the convergence rate is the highest (β ∗ = 0.00167), followed by the medium (β ∗ = 0.00042) and wide (β ∗ = 0.00010) range cases. Theoretical stopping times t∗ are marked by vertical dotted lines. Despite

We investigate how the selection of designated nodes affects the convergence behavior in Fig. 6. To make the distinction more pronounced, we use a Barabási-Albert (BA) scale-free network [49] with n = 50 and r = 3, and pick the designated set in three ways: (i) the r nodes are those with the highest degrees (hubs), (ii) the r nodes are chosen uniformly at random, and (iii) the r nodes are those with the lowest degrees (periphery). The corresponding degree sequences for each case are shown in the top row of Fig. 6. In all three cases, the designated nodes are assigned the same initial values {−1, 0, 1}, and the n − r remaining node values are drawn once from N (0, 102 ) and reused across the three cases. Consequently, the three cases use the same set of initial values, so the target y∞ , the half-range σr , and the initial gap ∆0 are identical. By Eq. (20), they share the same β ∗ and t∗ , and differ only in the choice of the designated set, whose nodes may have quite different degrees. As shown in the left panel of the bottom row of Fig. 6, under β = β ∗ , all three strategies yield cov = 1.00 at t∗ , and their trajectories are essentially indistinguishable. This result shows that the convergence guarantee by our protocol

9

FIG. 3. Effect of the resetting rate β on the convergence behavior for an ER network under the same setting as in Fig. 2, except that n = 50. All three panels share the same network, initial conditions, and critical time horizon t∗ and resetting rate β ∗ . The solid black line shows the theoretical prediction yt under β ∗ , and colored lines show 50 individual simulation replicates. Left: β = β ∗ ; the realizations Yt are tightly clustered around yt , all replicates converge within y∞ ± ε at t∗ , yielding cov = 1.00. Center: β = 50 × β ∗ ; convergence is faster initially, but trajectories exhibit persistent fluctuations and coverage drops to cov = 0.76. Right: β = 100 × β ∗ ; fluctuations are even larger and coverage further drops to cov = 0.58. In the latter two cases, trajectories fail to remain within y∞ ± ε even as t → ∞.

FIG. 4. Effect of the range of designated node initial values on the convergence behavior. The setup is the same as in Fig. 3, except for the initial values of the nodes in the designated set. We consider three sets of such initial values with the same mean 0 but different ranges: {−0.5, −0.3, 0, 0.3, 0.5} (tight), {−1.0, −0.5, 0, 0.5, 1.0} (medium), and {−2.0, −0.7, 0, 0.7, 2.0} (wide). Note that y∞ is also the same for all cases. As the range widens, β ∗ decreases and t∗ increases (vertical dotted lines) according to our theory. Numerically, the coverage rate cov = 1.00 is achieved at t∗ in all three cases.

does not depend much on the specific way to select the designated nodes, and holds regardless of whether hubs, randomly chosen nodes, or peripheral nodes are selected. Subset selection may, however, influence the dynamics when β is large, as shown in the right panel of the bottom row of Fig. 6. Under β = 100 × β ∗ , the hub strategy converges faster than the random and periphery strategies. Nevertheless, as also shown in Fig. 3, large resetting rates increase trajectory variation and induce oscillations, and in general there is no convergence guarantee for fixed ε and δ.

FIG. 5. Effect of the number of designated nodes r on the convergence behavior (ER network, n = 50, p = 0.3, α = 0.5, ε = 0.5, δ = 0.1, 50 replicates). Initial values for designated node are evenly spaced in [−1, 1] with mean zero for all r ∈ {5, 10, 15}; initial valuesP for other nodes are rescaled so that the sum of initial values n i=1 x0 (i), and hence y∞ , is identical across all three cases. The theoretical curve yt and its ±ε/2 band are plotted for each r; faint lines are individual replicates. However, the difference between them is too small, and they are visually indistinguishable, almost collapsing onto a single curve. In all three cases, we find cov = 1.00 at their respective t∗ , confirming that the coverage guarantee holds for different choices of r.

D.

Influence of network size

We investigate how the network size affects the convergence behavior in Fig. 7. We fix the network type (ER, p = 0.3) and the number of designated nodes (r = 5), and vary the network size n ∈ {30, 50, 100}. To isolate the effect of n, we apply two controls. (1) The designated values {−1, −0.5, 0, 0.5, 1} are the same Pr for all n. Since they sum to zero, the target y∞ ≈ nr k=1 x0 (k) = 0 for every n, and their half-range σr = 1 is fixed. (2) For

10

FIG. 6. Effect of designated node selection on convergence behavior (BA scale-free network, n = 50, r = 3, α = 0.5, ε = 0.5, δ = 0.1). Top row: Network visualizations for the three selection strategies: hubs (deg = [24, 14, 14]), random (deg = [2, 3, 4]), and periphery (deg = [2, 2, 2]). Bottom row: Mean trajectories (bold) and individual replicates (faint) over 50 runs, under β = β ∗ (left) and β = 100 × β ∗ (right). Under β = β ∗ , all three strategies achieve cov = 1.00 at t∗ . Under β = 100 × β ∗ , the hub strategy converges noticeably faster, while all strategies exhibit increased trajectory variance and oscillation, with no convergence guarantee.

each n, the non-designated node initial values are drawn independently from N (0, 102 ) and then rescaled so that P n i=1 x0 (i) matches the value used in the n = 30 case. Consequently, the initial gap ∆0 is identical for all three cases. By Eq. (20), β ∗ and t∗ depend on the initial values only through y∞ , σr , and ∆0 . With these fixed, the network size n is the only quantity that varies, and β ∗ = β ∗ (n) and t∗ = t∗ (n) depend on the corresponding n in each case. As shown in Fig. 7, larger networks converge more slowly: the stopping time t∗ increases substantially with n, as marked by the vertical dashed lines. This is expected since β ∗ (n) decreases with n, and larger networks require more steps for the gossip mixing dynamics to propagate information across the graph. In fact, by Eq. (20), β ∗ is proportional to n−1 , and t∗ ∼ n2 . Due to the computational cost, we do not further increase n in our simulations. Nevertheless, all three settings considered here achieve cov = 1.00 at their respective t∗ , providing evidence that the convergence guarantee scales correctly with network size.

E.

FIG. 7. Effect of network size n on convergence behavior (ER network, p = 0.3, r = 5, α = 0.5, ε = 0.5, δ = 0.1, 50 replicates). Designated node values are fixed at {−1, −0.5, 0, 0.5, 1}; regular node values are rescaled so that their sum is identical across all three cases, keeping the initial gap ∆0 constant while y∞ ≈ 0. Larger networks require longer stopping times t∗ (vertical dashed lines), yet all three settings achieve cov = 1.00 at their respective t∗ .

Influence of initial sum gap ∆0

Here we investigate how the initial sum gap ∆0 = y0 −y∞ affects the convergence behavior. Specifically, we fix an ER network (n = 50, p = 0.3) with r = 5 designated nodes

with initial values {−1, −0.5, 0, 0.5, 1} (note that the sum is 0), so that y∞ ≈ 0 in all cases. We then vary the mean of the Gaussian distribution from which the other n − r regu-

11

FIG. 8. Effect of the initial sum gap ∆0 = y0 − y∞ on convergence behavior (ER network, n = 50, p = 0.3, r = 5, α = 0.5, ε = 0.5, δ = 0.1, 50 replicates). The network, designated nodes, and their initial values {−1, −0.5, 0, 0.5, 1} are identical across all three cases. The initial values for other regular nodes are drawn from three Gaussian distributions with different means. A larger |∆0 | results in a longer stopping time t∗ (vertical dashed lines). All three cases achieve cov = 1.00 at their respective t∗ .

lar node initial values are drawn: N (0, 102 ), N (−10, 102 ), and N (−30, 102 ), respectively. As the Gaussian mean decreases, the corresponding gap |∆0 | increases. By Eq. (20), a longer stopping time t∗ is expected. We confirm this result in Fig. 8. The case with N (0, 102 ) starts closest to y∞ and converges earliest, while the case with N (−30, 102 ) starts furthest away from y∞ and requires the longest time to enter the ε band. The stopping time t∗ in each case is marked by a vertical dashed line. Despite these differences in |∆0 |, all three cases achieve cov = 1.00 at their respective t∗ , confirming that the convergence guarantee holds across a wide range of initial sum gaps.

F.

Influence of network structure

We compare the gossip-with-reset dynamics across three canonical network models: the ER random graph, the twodimensional periodic lattice, and the BA scale-free network. To separate the effect of edge density from that of topology, we consider the ER model at two densities: one with p = 0.3 as above (mean degree ⟨k⟩ ≈ 14.9) and a sparse variant (ER-sparse) with p = 0.08 whose mean degree ⟨k⟩ ≈ 3.8 is matched to that of the lattice (⟨k⟩ ≈ 3.7) and the BA (⟨k⟩ ≈ 3.8) network. This yields four network instances in total. All four networks have n = 50 nodes, with r = 5 designated nodes selected uniformly at random. The initial values of the designated nodes are iid draws from N (−1, 12 ), and those of the remaining nodes from N (0, 102 ). We run 50 independent replicates for each network. The four networks differ substantially in structure and spectral gap: λ2 = 7.3979 for ER, λ2 = 0.4063 for ER-sparse, λ2 = 0.3553 for the lattice, and λ2 = 0.7297 for BA. Specifically, ER is homogeneously well connected, the lattice has a rigid regular structure, and BA exhibits a highly heterogeneous degree distribution dominated by a few high-degree hubs (first row of Fig. 9). The ER-sparse, lattice, and BA networks are density matched (mean degree 3.7–3.8) but differ

in degree heterogeneity and spectral gap, whereas the two ER networks share the same random-graph model and differ in edge density by roughly a factor of 4; the comparison therefore separates the effect of density from that of topology. Despite these structural differences, when β ∗ and t∗ are computed from our theoretical formula, all four networks achieve 100% empirical coverage at the stopping time t∗ (second row of Fig. 9). This provides evidence that, for the representative topologies considered here, our convergence guarantee is insensitive to the network topology, without requiring any prior knowledge of the network topology. In particular, the guarantee does not depend on the spectral gap λ2 , provided that the small-β condition [Eq. (15)] is satisfied. This is a notable departure from many classical gossip and diffusion dynamics, where the spectral gap directly governs the convergence rate and different network topologies would require different parameter choices. The behavior changes, however, when β exceeds β ∗ , as shown in the third row of Fig. 9 with β = 100 × β ∗ . In this regime the coverage guarantee no longer holds for any of the four networks: the empirical coverage is cov = 0.22 (ER), 0.20 (ER-sparse), 0.08 (lattice), and 0.00 (BA), all far below the target 1 − δ = 0.9, and individual trajectories exhibit substantial variation across all four topologies. This further illustrates that operating far beyond β ∗ breaks the convergence guarantee regardless of network structure.

V.

FURTHER DISCUSSION

We mainly consider the task of subset averaging above, and one important ingredient of our protocol is calculatPr ing the “weighted” sum k=1 w(k)x0 (k) with w(k) = 1/r. This can be generalized to the case that w(k) is not constant. Concretely, if we let the resetting rate β be node specific such that β(k) = β0 w(k) for kP∈ [r], with β0 r being a common factor, w(k) ≥ 0, and k=1 w(k) = 1, then our analysis can still be applied with minor modifications. For example, the expression for T1 in Eq. (10) is now In − β0 U W U T with W = diag{w(1), . . . , w(r)}. Following Pr similar steps in Appendix B, we arrive at y∞ = n k=1 w(k)x0 (k) + O(β0 ), which naturally reduces to (14) when w(k) = 1/r. Our protocol may also be used to provide an approximate value of maxk∈[r] x0 (k), which is a highly nonlinear function of {x0 (k)}k∈[r] . To this end, we note the relation that max eηx0 (k) ≤ k

r X k=1

eηx0 (k) ≤ r max eηx0 (k) k

for any η > 0, which immediately implies ! r X 1 ln r ηx0 (k) max x0 (k) ≤ ln e ≤ max x0 (k) + . k k η η k=1

Hence, if a large η is given, and our protocol is applied to a set of modified initial values eηx0 (k) , then maxk x0 (k) can be approximated by a simple transformation of the protocol output.

12

FIG. 9. Comparison of gossip-with-reset dynamics across three network models: Erdős-Rényi (ER), periodic lattice, and BarabásiAlbert (BA). The ER model is included at two densities, the original p = 0.3 and a density-matched sparse variant (ER-sparse, p = 0.08), giving four network instances in total, with n = 50 nodes and r = 5 designated nodes selected uniformly at random. The designated node initial states are drawn iid from N (−1, 12 ) and those for the remaining nodes from N (0, 102 ). The four networks have distinct spectral gaps λ2 = 7.3979 (ER), 0.4063 (ER-sparse), 0.3553 (lattice), and 0.7297 (BA). The sparse ER, lattice, and BA networks are density matched (mean degree 3.7–3.8) while differing in degree heterogeneity and spectral gap, whereas the two ER networks share the same random-graph model but differ in edge density by roughly a factor of four; the comparison thus disentangles the effect of density from that of topology. Second row: Under β = β ∗ , all four networks achieve cov = 1.00 at t∗ , consistent with our convergence guarantee being insensitive to network topology under the small-β condition [Eq. (15)]. Third row: Under large β (β = 100 × β ∗ ), the coverage guarantee no longer holds, and a large β introduces significant variation among individual trajectories. Bold lines show the empirical mean, averaged across all Monte Carlo replicates at each time step. Fourth row: Degree distributions of the four network instances, illustrating the structural differences between ER (approximately Gaussian), lattice (near uniform), and BA (heavy tailed, hub dominated).

VI.

CONCLUSION

In this work, we theoretically analyze the effect of resetting (at rate β) on the gossip dynamics in a general connected network. We first observe that the long-time and small-β limits do not commute. As long as the resetting mechanism is present, even if β ≪ 1, the network will asymptotically converge to a state that is predominantly determined by a designated subset of nodes subject to resetting [Eq. (14)]. These nodes may be scattered throughout the network and need not form a cluster geometrically. For small β, we then show that the system converges exponentially fast to the asymptotic state and provides an approximate but informative rate [Eq. (16)]. Finally, we provide an approximate confidence interval for the mean sum of the system state at time t [Eq. (18)]. Combining these findings, we are able to identify the critical resetting rate and system evolution time [Eq. (20)] such that, with high probability, the resulting random sum of the state vector is within a specified tolerance of the mean sum of the asymptotic state [Eq. (19)]. It is worth noting that the resetting dynamics is local as it

involves only one node, the swapping dynamics is quasilocal as it involves two “adjacent” nodes, but the influence of the two types of dynamics is global. From a distributed systems perspective, the combination of resetting and swapping offers a means of controlling the network without relying on a central coordinator. This is beneficial not only for classical tasks, but also in quantum settings, where the resetting and swapping gates as natural generalizations of their classical counterparts can be applied to drive a quantum network toward some desired state determined by a subsystem. We hope the theory developed in this work could serve as a foundation for exploring such quantum applications, which may be crucial for advancing quantum communications.

ACKNOWLEDGMENTS

X.M. and I.G. were supported in part by NSF CNS Grant No. 2504595, grants from the IBM-Illinois Discovery Accelerator Institute (IIDAI), and a gift from Microsoft.

13 Appendix A: The operator norm of E[A]

On the other hand, since T2 commutes with L, it is well known that

Let M be a generic n × n real matrix. In this section, we use ∥M ∥ to denote the operator norm of M . That is, ∥M ∥ := maxv∈Rn :∥v∥=1 ∥M v∥. Moreover, if M has a spectral decomposition, then we use λi (M ) to denote the ith smallest eigenvalue of M and let vi (M ) be a corresponding orthonormal eigenvector.

1 vn (T2 ) = v1 (L) = √ 1n . n However, it is readily observed that √1n 1T n is not an eigenvector of T1 . We thus conclude that ∥E[A]∥ < 1,

Lemma 1. We have ∥E[A]∥ < 1.

completing the proof.

Proof of Lemma 1. First note that E[A] = T1 T2 . It is obvious that T1 as a diagonal matrix has eigenvalues 1 − β/r and 1, and thus ∥T1 ∥ = 1. Also, T2 commutes with L and has eigenvalues λi (T2 ) = 1 −

n X

First, let us use the regularization trick to introduce a regularized version of the Laplacian L as

α λn+1−i (L) m

with 0 = λ1 (L) < λ2 (L) ≤ · · · ≤ λn (L). Recall that since we consider a connected network, there is only one eigenvalue of L that is exactly equal to 0. The maximal eigenvalue λn (L) can be upper bounded by

λn (L) <

Appendix B: Derivation of Eq. (14) and discussions

λi (L) = Tr(L) =

n X

di = 2m,

i=1

i=1

which implies that λ1 (T2 ) > 1 − 2α > −1 as α ∈ (0, 1) in our setting. Summarizing, we have

L̃ = L + ϵIn , where ϵ is a small constant. Unlike the original L, such a regularized L̃ is invertible, but it shares the same set of ˜ by replacing eigenvectors of L. We also denote T̃2 and E[A] L with L̃ in T2 and E[A], respectively. The introduction of the regularization makes the following analysis convenient (as matrices involved are invertible) and restores the original setting by letting ϵ → 0. It is straightforward to verify that this does not lead to any pathological behavior that would invalidate the approach. We then deal with the matrix inversion in Eq. (13). Note that α β L̃ + U U T T̃2 m  r  mβ −1 α L̃ U U T T̃2 . = L̃ In + m αr

In − E[Ã] = −1 < λ1 (T2 ) ≤ · · · ≤ λn−1 (T2 ) < λn (T2 ) = 1 = ∥T2 ∥. Since the operator norm is submultiplicative, we have ∥E[A]∥ ≤ ∥T1 ∥ × ∥T2 ∥ = 1. However, if the upper bound 1 of ∥E[A]∥ can be attained, then it is necessary that there exists a vector v∗ such that

(In − E[Ã])

−1 mβ −1 L̃ U U T T̃2 αr  −1 mβ −1 mβ T −1 L̃ U Ir + U T̃2 L̃ U = In − U T T̃2 . αr αr 

In +

Therefore, (In − E[Ã])−1 U can be calculated as

v∗ = vn (T1 ) = vn (T2 ).

−1

By the Woodbury formula, we have

!  −1 mβ T −1 T Ir + U T̃2 L̃ U U T̃2 L̃−1 U αr  −1   m −1 m −1 mβ T mβ T −1 −1 = L̃ U − L̃ U Ir + U T̃2 L̃ U U T̃2 L̃ U α α αr αr  −1 ! m −1 mβ T (∗) m −1 = L̃ U − L̃ U Ir − Ir + U T̃2 L̃−1 U α α αr  −1 m −1 mβ T −1 = L̃ U Ir + U T̃2 L̃ U , α αr

m U= α

mβ −1 In − L̃ U αr

(B1)

where (∗) is due to the fact that (I + M )−1 M = I − (I + M )−1 , which can be directly verified by left multiplying (I + M )

14 to both sides. To proceed, we use the spectral decomposition of L̃: L̃ =

n X

Then we rewrite M̃ as M̃ =

λi (L̃)vi viT ,

i=1

Again, by the Woodbury formula, we have

where {vi } is a set of orthonormal eigenvector of L and

mβ −1 R̃ v̂1 v̂ T R̃−1 , M̃ −1 = R̃−1 − αnϵ mβ T 1 1 + αnϵ v̂1 R̃−1 v̂1

λi (L̃) = λi + ϵ with λi being short for √ λi (L), the ith smallest eigenvalue of L. Note that 1n = nv1 . We thus have −1 1T = n L̃

√ 1 √ T T n T 1T nv1 vi vi = v1 = n , λ +ϵ λ1 + ϵ ϵ i=1 i

n X

where we have used the fact that v1T vi = δ1i and λ1 = 0. Hence, −1 1T U= n L̃

1T 1T nU = r. ϵ ϵ

(B2)

Also, note that  α α  T̃2 L̃−1 = In − L̃ L̃−1 = L̃−1 − In m m

α U T T̃2 L̃−1 U = U T L̃−1 U − Ir . m

mβ −1 v̂1 v̂1T R̃−1 m T −1 m T −1 m 1T r αnϵ R̃ 1r M̃ = 1r R̃ − mβ αϵ αϵ αϵ 1 + αnϵ v̂1T R̃−1 v̂1 mβ √ m T −1 m αrϵ nv̂1T R̃−1 v̂1 v̂1T R̃−1 = 1 R̃ − mβ T −1 αϵ r αϵ 1 + αnϵ v̂1 R̃ v̂1   mβ T −1 T −1 v̂ R̃ v̂ 1 1r R̃ m T −1 m αnϵ 1   = 1 R̃ − αϵ r αϵ 1 + mβ v̂ T R̃−1 v̂ 1 αnϵ 1 ! m T −1 m 1 −1 = 1 R̃ − 1− 1T r R̃ mβ T −1 αϵ r αϵ 1 + αnϵ v̂1 R̃ v̂1 m T −1 αϵ 1r R̃ . mβ T −1 v̂1 R̃ v̂1 1 + αnϵ

(B5)

By Eqs. (B4) and (B5), we have (B3)

Combining Eqs. (B1), (B2), and (B3), we arrive at ˜ −1 U 1T n (In − E[A])  −1 m T mβ  T −1 α  = 1r Ir + U L̃ U − Ir αϵ αr m   −1 β mβ T −1 m T 1 1− Ir + U L̃ U = αϵ r r αr m T −1 := 1 M̃ , αϵ r

which leads to

=

and U T U = Ir . It is straightforward to have

˜ −1 E[B]x0 1T n (In −E[A])    β T T −1 ˜ U x0 = 1n (In − E[A]) U r   m  β −1 = 1T U T x0 r M̃ αϵ r mβ T −1 T 1r R̃ U x0 = αϵr mβ 1 + αnϵ v̂1T R̃−1 v̂1 √1 v̂ T R̃−1 U T x0 r 1 . 1 T −1 v̂1 mβ + n v̂1 R̃

= αϵ

(B4)

where M̃ as defined above is clearly a full-rank r×r matrix. Applying the spectral decomposition of L̃−1 again, we find that !   n mβ T X vi viT β Ir + U U M̃ = 1 − r αr λ +ϵ i=1 i !   n T X mβ T β mβ v v i i = U v1 v1T U + 1 − Ir + UT U αrϵ r αr λ + ϵ i i=2 :=

mβ v̂1 v̂1T + R̃. αnϵ

mβ 1r 1T r + R̃. αnϵ r

Note that U T x0 is a vector of dimension r. We use the basis {v̂k } to expand it as U T x0 =

r X

ck v̂k ,

k=1

where ck = v̂kT U T x0 . In particular, Pr x0 (i) T T √ . c1 = v̂1 U x0 = i=1 r We then have

Note that all λi > 0 for i ̸= 1. Thus, the leading term of T mβ 1r 1r M̃ is αnϵ for small ϵ. Let {v̂1 , . . . , v̂r } be a set of fixed r orthonormal basis vectors (independent of ϵ) in Rr with v̂1 chosen as 1 v̂1 = √ 1r . r

˜ −1 E[B]x0 1T n (In −E[A]) Pr √1 v̂ T R̃−1 k=1 ck v̂k r 1 = αϵ 1 T −1 v̂1 mβ + n v̂1 R̃ P r ck T −1 c1 T −1 √ v̂ R̃ v̂1 + k=2 √ v̂ R̃ v̂k r 1 r 1 = . αϵ 1 T −1 v̂1 mβ + n v̂1 R̃

(B6)

15 Inserting the expression of c1 in Eq. (B6) and taking the limit ϵ → 0, we come to the conclusion that −1 y∞ = 1T E[B]x0 n (In − E[A]) r nc1 X nck v̂1T R−1 v̂k √ T −1 = √ + r r v̂1 R v̂1 k=2 r

r

X nck v̂ T R−1 v̂k nX √ 1T −1 , = x0 (i) + r i=1 r v̂1 R v̂1

(B7)

k=2

Thus, for small β, we can view R as a perturbation of the identity matrix Ir . Then R−1 can also be seen as a perturbation of Ir , and can be written as

where  R=

β 1− r



mβ T Ir + U αr

n X vi v T i

i=2

λi

! U.

R−1 = Ir − βS + o(β).

Clearly, R is positive definite. Hence, R−1 exists and is also positive definite, and Eq. (B7) is thus always valid. Moreover, this result does not depend on the specific choice of v̂2 , . . . , v̂r because r X

v̂k ck =

k X

To leading order in β, we have for k ̸= 1 that v̂1T Ir v̂k − βv̂1T Sv̂k v̂1T R−1 v̂k ≈ ≈ −βv̂1T Sv̂k v̂1T R−1 v̂1 v̂1T Ir v̂1 − βv̂1T Sv̂1 ! n m T T X vi viT U v̂k , = −β v̂1 U αr λ i=2

v̂k v̂kT U T x0 = (Ir − v̂1 v̂1T )U T x0 ,

r=2

k=2

So far, there have been no approximations made, and the result is rigorous. On the right-hand side of Eq. (B7), the dependence on β is via R−1 . We now investigate the situation when β is small. We may rewrite R as the sum of Ir and an additional term proportional to β. That is, R := Ir + βS, where ! n m T X vi viT Ir U− . U S= αr λ r i i=2

where we have used the fact that v̂1T βr Ir v̂k = 0 for k ̸= 1. Hence, for small β, we have

which is fixed once v̂1 is selected.

n −1 y∞ = 1T E[B]x0 = n (In − E[A])

r X

r

m X nck T T √ v̂1 U x0 (i) − β r i=1 αr r k=2

which is a more precise version of our first main result (14). Some discussions about the result are in order. First, what do we mean by β is small? Technically, we may require that the operator norm ∥βS∥ ≪ 1. Note that ! n X Ir m vi viT T ∥S∥ ≤ + U U r αr λi i=2 n X 1 m vi viT ≤ + ∥U T ∥ × × ∥U ∥ r αr λi i=2

=

m 1 + , r αrλ2

where the first step follows from the triangle inequality, and the second step is due to the submultiplicativity of the operator norm. Hence, we arrive at the sufficient condition (15). Second, there is an interesting special case where √ x0 (i) is the same for i = 1, . . . , r, i.e., U T x0 √= c1r = c rv̂1 is a constant vector. In this case, c1 = c r and ck = 0 for k ̸= 1, inserting which into Eq. (B7) yields r

y∞ = nc =

nX x0 (i). r k=1

This exact result shows that if all r nodes in the subset have the same initial state, then they are able to drive the

n X vi v T i

i=2

λi

! U v̂k + o(β),

(B8)

network to the desired state on average in the long-time limit, irrespective of the value of β.

Appendix C: Analysis of ∆t

We are interested in the regime where t ≫ 1 and β ≪ 1. As defined in the main text, ∆t = ∆t1 + ∆t2 . We first consider ∆t1 . In general, E[A] does not have a spectral decomposition. However, as defined above, E[A] = T1 T2 = −1/2 1/2 1/2 1/2 T1 (T1 T2 T1 )T1 , where T1 = In − βU U T /r and 1/2 1/2 T2 = In − αL/m. Hence E[A] is similar to T1 T2 T1 , and 1/2

1/2

1/2

−1/2

∥E[A]∥ ≤ ∥T1 ∥ × ∥T1 T2 T1 ∥ × ∥T1 s 1 1/2 1/2 = 1 × ∥T1 T2 T1 ∥ × 1 − βr   β 1/2 1/2 ≈ 1+ × ∥T1 T2 T1 ∥. 2r

∥

By similar arguments as in Appendix A, one can show that 1/2 1/2 the operator norm ∥T1 T2 T1 ∥ < 1. Hence, if we approx1/2 1/2 imate E[A] by T1 T2 T1 , then the relative error is on the

16 Following the similar analysis, we also approximate ∆t2 for large t and small β as

order of O(β). Moreover, since 1/2

1/2

1/2

−1/2

(T1 T2 )t = T1 (T1 T2 T1 )t T1

,

we similarly have that the relative error incurred by using 1/2 1/2 (T1 T2 T1 )t to approximate E[A]t is also O(β). 1/2

1/2

As a real symmetric matrix, (T1 T2 T1 )t can be written as 1/2

1/2

(T1 T2 T1 )t =

n X

µti ui uT i,

i=1 1/2

1/2

where {µi }i∈[n] are the eigenvalues of T1 T2 T1 and {ui }i∈[n] are the corresponding orthonormal eigenvectors. The mode associated with the largest |µi | dominates for large t. We assume the truncation error (which depends on the spectrum of L) at a finite but large enough t is negligible and do not contain it in the following discussion. 1/2 Since in the case of a small β, T1 =  qwe are interested 1 − βr − 1 U U T can be seen as a perturbation of In + 1/2

1/2

In , and T1 T2 T1 1/2

1/2

T1 T2 T1

can be seen as a perturbation of T2 : r

≈ T2 +

1−

β −1 r

! U U T T2 + T2 U U T

β ≈ T2 − (U U T T2 + T2 U U T ), 2r where we have omitted higher-order terms in β. Let {λi }i∈[n] be the set of eigenvalues of the Laplacian matrix L and {vi }i∈[n] be the set of corresponding eigenvectors. Then we can approximate the eigenvalues {µi }i∈[n] as   β αλi α  − viT U U T In − L vi m 2r m β T α  − vi In − L U U T vi + o(β). 2r m

 µi =

1−

1n Notice that λ1 = 0 and v1 = √ . We expect that when β n is sufficiently small, the largest |µi | is equal to

β T β µn ≈ 1 − 1n U U T 1n = 1 − , nr n where we have used the fact that L1n = 0n×1 . Similarly, the corresponding eigenvector is approximated by v1 up to a term ∼ O(β). Hence, we conclude that, to leading order in β,  ∆t1 ≈

β 1− n

t

T 1T n v1 v1 x 0 =



β 1− n

t

1T n x0 .

This approximation of ∆t1 behaves well when the spectral gap of L is not too small, i.e., when λ2 is not too close to 0. Now, let us consider ∆t2 . Note that E[A]t−1 + · · · + In = (In − E[A])−1 (In − E[A]t ).

−1 ∆t2 = −1T E[A]t E[B]x0 n (In − E[A]) ! n X µti T T ≈ −1n ui ui E[B]x0 1 − µi i=1

µtn β T un uT n U U x0 1 − µn r β (1 − β/n)t T 1n U U T x0 ≈− r β/n !  t r β nX =− 1− x0 (k) . n r ≈ −1T n

k=1

Combining the results for ∆t1 and ∆t2 , we have that ! t X  r n nX β x0 (k) x0 (i) − ∆t ≈ 1 − n r i=1 k=1  t β ≈ 1− ∆0 . (C1) n We expect this approximation to be reasonably accurate for fairly large λ2 and when t ≫ 1 and β ≪ 1. For future reference, we note that 1T n E[xt ] = ∆t + y∞   t n t ! X r β X β n ≈ 1− x0 (i) + 1 − 1 − x0 (k) n i=1 n r k=1  t  t ! β β n Tβ T = 1− 1 U U T x0 1n x0 + 1 − 1 − n n β nr  t  t ! β β n T T = 1− 1n x0 + 1 − 1 − 1 E[B]x0 n n β n  t t−1−τ t−1  X β β T = 1− 1n x0 + 1T 1− n E[B]x0 . (C2) n n τ =0 Appendix D: Probabilistic bounds for Yt

In this appendix, we aim to bound the (absolute) differT ence |Yt − yt | = |1T n xt − 1n E[xt ]| with high probability, in an informative way. On a high level, we aim to show that Yt is a sub-Gaussian random variable and then provide an (approximate) sub-Gaussian parameter associated with it. Such a parameter can be used to construct an interval that covers yt with high probability, and it is informative in the sense that it explicitly depends on β. To this end, we will argue that the resetting-swapping dynamics considered in this work can be approximated by an effective one when t is large and β is small, in which the randomness can be handled more easily than in the original problem. By doing so, we sacrifice a bit of mathematical rigor, but gain clearer physical intuition, which captures the main feature of the process in a typical setting. Note that, in order to calculate Yt , we encounter terms in the form of 1T n At−1 . . . Aτ . To ease the notation, we

17 denote Rτ = ekτ eT kτ

T

and Sτ = (eiτ − ejτ )(eiτ − ejτ ) .

Since 1T n Sτ v = 0 for a generic vector v, we have T 1T n At−1 = 1n (In − βRt−1 − αSt−1 + αβRt−1 St−1 )

= 1T n (In − βRt−1 + αβRt−1 St−1 ). Pn √ Recall that nv1 = 1n and i=1 vi viT = In . Thus, ! n X T T 1n (In − βRt−1 + αβRt−1 St−1 ) vi vi =

where ω and b are two vectors of dimension t. Note that in this approximate expression for Yt − yt , the randomness only originates from Bτ . This is equivalent to an effective dynamics, which can be seen as a weighted sum of the resetting dynamics at each time step, and the weights decay exponentially with the temporal distance of each resetting event from the present. In the following, we will establish that ω T b is a subGaussian random variable. Recall that, by definition, a sub-Gaussian random variable X satisfies [47] 2

√

nv1T (In − βRt−1 + αβRt−1 St−1 )v1 v1T n X √ T + nv1 (In − βRt−1 + αβRt−1 St−1 )vi viT . i=2

Again, note that v T St−1 v1 = 0 for a generic v and that for each i ̸= 1, we have |v1T (In −βRt−1 + αβRt−1 St−1 )vi | = |β(−v1T Rt−1 vi + αv1T Rt−1 St−1 vi )| √ β(1 + 2α) √ . ≤ n

2

E[es(X−E[X]) ] ≤ es σ /2 for all s ∈ R,

i=1

where σ 2 is a constant. We might denote X ∼ subG(σ 2 ). It is well known that all bounded random variables are subGaussian. In particular, if X ∈ [a, b] almost surely, then  2 ! b−a X ∼ subG . 2 A sub-Gaussian random variable X ∼ subG(σ 2 ) is typically not too far away from its mean E[X], as quantified by the following concentration inequality [47]:   ε2 P (|X − E[X]| > ε) ≤ 2 exp − 2 2σ

Hence, for a unit vector v, we obtain
T T |1T n At−1 v − v1 (In − βRt−1 )v1 1n v| √ n X √ √ √ β(1 + 2α) T √ ≤ n |vi v| ≤ β(1 + 2α) n − 1 n i=2 √ = O(β n). √ It is sufficient that, if β n ≪ 1, one can approximate   then T T 1T n At−1 by v1 (In − βRt−1 )v1 1n reasonably well, and β , n which is deterministic and does not depend on the specific time t − 1. However, we do not only want to approximate 1T n At−1 by keeping only the term associated with v1 ; we also expect a similar approximation to be valid for 1T n At−1 . . . Aτ . That is,  t−τ β 1T A . . . A ≈ 1 − 1T t−1 τ n n. n v1T (In − βRt−1 )v1 = v1T (In − βekt−1 eT kt−1 )v1 = 1 −

A more precise error analysis is awaited, but the above approximation captures the “first order” behavior. Based on this idea, the calculation for an approximate 1T n xt is straightforward based on an effective dynamics:  t t−1−τ t−1  X β β T 1T x ≈ 1 − 1 x + 1 − 1T n t n 0 n Bτ x0 . n n τ =0 Thus, by Eq. (C2), the fluctuation of 1T n xt around its mean 1T E[x ] is approximately t n t−1−τ t−1  X β T 1T (Bτ − E[B])x0 1T x − 1 E[x ] ≈ 1 − t n t n |n {z } n τ =0 | {z } :=b(τ +1) :=ω(τ +1)

T

:= ω b,

for all ε > 0. For each i ∈ [t] and τ = i − 1, one can directly verify that ! r βX T T T b(i) = 1n βekτ ekτ − ek ek x0 r k=1  Pr  k=1 x0 (k) = βx0 (kτ ) − β r Pr   k=1 x0 (k) . ≤ β max x0 (k) − r k∈[r] Similarly, we also have Pr   k=1 x0 (k) . b(i) ≥ β min x0 (k) − r k∈[r] Hence, for all i ∈ [t], b(i) is bounded and thus sub-Gaussian: b(i) ∼ subG(β 2 σr2 ), where σr =

1 2



 max x0 (k) − min x0 (k) . k∈[r]

k∈[r]

Note that b(i)’s are independent. So ω T b is the weighted sum of t independent sub-Gaussian random variables, and it is also sub-Gaussian with ω T b ∼ subG(∥ω∥2 β 2 σr2 ). This can be verified by noticing that, for all s ∈ R, T

T

T

E[es(ω b−ω E[b]) ] = E[esω b ] =

t Y i=1

≤

t Y i=1

2

2

2

2

2

2

2

2

es ωi β σr /2 = es ∥ω∥ β σr /2 .

E[esωi bi ]

18 Applying the tail probability bound for sub-Gaussian random variables [47], we have 
T P |1T x − 1 E[x ]| > ε ≤ 2 exp − t t n n

ε2 2∥ω∥2 β 2 σr2



for all ε > 0. Finally, note that

2

∥ω∥ =

t−1  X τ =0

β 1− n

t−1−τ !2 =

t−1  X τ =0

1−

β n

2τ

1 − (1 − β/n)2t = . 1 − (1 − β/n)2 Since we are interested in the large-t and then small-β regime, we have ∥ω∥2 ≈

n . 2β

[1] C. Külske, The Ising model: highlights and perspectives, Math. Phys. Anal. Geom. 28, 20 (2025). [2] M. Mobilia, Does a single zealot affect an infinite group of voters?, Phys. Rev. Lett. 91, 028701 (2003). [3] P. Clifford and A. Sudbury, A model for spatial conflict, Biometrika 60, 581 (1973). [4] R. A. Holley and T. M. Liggett, Ergodic theorems for weakly interacting infinite systems and the voter model, Ann. Probab. 3, 643 (1975). [5] C. Castellano, S. Fortunato, and V. Loreto, Statistical physics of social dynamics, Rev. Mod. Phys. 81, 591 (2009). [6] M. Starnini, A. Baronchelli, and R. Pastor-Satorras, Ordering dynamics of the multi-state voter model, J. Stat. Mech. 2012, P10027 (2012). [7] G. A. Böhme and T. Gross, Fragmentation transitions in multistate voter models, Phys. Rev. E 85, 066117 (2012). [8] M. H. DeGroot, Reaching a consensus, J. Am. Stat. Assoc. 69, 118 (1974). [9] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, Next century challenges: Scalable coordination in sensor networks, in Proc. ACM/IEEE Int. Conf. Mobile Comput. Netw. (MobiCom) (1999) pp. 263–270. [10] W. R. Heinzelman, J. Kulik, and H. Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, in Proc. ACM/IEEE Int. Conf. Mobile Comput. Netw. (MobiCom) (1999) pp. 174–185. [11] C. Sengul, M. J. Miller, and I. Gupta, Adaptive probabilitybased broadcast forwarding in energy-saving sensor networks, ACM Trans. Sensor Netw. 4, 1 (2008). [12] A. Lalitha, S. Shekhar, T. Javidi, and F. Koushanfar, Fully decentralized federated learning, in Third workshop on Bayesian deep learning at NeurIPS, Vol. 12 (2018). [13] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent, Adv. Neural Inf. Process. Syst. (NeurIPS) 30 (2017). [14] I. Hegedűs, G. Danner, and M. Jelasity, Gossip learning as a decentralized alternative to federated learning, in IFIP Int. Conf. Distrib. Appl. Interoper. Syst. (Springer, 2019) pp. 74–90.

In this case, the tail probability is approximately bounded by  
ε2 T P |1T x − 1 E[x ]| > ε ≲ 2 exp − . t n t n nβσr2 Let the right-hand side be equal to δ ∈ (0, 1). Then the result can be equivalently reinterpreted: with probability roughly as high as 1 − δ, we have s   2 T T |1n xt − 1n E[xt ]| ≤ nβ ln σr . δ T Moreover, if we require that |1T n xt − 1n E[xt ]| ≤ ε with probability 1 − δ, where both ε > 0 and δ ∈ (0, 1) are prescribed, then we need

β≤

ε2 n ln

2 δ

σr2

.

[15] L. Yuan, Z. Wang, L. Sun, P. S. Yu, and C. G. Brinton, Decentralized federated learning: A survey and perspective, IEEE Internet Things J. 11, 34617 (2024). [16] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Randomized gossip algorithms, IEEE Trans. Inf. Theory 52, 2508 (2006). [17] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Gossip algorithms: Design, analysis and applications, in Proc. IEEE Joint Conf. Comput. Commun. Soc. (INFOCOM), Vol. 3 (2005) pp. 1653–1664. [18] D. Kempe, J. Kleinberg, and A. Demers, Spatial gossip and resource location protocols, J. ACM 51, 943 (2004). [19] Z. J. Haas, J. Y. Halpern, and L. Li, Gossip-based ad hoc routing, in Proc. IEEE Joint Conf. Comput. Commun. Soc. (INFOCOM), Vol. 3 (2002) pp. 1707–1716. [20] M. Jelasity, A. Montresor, and O. Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Trans. Comput. Syst. 23, 219 (2005). [21] R. J. Baxter, Exactly Solved Models in Statistical Mechanics (Elsevier, 2016). [22] M. Newman, Networks (Oxford University Press, 2018). [23] R. Olfati-Saber, J. A. Fax, and R. M. Murray, Consensus and cooperation in networked multi-agent systems, Proc. IEEE 95, 215 (2007). [24] S. H. Strogatz, From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators, Physica D 143, 1 (2000). [25] A.-L. Barabási, Network science, Phil. Trans. R. Soc. A 371, 20120375 (2013). [26] D. Shah, Gossip algorithms, Found. Trends Netw. 3, 1 (2009). [27] D. Kempe, A. Dobra, and J. Gehrke, Gossip-based computation of aggregate information, in IEEE Symp. Found. Comput. Sci. (FOCS) (2003) pp. 482–491. [28] L. Mazzarella, A. Sarlette, and F. Ticozzi, Consensus for quantum networks: Symmetry from gossip interactions, IEEE Trans. Autom. Control 60, 158 (2015). [29] R. Olfati-Saber and R. M. Murray, Consensus problems in networks of agents with switching topology and timedelays, IEEE Trans. Autom. Control 49, 1520 (2004).

19 [30] R. Carli, A. Chiuso, L. Schenato, and S. Zampieri, A PI consensus controller for networked clocks synchronization, IFAC Proc. Vol. 41, 10289 (2008). [31] L. Schenato and F. Fiorentin, Average timesynch: A consensus-based protocol for clock synchronization in wireless sensor networks, Automatica 47, 1878 (2011). [32] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. 3, 1 (2011). [33] A. Nedic and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control 54, 48 (2009). [34] S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, Tinydb: an acquisitional query processing system for sensor networks, ACM Trans. Database Syst. 30, 122 (2005). [35] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera y Arcas, Communication-efficient learning of deep networks from decentralized data, in Proc. Mach. Learn. Res. (2017) pp. 1273–1282. [36] A. Pal and S. Reuveni, First Passage under Restart, Phys. Rev. Lett 118, 030603 (2017). [37] R. K. Singh, R. Metzler, and T. Sandev, Competing random searchers under restarts (2024), arXiv:2409.09390. [38] A. Biswas, A. Kundu, and A. Pal, Search with stochastic home returns can expedite classical first passage under resetting, Phys. Rev. E 110, L042101 (2024).

[39] S. Belan, Restart Could Optimize the Probability of Success in a Bernoulli Trial, Phys. Rev. Lett. 120, 080601 (2018). [40] R. Singh, T. Sandev, and S. Singh, Bernoulli trial under restarts: A comparative study of resetting transitions, Phys. Rev. E 108, L052106 (2023). [41] B. De Bruyne, J. Randon-Furling, and S. Redner, Optimization in First-Passage Resetting, Phys. Rev. Lett. 125, 050602 (2020). [42] Y. Xu, M. Deng, X. Cheng, Y. Tian, Z. Liu, and T. Jaakkola, Restart sampling for improving generative processes, Adv. Neural Inf. Process. Syst. (NeurIPS) 36, 76806 (2023). [43] N. E. Friedkin and E. C. Johnsen, Social influence and opinions, J. Math. Sociol. 15, 193 (1990). [44] J. Ghaderi and R. Srikant, Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate, Automatica 50, 3209 (2014). [45] Y. Xing and K. H. Johansson, Concentration in gossip opinion dynamics over random graphs, SIAM J. Control Optim. 62, 1521 (2024). [46] L. Wang, Y. Xing, and K. H. Johansson, On final opinions of the Friedkin-Johnsen model over random graphs with partially stubborn community, in Proc. IEEE Conf. Decision and Control (CDC) (2024) pp. 4562–4567. [47] R. van Handel, Probability in high dimension, Lecture Notes (Princeton University) (2014). [48] P. Erdös and A. Rényi, On random graphs I, Publ. Math. Debrecen 6, 18 (1959). [49] A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286, 509 (1999).

Related documents

• Approximating Random Walks in $\widetilde{O}(\log n + \log^2 κ)$ Space for $κ$-Conditioned Graphs#1215882
• Estimation and Recovery of a Planted Dense Subgraph from a Single Network Cascade#1218558
• Optimal Sampling and Transmission Policy for Information Freshness in Gossip Networks#1605184
• Subgraph Counting with Local Node Differential Privacy#1357933
• Subgraph Counting with Local Node Differential Privacy#1348761