Event-Triggered Quantized Average Consensus via Mass Summation
Apostolos I. Rikos Christoforos N. Hadjicostis
eess.SY cs.SY























Event-Triggered Quantized Average Consensus via Mass Summation
    Apostolos I. Rikos, Member, IEEE
	Apostolos I. Rikos is with Division of Decision and Control Systems, KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden. E-mail: rikos@kth.se., 
Christoforos N. Hadjicostis, Fellow, IEEE 
	Christoforos N. Hadjicostis is with the Department of Electrical and Computer Engineering at the University of Cyprus, Nicosia, Cyprus, and also with the Department of Electrical and Computer Engineering at the University of Illinois, Urbana-Champaign, IL, USA. E-mail: chadjic@ucy.ac.cy.
	Parts of the results for quantized average consensus via event-triggered mass summation appear in <cit.>. The present version of the paper includes complete proofs for convergence as well as an enhanced version of the algorithm that allows nodes to determine when to seize transmissions, once quantized average consensus is reached (not addressed in <cit.>).

    December 30, 2023
========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================

empty
empty






We study the distributed average consensus problem in multi-agent systems with directed communication links that are subject to quantized information flow. 
The goal of distributed average consensus is for the nodes, each associated with some initial value, to obtain the average (or some value close to the average) of these initial values. 
In this paper, we present and analyze novel distributed averaging algorithms which operate exclusively on quantized values (specifically, the information stored, processed and exchanged between neighboring agents is subject to deterministic uniform quantization) and rely on event-driven updates (e.g., to reduce energy consumption, communication bandwidth, network congestion, and/or processor usage). 
We characterize the properties of the proposed distributed averaging protocols on quantized values and show that their execution, on any time-invariant and strongly connected digraph, will allow all agents to reach, in finite time, a common consensus value represented as the ratio of two quantized values that is equal to the exact average. 
We conclude with examples that illustrate the operation, performance, and potential advantages of the proposed algorithms. 




Quantized average consensus, digraphs, event-triggered distributed algorithms, quantization, multi-agent systems. 



















§ INTRODUCTION



In recent years, there has been a growing interest for control and coordination of networks consisting of multiple agents, like groups of sensors <cit.> or mobile autonomous agents <cit.>. 
A problem of particular interest in distributed control is the consensus problem where the objective is to develop distributed algorithms that can be used by a group of agents in order to reach agreement to a common decision. 
The agents start with different initial values/information and are allowed to communicate locally via inter-agent information exchange under some constraints on connectivity. 
Consensus processes play an important role in many problems, such as leader election <cit.>,  motion coordination of multi-vehicle systems <cit.>, and clock synchronization <cit.>.






One special case of the consensus problem is distributed averaging, where each agent (initially endowed with a numerical value) can send/receive information to/from other agents in its neighborhood and update its value iteratively, so that eventually, all agents compute the average of all initial values. 
Average consensus is an important problem and has been studied extensively in settings where each agent processes and transmits real-valued states with infinite precision <cit.>. 



Most existing algorithms, for average consensus (and also consensus) provide asymptotic convergence to the consensus value and cannot be directly applied to real-world control and coordination applications.
For this reason there has been interest on finite time (average) consensus algorithms (e.g., <cit.>) but the challenge of designing simple finite time algorithms for these tasks remains open. 
Furthermore, in practice, due to constraints on the bandwidth of communication links and the capacity of physical memories, both communication and computation need to be performed assuming finite precision.
For these reasons, researchers have also studied the case when network links can only allow messages of limited length to be transmitted between agents, effectively extending techniques for average consensus towards the direction of quantized consensus.
Various distributed strategies have been proposed, to allow the agents in a network to reach quantized consensus <cit.>. 
Apart from <cit.> (which converges in a deterministic fashion but requires a communication topology that forms a doubly stochastic matrix), these existing strategies use randomized approaches to address the quantized average consensus problem (implying that all agents reach quantized average consensus with probability one or in some other probabilistic sense); the design of deterministic distributed strategies that achieve quantized average consensus remains largely unexplored. 
An additional desirable feature in many types of communication networks is the infrequent update of values to avoid consuming valuable network resources. 
Thus, there has also been an increasing interest for novel event-triggered algorithms for distributed quantized average consensus (and, more generally, distributed control), in order to achieve more efficient usage of network resources <cit.>.



















In this paper, we present three novel distributed average consensus algorithms that combine the desirable features mentioned above. 
More specifically, average consensus is reached in finite time, and the processing, storing, and exchange of information between neighboring agents is subject to uniform quantization and “event-driven”. 
Following <cit.> we assume that the states are integer-valued (which comprises  a uniform class of quantization effects) and the control actuation of each node is event-based. 
We note that most work dealing with quantization has concentrated on the scenario where the agents can store and process real-valued states but can transmit only quantized values through limited rate channels (see, e.g., <cit.>). 
By contrast, our assumption is also suited to the case where the states are stored in digital memories of finite capacity (as in <cit.>) as long as the initial values are also quantized. 
The paper establishes that the proposed algorithms allow all agents to reach quantized average consensus in finite time by reaching a value represented as the ratio of two integer values that is equal to the average. 
In the case of the probabilistic algorithm we present, this ratio equals the average in finite time with probability one.


The remainder of this paper is organized as follows. 
In Section <ref> we review the existing literature related to our work while in Section <ref>, we introduce the notation used throughout the paper.
In Section <ref> we formulate the quantized average consensus problem.
In Section <ref>, we present a probabilistic distributed algorithm, which allows the agents to reach consensus to the exact quantized average of the initial values with probability one. 
In Section <ref>, we present a deterministic event-triggered version of the algorithm in Section <ref>, and show that it reaches consensus to the exact quantized average of the initial values after a finite number of steps, for which we also provide a worst case upper bound.  
In Section <ref>, we present a deterministic event-triggered distributed algorithm, which, not only allows the agents to reach consensus to the exact quantized average of the initial values after a finite number of steps, but also allows them to cease transmissions once quantized average consensus is reached. 
For each proposed algorithm, we analyze the operation and establish convergence to the quantized average of the initial values. 
In Section <ref>, we present simulation results and comparisons. 
We conclude in Section <ref> with a brief summary and remarks about future work.












§ LITERATURE REVIEW


In this section, we review existing literature on algorithms for distributed averaging under quantized communication, depending on whether they converge in a probabilistic or a deterministic fashion. 

In recent years, quite a few probabilistic distributed algorithms for averaging under quantized communication, have been proposed. 
Specifically, the probabilistic quantizer in <cit.> converges to a common value with a random quantization level for the case where the topology forms a directed graph. 
In <cit.> the authors present a distributed algorithm which adds a dither over the agents' measurements (before the quantization process) and they show that the mean square error can be made arbitrarily small. 
In <cit.> the authors present a distributed algorithm which guarantees all agents to reach a consensus value on the interval in which the average lies after a finite number of time steps. 
In <cit.> the authors present a quantized gossip algorithm which deals with the distributed averaging problem over a connected weighted graph, and calculate lower and upper bounds on the expected value of the convergence time, which depend on the principal submatrices of the Laplacian matrix of the weighted graph.


The available literature concerning deterministic distributed algorithms for averaging under quantized communication, comprises less publications. 
In <cit.> the authors present a distributed averaging algorithm with dynamic encoding and
decoding schemes. 
They show that for a connected undirected dynamic graph, average consensus is achieved asymptotically with
as few as one bit of information exchange between each pair of adjacent agents at each time step, and the 
convergence rate is asymptotic and depends on the number of network nodes, the number of quantization levels and the synchronizability of the network.
In <cit.> the authors present a novel quantization scheme for solving the average consensus problem when sensors exchange quantized state information. 
The proposed scheme is based on progressive reduction of the range of a uniform quantizer and it leads to progressive refinement of the information exchanged by the sensors.
In <cit.> the authors derive bounds on the rate of convergence to average consensus for a team of mobile agents exchanging information over time-invariant and randomly time-varying communication networks with symmetries. 
Furthermore, they study the control performance when agents also exchange logarithmically quantized data in static communication topologies with symmetries.
In <cit.> the authors study distributed algorithms for the averaging problem over networks with time-varying topology, with a focus on tight bounds on the convergence time of a general class of averaging algorithms.
They consider algorithms for the case where agents can exchange and store continuous or quantized values, establish a tight convergence rate, and show that these algorithms guarantee convergence within some error from the average of the initial values; this error depends on the number of quantization levels. 


Finally, recent papers have studied the quantized average consensus problem with the additional constraint that the state of each node is an integer value. 
In <cit.> the authors present a probabilistic algorithm which allows every agent to reach quantized consensus almost surely for a static and undirected communication topology, while in <cit.> and <cit.> they analyze and further improve its convergence rate. 
In <cit.> a probabilistic algorithm was proposed to solve the quantized consensus problem for static directed graphs for the case where the agents exchange quantized information and store the changes of their states in an additional (also quantized) variable called `surplus'. 
In <cit.> the authors present a deterministic distributed averaging protocol subject to quantization on the links and show that, depending on initial conditions, the system either converges in finite time to a quantized consensus, or the nodes' enter into a cyclic behaviour with their values oscillating around the average.












§ NOTATION AND MATHEMATICAL BACKGROUND


The sets of real, rational, integer and natural numbers are denoted by ℝ, ℚ, ℤ and ℕ, respectively. 
The symbol ℤ_+ denotes the set of nonnegative integers. 




Consider a network of n (n ≥ 2) agents communicating only with their immediate neighbors. 
The communication topology can be captured by a directed graph (digraph), called communication digraph. 
A digraph is defined as 𝒢_d = (𝒱, ℰ), where 𝒱 =  {v_1, v_2, …, v_n} is the set of nodes (representing the agents) and ℰ⊆𝒱×𝒱 - { (v_j, v_j)  |  v_j ∈𝒱} is the set of edges (self-edges excluded). 
A directed edge from node v_i to node v_j is denoted by m_ji≜ (v_j, v_i) ∈ℰ, and captures the fact that node v_j can receive information from node v_i (but not the other way around). 
We assume that the given digraph 𝒢_d = (𝒱, ℰ) is strongly connected (i.e., for each pair of nodes v_j, v_i ∈𝒱, v_j ≠ v_i, there exists a directed path[A directed path from v_i to v_j exists if we can find a sequence of vertices v_i ≡ v_l_0,v_l_1, …, v_l_t≡ v_j such that (v_l_τ+1,v_l_τ) ∈ℰ for τ = 0, 1, … , t-1.] from v_i to v_j). 
The subset of nodes that can directly transmit information to node v_j is called the set of in-neighbors of v_j and is represented by 𝒩_j^- = { v_i ∈𝒱  |   (v_j,v_i)∈ℰ}, while the subset of nodes that can directly receive information from node v_j is called the set of out-neighbors of v_j and is represented by 𝒩_j^+ = { v_l ∈𝒱  |   (v_l,v_j)∈ℰ}. 
The cardinality of 𝒩_j^- is called the in-degree of v_j and is denoted by 𝒟_j^- (i.e., 𝒟_j^- = | 𝒩_j^- |), while the cardinality of 𝒩_j^+ is called the out-degree of v_j and is denoted by 𝒟_j^+ (i.e., 𝒟_j^+ = | 𝒩_j^+ |). 


We assume that each node is aware of its out-neighbors and can directly (or indirectly[Indirect transmission could involve broadcasting a message to all out-neighbors while including in the message header the ID of the out-neighbor it is intended for.]) transmit messages to each out-neighbor; however, it cannot necessarily receive messages (at least not directly) from them. 
In the randomized version of the protocol, each node v_j assigns a nonzero probability b_lj to each of its outgoing edges m_lj (including a virtual self-edge), where v_l ∈𝒩^+_j ∪{ v_j }. 
This probability assignment can be captured by a column stochastic matrix ℬ = [b_lj]. 
A very simple choice[Note that this choice of nonzero probabilities is not unique. In fact, any positive values for the probabilities b_lj, for v_l ∈𝒩_j^+ ∪{ v_j }, subject to the constraint that they sum to one, is also possible for the type of algorithms we discuss.] would be to set  

    b_lj = {[ 1/1 + 𝒟_j^+,             ;           0,              ].

Each nonzero entry b_lj of matrix ℬ represents the probability of node v_j transmitting towards the out-neighbor v_l ∈𝒩^+_j through the edge m_lj, or performing no transmission[From the definition of ℬ = [b_lj] we have that b_jj = 1/1 + 𝒟_j^+, ∀ v_j ∈𝒱. This represents the probability that node v_j will not perform a transmission to any of its out-neighbors v_l ∈𝒩^+_j (i.e., it will transmit to itself).].


In the deterministic version of the protocol, each node v_j assigns a unique order in the set {0,1,..., 𝒟_j^+ -1} to each of its outgoing edges m_lj, where v_l ∈𝒩^+_j. 
More specifically, the order of link (v_l,v_j) for node v_j is denoted by P_lj (such that {P_lj  |   v_l ∈𝒩^+_j} = {0,1,..., 𝒟_j^+ -1}). 
This unique predetermined order is used during the execution of the proposed distributed algorithm as a way of allowing node v_j to transmit messages to its out-neighbors in a round-robin[When executing the deterministic protocol, each node v_j transmits to its out-neighbors, one at a time, by following a predetermined order. The next time it transmits to an out-neighbor, it continues from the outgoing edge it stopped the previous time and cycles through the edges in a round-robin fashion according to the predetermined ordering.] fashion. 





§ PROBLEM FORMULATION


Consider a strongly connected digraph 𝒢_d = (𝒱, ℰ), where each node v_j ∈𝒱 has an initial (i.e., for k=0) quantized value y_j[0] (for simplicity, we take y_j[0] ∈ℤ). 
In this paper, we develop a distributed algorithm that allows nodes (while processing and transmitting quantized information via available communication links between nodes) to eventually obtain, after a finite number of steps, a fraction q^s which is equal to the average q of the initial values of the nodes, where

    q = ∑_l=1^ny_l[0]/n .




Following <cit.> we assume that the state of each node is integer valued. 
This abstraction subsumes a class of quantization effects (e.g., uniform quantization).



The algorithms we develop are iterative. 
With respect to quantization of information flow, we have that at time step k ∈ℤ_+ (where ℤ_+ is the set of nonnegative integers), each node v_j ∈𝒱 maintains the state variables y^s_j, z^s_j, q_j^s, where y^s_j ∈ℤ, z^s_j ∈ℤ_+ and  q_j^s = y_j^s/z_j^s, and the mass variables y_j, z_j, where y_j ∈ℤ and z_j ∈ℤ_+.
The aggregate states are denoted by y^s[k] = [y^s_1[k]  ...  y^s_n[k]]^ T∈ℤ^n, z^s[k] = [z^s_1[k]  ...  z^s_n[k]]^ T∈ℤ_+^n, q^s[k] = [q^s_1[k]  ...  q^s_n[k]]^ T∈ℚ^n and y[k] = [y_1[k]  ...  y_n[k]]^ T∈ℤ^n, z[k] = [z_1[k]  ...  z_n[k]]^ T∈ℤ_+^n respectively. 

Following the execution of the proposed distributed algorithms, we argue that there exists k_0 so that for every k ≥ k_0 we have 

    y^s_j[k] = ∑_l=1^ny_l[0]/α  and  z^s_j[k] = n/α ,

where α∈ℕ. This means that 

    q^s_j[k] = (∑_l=1^ny_l[0]) / α/n / α = q ,

for every v_j ∈𝒱 (i.e., for k ≥ k_0 every node v_j has calculated q as the ratio of two integer values). 




















§ RANDOMIZED QUANTIZED AVERAGING WITH MASS SUMMATION


In this section we propose a distributed information exchange process in which the nodes, each having an integer initial value, transmit and receive quantized (integer) messages so that they reach average consensus on their initial values after a finite number of steps.




 §.§ Randomized Distributed Algorithm with Mass Summation



The operation of the proposed distributed algorithm is summarized below.

Initialization:
Each node v_j selects a set of probabilities { b_lj |  v_l∈𝒩_j^+ ∪{v_j}} such that 0 < b_lj < 1 and ∑_v_l∈𝒩_j^+ ∪{v_j} b_lj = 1 (see Section <ref>). 
Each value b_lj, represents the probability for node v_j to transmit towards out-neighbor v_l ∈𝒩^+_j (or perform a self transmission), at any given time step (independently between time steps and between nodes).  
Each node has some initial value y_j[0], and also sets its state variables, for time step k=0, as z_j[0] = 1, z^s_j[0] = 1 and y^s_j[0] = y_j[0], which means that q^s_j[0] = y_j[0] / 1. 




The iteration involves the following steps:

Step 1. Transmitting: According to the nonzero probabilities b_lj, assigned by node v_j during the initialization step, it either transmits z_j[k] and y_j[k] towards a randomly selected out-neighbor v_l ∈𝒩_j^+ or performs a self transmission. 
If it performs a transmission towards an out-neighbor v_l ∈𝒩_j^+, it sets y_j[k] = 0 and z_j[k] = 0.

Step 2. Receiving: Each node v_j may receive messages y_i[k] and z_i[k] from its in-neighbor v_i ∈𝒩_j^- or itself; it sums all such messages it receives (if any) along with its stored mass variables y_j[k] and z_j[k] as

    y_j[k+1] = y_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]y_i[k] ,

and 

    z_j[k+1] = z_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]z_i[k] ,

where w_ji[k] = 0 (or w_jj[k] = 0) if no message is received from in-neighbor v_i ∈𝒩_j^-; otherwise w_ji[k] = 1.


Step 3. Processing: 
If z_j[k+1] ≥ z^s_j[k], node v_j sets z^s_j[k+1] = z_j[k+1], y^s_j[k+1] = y_j[k+1] and 

    q^s_j[k+1] = y^s_j[k+1]/z^s_j[k+1] .

Then, k is set to k+1 and the iteration repeats (it goes back to Step 1). 




The proposed algorithm is essentially a probabilistic quantized mass transfer process and is detailed as Algorithm <ref> below (for the case when b_lj = 1/(1+𝒟_j^+) for v_l ∈𝒩_j^+ ∪{ v_j } and b_lj=0 otherwise). 
Due to space limitations we do not illustrate the operation of the proposed algorithm, however, an analytical illustration can be found in <cit.>. 



    
1
Probabilistic Quantized Average Consensus
Input 

 1) A strongly connected digraph 𝒢_d = (𝒱, ℰ) with n=|𝒱| nodes and m=|ℰ| edges. 

 2) For every v_j ∈𝒱 we have y_j[0] ∈ℤ. 


Initialization 

 Every node v_j ∈𝒱 does the following:

 1) It assigns a nonzero probability b_lj to each of its outgoing edges m_lj and its self-edge, where v_l ∈𝒩^+_j ∪{v_j}, as follows  

    b_lj = {[ 1/1 + 𝒟_j^+,             ;           0,              ].


 2) It sets z_j[0] = 1, z^s_j[0] = 1 and y^s_j[0] = y_j[0] (which means that q^s_j[0] = y_j[0] / 1). 


Iteration

 For k=0,1,2,…, each node v_j ∈𝒱 does the following:

 1) It either transmits y_j[k] and z_j[k] towards a randomly chosen out-neighbor v_l ∈𝒩_j^+ (according to the nonzero probability b_lj) or performs a self transmission (according to the nonzero probability b_jj). If it transmitted towards an out-neighbor, it sets y_j[k] = 0 and z_j[k] = 0.

 2) It receives y_i[k] and z_i[k] from its in-neighbors v_i ∈𝒩_j^- and sets 

    y_j[k+1] = y_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]y_i[k] ,

and 

    z_j[k+1] = z_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]z_i[k] ,

where w_ji[k] = 1 if node v_j receives values from node v_i (otherwise w_ji[k] = 0). 

 3) If the following condition holds,

    z_j[k+1] ≥ z^s_j[k],

it sets z^s_j[k+1] = z_j[k+1], y^s_j[k+1] = y_j[k+1], which means that q^s_j[k+1] = y^s_j[k+1]/z^s_j[k+1]. 

 4) It repeats (increases k to k + 1 and goes back to Step 1).












































































































































































From the operation of Algorithm <ref>, it is important to notice that, once the initial mass variables “merge” (i.e., Step 2 of the Iteration of Algorithm <ref>), they remain “merged” during the operation of Algorithm <ref>. 






 §.§ Finite Time Convergence Analysis



We are now ready to prove that during the operation of Algorithm <ref> each agent obtains two integer values y^s and z^s, the ratio of which is equal to the average q of the initial values of the nodes. 



Consider a strongly connected digraph 𝒢_d = (𝒱, ℰ) with n=|𝒱| nodes and m=|ℰ| edges, and z_j[0] = 1 and y_j[0] ∈ℤ for every node v_j ∈𝒱 at time step k=0. 
Suppose that each node v_j ∈𝒱 follows the Initialization and Iteration steps as described in Algorithm <ref>. 
Let 𝒱^+[k] ⊆𝒱 be the set of nodes v_j with positive mass variable z_j[k] at iteration k (i.e., 𝒱^+[k] = { v_j ∈𝒱  |   z_j[k] > 0 }). 
During the execution of Algorithm <ref>, for every k ≥ 0, we have that

    1 ≤ | 𝒱^+[k+1] | ≤ | 𝒱^+[k] | ≤ n .






Steps 1 and 2 at iteration k of Algorithm <ref> can be expressed according to the following equations 

    y[k+1] = W[k]  y[k] ,


    z[k+1] = W[k]  z[k] ,

where y[k] = [y_1[k]  ...  y_n[k]]^ T, z[k] = [z_1[k]  ...  z_n[k]]^ T and W[k] = [w_lj[k]] is an n × n binary column stochastic matrix. 
More specifically, for every k, the weights w_lj[k], for l=j or l such that (v_l,v_j) ∈ℰ, are either equal to 1 or 0, and furthermore each column sums to one.  


Focusing on (<ref>), at time step k_0, let us assume without loss of generality that
z[k_0] =  [ z_1[k_0] … z_p_0[k_0]   0 …  0  ]^ T, where z_i[k_0] > 0, ∀ v_i ∈{ v_1, ⋯, v_p_0} and z_l[k_0] = 0, ∀ v_l ∈𝒱 - { v_1, ⋯, v_p_0}. 
We can assume without loss of generality that the nodes with zero mass do not transmit (or transmit to themselves). 
Let us consider the scenario where ∑_v_i ∈𝒩_j^- ∪{v_j} w_ji[k_0] = 1, ∀ v_j ∈𝒱 (i.e., for every row of W[k_0] exactly one element is equal to 1 and all the other elements are equal to zero). 
This means that each node v_j will receive at most one mass variable z_i[k_0] and, since, at time step k_0, we have p_0 nodes with nonzero mass variables, we have that at time step k_0 + 1, exactly p_0 nodes have a nonzero mass variable. 
As a result, for this scenario, we have | 𝒱^+[k_0+1] | = | 𝒱^+[k_0] |. 


Let us now consider the scenario where w_ji_1[k_0] = 1, w_ji_2[k_0] = 1 (where v_i_1, v_i_2 ∈ ( 𝒩_j^- ∪{ v_j } ) ∩𝒱^+[k_0]) and w_ji[k_0] = 0, ∀ v_i ∈ ( 𝒩_j^- ∪{ v_j } ) - { v_i_1, v_i_2} (i.e., the j^th row of matrix 𝒲[k_0] has exactly 2 elements equal to 1 and all the other elements zero). 
Also, let us assume that ∑_v_i ∈𝒩_l^- ∪{v_l} w_li[k_0] ≤ 1, ∀ v_l ∈𝒱 - { v_j } (i.e., for every row of W[k_0] (except row j) at most one element is equal to 1 and all the other elements are equal to zero). 
The above assumptions, regarding matrix W[k], mean that, during time step k_0, only node v_j will receive two mass variables (from nodes v_i_1 and v_i_2) and all the other nodes will receive at most one mass variable. 
We have that z_j[k_0 + 1] = z_i_1[k_0] + z_i_2[k_0] and z_l[k_0 + 1] = z_i(l)[k_0], for v_l ∈𝒱 - { v_j } and some v_i(l)∈𝒱 - { v_i_1, v_i_2} (i.e., node v_j received two nonzero mass variables while all the other nodes received at most one nonzero mass variable, also counting its own mass variables). 
Since, at time step k_0, we had p_0 nodes with nonzero mass variables and at time step k_0 + 1 node v_j received (and summed) two nonzero mass variables, while all the other nodes received at most one nonzero mass variable, this means that, at time step k_0 + 1, we have p_0 - 1 nodes with nonzero mass variables. 
This means that | 𝒱^+[k_0+1] | < | 𝒱^+[k_0] |.












By extending the above analysis for scenarios where each row of W[k], at different time steps k, may have multiple elements equal to 1 (but W[k] remains column stochastic), we can see that the number of nodes v_j with nonzero mass variable z_j[k] > 0 is non-increasing and thus we have | 𝒱^+[k+1] | ≤ | 𝒱^+[k] |, ∀ k ∈ℤ_+. 






Consider a strongly connected digraph 𝒢_d = (𝒱, ℰ) with n=|𝒱| nodes and m=|ℰ| edges and z_j[0] = 1 and y_j[0] ∈ℤ for every node v_j ∈𝒱 at time step k=0. 
Suppose that each node v_j ∈𝒱 follows the Initialization and Iteration steps as described in Algorithm <ref>. 
With probability one, we can find k_0 ∈ℤ_+, so that for every k ≥ k_0 we have 

    y^s_j[k] = ∑_l=1^ny_l[0]  and  z^s_j[k] = n ,   ∀ v_j ∈𝒱

which means that 

    q^s_j[k] = ∑_l=1^ny_l[0]/n ,

for every v_j ∈𝒱 (i.e., for k ≥ k_0 every node v_j has calculated q as the ratio of two integer values). 




From Proposition <ref> we have that | 𝒱^+[k+1] | ≤ | 𝒱^+[k] | (i.e., the number of nonzero mass variables is non-increasing). 
We will first show that the number of nonzero mass variables is decreasing after a finite number of steps, until, at some k'_0 ∈ℤ_+, we have y_j[k'_0] =∑_l=1^ny_l[0]  and  z_j[k'_0] = n, for some node v_j ∈𝒱, and y_i[k'_0] = 0    and  z_i[k'_0] = 0, for each v_i ∈𝒱 - { v_j }). 


We have that Steps 1 and 2 at iteration (time step) k can be expressed according to (<ref>) and (<ref>).
Focusing on (<ref>), consider for example, two nodes v_i and v_j that happen to share a common out-neighbor (say v_l): suppose that, during time step k_0, we have z_i[k_0] > 0, z_j [k_0] > 0  and w_li[k_0] = 1, w_lj [k_0] = 1. 
This scenario will occur with probability equal to (1 + 𝒟_i^+)^-1(1 + 𝒟_j^+)^-1 (i.e., as long as nodes v_i and v_j both transmit towards node v_l). 
Of course, for this to happen we need to have node v_l be a common neighbor to nodes v_i and v_j.
More generally, since the graph is strongly connected, for any pair of nodes v_i and v_j, we can find a node (say v_l) and two paths (of length at most n-1) such that the first path p_li connects v_i to v_l and the second path p_lj connects v_j to v_l. 
If the two paths are not of equal length, we can make them of equal length (at most n-1) by inserting one (or more) self loops in the shortest of the two paths (p_li or p_lj). 
Then, it is easy to see that if, during time step k_0, we have z_i[k_0] > 0, z_j[k_0] > 0 (for any two nodes, v_i and v_j, i ≠ j), the two masses will merge at some node v_l after at most n-1 steps, with probability 

    P_two merge    =    ( ∏_v_j'∈ p_lj(1 + 𝒟_j'^+)^-1) ( ∏_v_i'∈ p_li(1 + 𝒟_i'^+)^-1) 
       ≥   ( ∏_v_j'∈ p_lj(1 + 𝒟_max^+)^-1) ( ∏_v_i'∈ p_li(1 + 𝒟_max^+)^-1) 
       ≥   ((1 + 𝒟_max^+)^-1)^2(n-1)  ,

where 𝒟_max^+ = max_v_j ∈𝒱𝒟_j^+ and | p_lj | = | p_li | (since by inserting a sufficient number of self loops in the (shorter of the two) paths we can make the lengths of both paths p_lj and p_li equal (at most) to n-1). 
Note that the notation v_j'∈ p_lj means that there exists a directed path p_lj consisting of a v_j ≡ v_l_0,v_l_1, …, v_l_t≡ v_l (such that (v_l_τ+1,v_l_τ) ∈ℰ for τ = 0, 1, … , t-1 i.e., a directed path from v_j to v_l), and v_j'∈{ v_l_0,v_l_1, …, v_l_t}. 
Note that (<ref>) provides a lower bound on the probability that, every n time steps, two (or more) masses merge into one mass. 


By extending the above discussion, we have that after k = τ (n-1) time steps (i.e., τ “windows”, τ≥ (n-1), each consisting of n-1 time steps) the probability that all n masses will “merge” into one mass is

    P_single mass   ≥    1 - ∑_j=0^n-2τ j(1 - P_two merge)^τ - j P_two merge^j   ,

(where the summation on the right is an upper bound on the probability that n-2 or less mergings occur over the τ windows of length n-1.

Thus, by executing Algorithm <ref> for τ “windows” (each consisting of n-1 time steps), we have that 

    lim_τ→∞P_single mass    =     1   .



This means that, with probability one, ∃ k'_0 ∈ℤ_+ for which y_j[k'_0] =∑_l=1^ny_l[0]  and  z_j[k'_0] = n, for some node v_j ∈𝒱, and y_i[k'_0] = 0,    and  z_i[k'_0] = 0, for each v_i ∈𝒱 - { v_j }. 
Once this “merging” of all nonzero mass variables occurs, we have that the nonzero mass variables of node v_j will update the state variables of every node v_i ∈𝒱 (because it will eventually be forwarded to all other nodes), which means that ∃ k_0 ∈ℤ_+ (where k_0 > k'_0) for which y_i^s[k_0] =∑_l=1^ny_l[0]  and  z_i^s[k_0] = n, for every node v_i ∈𝒱. 
Therefore, after a finite number of steps, (<ref>) and (<ref>) will hold for every node v_j ∈𝒱 for the case where α = 1. 













§ EVENT-TRIGGERED QUANTIZED AVERAGING ALGORITHM WITH MASS SUMMATION


In this section we propose a distributed algorithm in which the nodes receive quantized messages and perform transmissions according to a set of deterministic conditions, so that they reach quantized average consensus on their initial values. 
This allows the calculation of an explicit worst-case upper bound regarding the number of steps required for quantized consensus. 
Unlike the operation of Algorithm <ref> where, after a finite number of steps k_0, (<ref>) and (<ref>) will hold for each node v_j with α = 1 (at least with high probability), we will see that α can be (under some rare circumstances) an integer larger than 1 in the deterministic algorithm of this section. 





 §.§ Event-Triggered Deterministic Distributed Algorithm with Mass Summation



The operation of the proposed distributed algorithm is summarized below.

Initialization:
Each node v_j assigns to each of its outgoing edges v_l ∈𝒩^+_j a unique order P_lj in the set {0,1,..., 𝒟_j^+ -1}, which will be used to transmit messages to its out-neighbors in a round-robin fashion. 
Node v_j has initial value y_j[0] and sets its state variables, for time step k=0, as z_j[0] = 1, z^s_j[0] = 1 and y^s_j[0] = y_j[0], which means that q^s_j[0] = y_j[0] / 1.
Then, it chooses an out-neighbor v_l ∈𝒩_j^+ (according to the predetermined order P_lj) and transmits z_j[0] and y_j[0] to that particular neighbor. 
Then, it sets y_j[0] = 0 and z_j[0] = 0 (since it performed a transmission).

The iteration involves the following steps:

Step 1. Receiving: Each node v_j receives messages y_i[k] and z_i[k] from its in-neighbors v_i ∈𝒩_j^- and sums them to obtain

    y_j[k+1] = y_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]y_i[k] ,

and 

    z_j[k+1] = z_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]z_i[k] ,

where w_ji[k] = 0 if no message is received from in-neighbor v_i ∈𝒩_j^-; otherwise w_ji[k] = 1. 

Step 2. Event Trigger Conditions: Node v_j checks the following conditions:


  * It checks whether z_j[k+1] is greater than z^s_j[k].

  * If z_j[k+1] is equal to z^s_j[k], it checks whether y_j[k+1] is greater than or equal to y^s_j[k].

If one of the above two conditions holds, it sets y^s_j[k + 1] = y_j[k+1], z^s_j[k + 1] = z_j[k+1] and q_j^s[k+1] = y_j^s[k+1]/z_j^s[k+1]. 

Step 3. Transmitting: If the “Event Trigger Conditions” above do not hold, no transmission is performed. 
Otherwise, if the “Event Trigger Conditions” above hold, node v_j chooses an out-neighbor v_l ∈𝒩_j^+ according to the order P_lj (in a round-robin fashion) and transmits z_j[k+1] and y_j[k+1]. 
Then, since it transmitted its stored mass, it sets y_j[k+1] = 0, z_j[k+1] = 0. 
Regardless of whether it transmitted or not, node v_j sets k to k+1 and the iteration repeats (it goes back to Step 1). 

This event-based quantized mass transfer process is summarized as Algorithm <ref>. 
Note that the “Event Trigger Conditions” effectively imply that no transmission is performed if z_j[k]=0. 




    
2
Deterministic Quantized Average Consensus
Input 

 1) A strongly connected digraph 𝒢_d = (𝒱, ℰ) with n=|𝒱| nodes and m=|ℰ| edges. 

 2) For every v_j we have y_j[0] ∈ℤ. 


Initialization 

 Every node v_j ∈𝒱 does the following:

 1) It assigns to each of its outgoing edges v_l ∈𝒩^+_j a unique order P_lj in the set {0,1,..., 𝒟_j^+ -1}.

 2) It sets z_j[0] = 1, z^s_j[0] = 1 and y^s_j[0] = y_j[0] (which means that q^s_j[0] = y_j[0] / 1). 

 3) It chooses an out-neighbor v_l ∈𝒩_j^+ according to the predetermined order P_lj (initially, it chooses v_l ∈𝒩_j^+ such that P_lj=0) and transmits z_j[0] and y_j[0] to this out-neighbor. Then, it sets y_j[0] = 0 and z_j[0] = 0.


Iteration

 For k=0,1,2,…, each node v_j ∈𝒱 does the following:

 1) It receives y_i[k] and z_i[k] from its in-neighbors v_i ∈𝒩_j^- and sets 

    y_j[k+1] = y_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]y_i[k] ,

and 

    z_j[k+1] = z_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]z_i[k] ,

where  w_ji[k] = 0 if no message is received (otherwise w_ji[k] = 1). 

 2) Event Trigger Conditions: If one of the following two conditions hold, node v_j performs Steps 2a and 2b below (otherwise it skips Steps 2a and 2b).

 Condition 1: z_j[k+1] > z^s_j[k].

 Condition 2: z_j[k+1] = z^s_j[k] and y_j[k+1] ≥ y^s_j[k].

 2a) It sets z^s_j[k+1] = z_j[k+1] and y^s_j[k+1] = y_j[k+1] which implies that 

    q^s_j[k+1] = y^s_j[k+1]/z^s_j[k+1] .

2b) It chooses an out-neighbor v_l ∈𝒩_j^+ according to the order P_lj (in a round-robin fashion) and transmits z_j[k+1] and y_j[k+1]. Then it sets y_j[k+1] = 0 and z_j[k+1] = 0.

 3) It repeats (increases k to k + 1 and goes back to Step 1).














We now analyze the functionality of the distributed algorithm and prove that it allows all agents to reach quantized average consensus after a finite number of steps. Depending on the graph structure and the initial mass variables of each node, we have the following two possible scenarios:


  A. Full Mass Summation (i.e., there exists k'_0 ∈ℤ_+ where we have y_j[k'_0] =∑_l=1^ny_l[0]  and  z_j[k'_0] = n, for some node v_j ∈𝒱, and y_i[k'_0] = 0    and  z_i[k'_0] = 0, for each v_i ∈𝒱 - { v_j }). 
In this scenario (<ref>) and (<ref>) hold for each node v_j for the case where α = 1. 

  B. Partial Mass Summation (i.e., there exists k'_0 ∈ℤ_+ so that for every k ≥ k'_0 there exists a set 𝒱^p[k] ⊆𝒱 in which we have y_j[k] = y_i[k] and z_j[k] = z_i[k], ∀ v_j, v_i ∈𝒱^p[k] and y_l[k] = 0    and  z_l[k] = 0, for each v_l ∈𝒱 - 𝒱^p[k]). 
In this scenario, (<ref>) and (<ref>) hold for each node v_j for the case where α = | 𝒱^p[k] |.








An example regarding the scenario of “Partial Mass Summation” is given below. 



Consider the strongly connected digraph 𝒢_d = (𝒱, ℰ) shown in Fig. <ref>, with 𝒱 = { v_1, v_2, v_3, v_4 } and ℰ = { m_21, m_32, m_43, m_14}, where each node has an initial quantized value y_1[0] = 9, y_2[0] = 3, y_3[0] = 9, and y_4[0] = 3, respectively. 
We have that the average of the initial values of the nodes, is equal to q = 24/4 = 6. 



At time step k=0 the initial mass and state variables for nodes v_1, v_2, v_3, v_4 are shown in Table <ref>. 



tableInitial Mass and State Variables for Fig. <ref>


Node    5c|Mass and State Variables for k=0

    y_j[0]   z_j[0]   y^s_j[0]   z^s_j[0]   q^s_j[0]

1-6
                         

v_1     9     1     9     1     9 / 1

v_2     3     1     3     1     3 / 1

v_3     9     1     9     1     9 / 1

v_4     3     1     3     1     3 / 1









Then, during time step k=0, every node v_j will transmit its mass variables y_j[0] and z_j[0] (since the “Event Trigger Conditions” hold for every node). 
The mass and state variables of every node at k=1 are shown in Table <ref>. 


It is important to notice here that, at time step k=1, nodes v_1 and v_3 have mass variables equal to y_1[1] = 3, z_1[1] = 1 and y_3[1] = 3, z_3[1] = 1 but the corresponding state variables are equal to y^s_1[1] = 9, z^s_1[1] = 1 and y^s_3[1] = 9, z^s_3[1] = 1. 
This means that at time step k=1, the “Event Trigger Conditions” do not hold for nodes v_1 and v_3; thus, these nodes will not transmit their mass variables (i.e., they will not execute Steps 2a and 2b of Algorithm <ref>). 
The mass and state variables of every node at k=2 are shown in Table <ref>. 


During time step k=2 we can see that the “Event Trigger Conditions” hold for nodes v_1 and v_3 which means that they will transmit their mass variables towards nodes v_2 and v_4 respectively. 
The mass and state variables of every node for k=3 are shown in Table <ref>. 




tableMass and State Variables for Fig. <ref> for k=1


Node    5c|Mass and State Variables for k=1

    y_j[1]   z_j[1]   y^s_j[1]   z^s_j[1]   q^s_j[1]

1-6
                         

v_1     3     1     9     1     9 / 1

v_2     9     1     9     1     9 / 1

v_3     3     1     9     1     9 / 1

v_4     9     1     9     1     9 / 1













tableMass and State Variables for Fig. <ref> for k=2 


Node    5c|Mass and State Variables for k=2

    y_j[2]   z_j[2]   y^s_j[2]   z^s_j[2]   q^s_j[2]

1-6
                         

v_1     12     2     12     2     12 / 2

v_2     0     0     9     1     9 / 1

v_3     12     2     12     2     12 / 2

v_4     0     0     9     1     9 / 1












tableMass and State Variables for Fig. <ref> for k=3


Node    5c|Mass and State Variables for k=3

    y_j[3]   z_j[3]   y^s_j[3]   z^s_j[3]   q^s_j[3]

1-6
                         

v_1     0     0     12     2     12 / 2

v_2     12     2     12     2     12 / 2

v_3     0     0     12     2     12 / 2

v_4     12     2     12     2     12 / 2











Following the algorithm operation we have that, for k=3, the “Event Trigger Conditions” hold for nodes v_2 and v_4, which means that they will transmit their masses to nodes v_1 and v_3 respectively. 
As a result we have, for k=4, that the mass variables for nodes v_1 and v_3 are y_1[4] = y_4[3] = 12, z_1[4] = z_4[3] = 2 and y_3[4] = y_2[3] = 12, z_3[4] = z_2[3] = 2 respectively. 
Then, during time step k=4, we have that the “Event Trigger Conditions” hold for nodes v_1 and v_3 which means that they will transmit their mass variables to nodes v_1 and v_3. 
We can easily notice that, during the execution of Algorithm <ref> for k ≥ 3, we have 𝒱^p[k] = 𝒱^p[k + 2] (where 𝒱^p[3] = { v_2, v_4 } and 𝒱^p[4] = { v_1, v_3 }), which means that the exchange of mass variables between the nodes will follow a periodic behavior and the mass variables will never “merge” in one node (i.e., ∄ k'_0 for which y_j[k'_0] =∑_l=1^4y_l[0]  and  z_j[k'_0] = 4, for some node v_j ∈𝒱, and y_i[k'_0] = 0    and  z_i[k'_0] = 0, for each v_i ∈𝒱 - { v_j }).

Nevertheless, after a finite number of steps, every node v_j obtains a quantized fraction q_j^s which is equal to the average q of the initial values of the nodes. 
From Table <ref>, we can see that for k ≥ 3 it holds that 

    q_j^s[k] = q = 24 / α/4 / α ,

for every v_j ∈𝒱, for α = | 𝒱^p[k] | = 2. 
 □




Note that the periodic behavior in the above graph is not only a function of the graph structure but also of the initial conditions. 
Also note that, in general, the priorities will also play a role because they determine the order in which nodes transmit to their out-neighbors (in the example, priorities do not come into play because each node has exactly one out-neighbor).





 §.§ Deterministic Convergence Analysis


For the development of the necessary results regarding the operation of Algorithm <ref> let us consider the following setup. 

Setup: Consider a strongly connected digraph 𝒢_d = (𝒱, ℰ) with n=|𝒱| nodes and m=|ℰ| edges. 
During the execution of Algorithm <ref>, at time step k_0, there is at least one node v_j'∈𝒱, for which 

    z_j'[k_0] ≥ z_i[k_0],  ∀ v_i ∈𝒱.

Then, among the nodes v_j' for which (<ref>) holds, there is at least one node v_j for which 

    y_j[k_0] ≥ y_j'[k_0] ,  v_j, v_j'∈{ v_i ∈𝒱 |  (<ref>)  holds}.

For notational convenience we will call the mass variables of node v_j for which (<ref>) and (<ref>) hold as the “leading mass” (or “leading masses”). 


Before showing that Algorithm <ref> allows each node to reach quantized average consensus after a finite number of steps, we present the following lemma, which is helpful in the development of our results. 



Under the above Setup, the “leading mass” or “leading masses” at time step k, (which may be held by different nodes at different time steps) will always fulfill the “Event Trigger Conditions” (Step 2 of Algorithm <ref>). 
This means that the mass variables of node v_j for which (<ref>) and (<ref>) hold at time step k_0 will be transmitted (at time step k_0) by v_j to an out-neighbor v_l ∈𝒩_j^+. 



Let us suppose that, at time step k_0, (<ref>) and (<ref>) hold for the mass variables of node v_j (i.e., it is the “leading mass”). 
We will show that, during time step k_0, the state variables z_i^s[k_0] and y_i^s[k_0] of every node v_i ∈𝒱, satisfy one of the following:


  * z_i^s[k_0] < z_j[k_0] or, 

  * z_i^s[k_0] = z_j[k_0] and y_i^s[k_0] ≤ y_j[k_0], 

which means that the mass variables z_j[k_0] and y_j[k_0] of node v_j ∈𝒱 will fulfill the “Event Trigger Conditions” at time step k_0 in Step 2 of Algorithm <ref> at time step k_0. 

By contradiction let us suppose that, at time step k_0, there exists a node v_i ∈𝒱 for which one of the following holds:


  * z_i^s[k_0] > z_j[k_0] or, 

  * z_i^s[k_0] = z_j[k_0] and y_i^s[k_0] > y_j[k_0], 

while the mass variables of node v_j are the “leading mass”. 
From Step 2 of Algorithm <ref>, we have that, if the “Event Trigger Conditions” hold then each node v_i sets its state variables equal to its mass variables. 
This means that at some past time step k'_0 (k'_0 ≤ k_0), there was a node v_l' such that z_l'[k'_0] = z_i^s[k'_0] and y_l'[k'_0] = y_i^s[k'_0]; furthermore, since nonzero masses (like the mass held by node v_l') can only remain the same or be merged with other masses, we know that there exists a node v_l ∈𝒱 for which, at time step k_0, we have one of the following:


  * z_l[k_0] = z_i^s[k_0] and y_l[k_0] ≥ y_i^s[k_0] or, 

  * z_l[k_0] > z_i^s[k_0]. 

However, this also means that 


  * z_l[k_0] = z_j[k_0] and y_l[k_0] > y_j[k_0] or, 

  * z_l[k_0] > z_j[k_0], 

which is a contradiction because (<ref>) and (<ref>) do not hold for the mass variables of node v_j (i.e., it is not the “leading mass”). 

As a result we have that the “leading mass” will always fulfill the “Event Trigger Conditions” (Step 2 of Algorithm <ref>); thus, it will always be transmitted to an out-neighbor of the node it is held by. 






Under the above Setup we have that the execution of Algorithm <ref> allows each node v_j ∈𝒱 to reach quantized average consensus after a finite number of steps, bounded by O(nm^2). 
 


According to Lemma <ref>, we have that the “leading mass” (which may be held by different nodes at different time steps) will always fulfill the “Event Trigger Conditions” (Step 2 of Algorithm <ref>). 
This means that the mass variables of node v_j for which (<ref>) and (<ref>) hold, at time step k, will always be transmitted by v_j to an out-neighbor v_l ∈𝒩_j^+ at time step k.


Let us assume that, at time step k_0, the mass variables of node v_j are the “leading mass” and there exists a set of nodes 𝒱^f [k_0] ⊆𝒱 which is defined as 𝒱^f [k_0] = { v_i ∈𝒱 |  z_i[k_0] > 0  but (<ref>)  or (<ref>)  do not hold} (i.e., it is the set of nodes which have nonzero mass variables at time step k_0 but they are not “leading masses”).
Note here that if the “leading mass” reaches a node simultaneously with some other (leading or otherwise mass) then it gets “merged”, i.e., the receiving node “merges” the mass variables it receives, by summing their numerators and their denominators, creating a set of mass variables with a greater denominator (if necessary, the receiving node updates its state variables to be equal to these merged variables and then propagates them to an out-neighbor). 
Furthermore, we will say that a leading mass, at time step k_0, gets “obstructed” if it reaches, at time step k_0 + 1, a node whose state variables are greater than the mass variables (i.e., either the denominator of the node's state variables is greater than the denominator of the mass variables, or, if the denominators are equal, the numerator of the state variables is greater than the numerator of the mass variables). 
Note that if the “leading mass” gets “obstructed” then its no longer the “leading mass” (there is a new leading mass held by some node in the network). 


Suppose that the leading mass at time step k_0 is held by node v_j and is given by y_j[k_0] and z_j[k_0]. 
If this leading mass does not get merged or obstructed, during the execution of Algorithm <ref>, it will reach every node v_j ∈𝒱 in at most m^2 steps, where m = | ℰ | is the number of edges of the given digraph 𝒢 (this follows from Proposition 3 in <cit.>, which actually provides a bound for an unobstructed “leading mass” to travel via each edge in the graph and thus necessarily also reach every other node[In Proposition 3 in <cit.> the authors show that the number of iterations required for a packet, which is transmitted between nodes in a round-robin fashion over a directed topology, to reach every node in the network is bounded by m^2, where m is the number of edges in the network.]). 
This means that, after executing Algorithm <ref> for m^2 steps, we have z_i^s[k_0 + m^2] ≥ z_j[k_0], for every node v_i ∈𝒱 (i.e., after m^2 steps every node will have its state variable z^s equal or larger than the “leading mass”). 
Thus, at time step k_0 + m^2, if there is any node v_i ∈𝒱 (for which we necessarily have z_i^s[k_0 + m^2] ≥ z_j[k_0]) that belongs in 𝒱^f [k_0 + m^2], this node will perform no transmission (i.e., its mass variables will “get obstructed”) unless the event triggered conditions hold. 


Starting at time step k_0, during the execution of Algorithm <ref>, we examine what happens in the next m^2 time steps by considering the following scenarios:


A) If in the next m^2 time steps the “leading mass” gets “merged” then we have that at least one “merging” occurred (i.e., two nonegative mass variables simultaneously reached a common node in this time window of length m^2). 


B) If the “leading mass” at time step k_0 gets “obstructed”, it means that it reached a node (say v_i) which performed no transmissions.
For this to happen, then node v_i (or some other node) has “merged”, at some earlier point, a set of mass variables so that the resulting mass is larger than the “leading mass” (i.e., either the denominator of the node's state variables is greater than the denominator of the “leading mass”, or, if the denominators are equal, the numerator of the other mass variables is greater than the numerator of the “leading mass”). 
However, this means that there was at least one “merging” in these m^2 steps. 


C) If the “leading mass” (or “leading masses”) does not get “obstructed” or “merged” during the next m^2 time steps, we have z_i^s[k_0 + m^2] ≥ z_j[k_0], for every node v_i ∈𝒱 (i.e., after m^2 steps every node will have its state variable z^s equal or larger than the “leading mass”).
For this scenario we have the two cases below:


i) There is at least one node v_i which has nonzero mass variable z_i[k_0 + m^2], and for which the “Event Trigger Conditions” do not hold. 
This node will perform no transmission and, since the “leading mass” will visit every node v_j ∈𝒱 in the subsequent m^2 time steps, we have that the “leading mass” will visit also this particular node it will “merge” with its nonzero mass variables. 


ii) All nodes have equal mass variables. 
This means that there exists a set of nodes 𝒱^l [k_0 + m^2] ⊆𝒱 which is defined as 𝒱^l [k_0 + m^2] = { v_i ∈𝒱 |  z_i[k_0 + m^2] > 0  and (<ref>)  and (<ref>)  hold} (i.e., it is the set of nodes which have nonzero mass variables at time step k_0 + m^2 and they are “leading masses”). 
Note here that for every v_i, v_l ∈𝒱^l [k_0 + m^2] we have y_i[k_0 + m^2] = y_l[k_0 + m^2] and z_i[k_0 + m^2] = z_l[k_0 + m^2]. 
Note also that it is possible that these leading masses never merge; however, in such case, the nodes have already reached average consensus since, for every v_i ∈𝒱^l [k_0], we have that 

    y_i[k_0] =  ∑_l=1^ny_l[0]/α
 
and 

    z_i[k_0] = nα

where α = |𝒱^l [k_0]| 
which means that 

    q_i^s[k_0] = ∑_l=1^ny_l[0]/n.

Even when there are mergings of these mass variables later on, the average will not change. Since the maximum number of mergings is at most n - 1, we have that after O(nm^2) iterations the nodes will be able to calculate the average of their initial values.



The “Event Trigger Conditions” in Algorithm <ref> allowed the calculation of an upper bound on the number of iterations required for every node v_j ∈𝒱 to reach quantized average consensus. 
However, from Lemma <ref> we have that the “leading mass” will always fulfill the “Event Trigger Conditions” in Step 2 of Algorithm <ref>.
This means that the “leading mass” (or leading masses) will continue being transmitted from each node towards its out-neighbors even though quantized average consensus has already been reached. 
The distributed algorithm presented in the following section aims to address this issue by invoking multiple sets of “Event Trigger Conditions”, which allow the nodes to cease transmissions once quantized average consensus has been reached. 











§ EVENT-TRIGGERED QUANTIZED AVERAGING ALGORITHM WITH MINIMUM MASS SUMMATION


Motivated by the need to reduce energy consumption, communication bandwidth, network congestion, and/or processor usage, many researchers have considered the use of event-triggered communication and control <cit.>. 
In this section we extend Algorithm <ref> so that, once quantized average consensus is reached, all transmissions are ceased. 
The main idea is to maintain a separate mechanism for broadcasting the state variables, y^s and z^s, of each node (as long as they satisfy certain event trigger conditions). 
This way, nodes learn the average but also have a way to decide when (or not) to transmit. 




 §.§ Event-Triggered Distributed Algorithm with Minimum Mass Summation



The details of the proposed distributed algorithm with transmission stopping capabilities can be seen in Algorithm <ref> below. 
Here we focus on the event triggering rules that are used to determine when to transmit state variables and/or mass variables.

Initialization:
Initialization is as in Algorithm <ref>, except that after initializing its state variables, each node v_j broadcasts its state variables z^s_j[0] and y^s_j[0] to every out-neighbor v_l ∈𝒩_j^+.

Iteration: The iteration involves the following steps.

Step 1. Each node v_j receives y^s_i[k] and z^s_i[k] from its in-neighbors v_i ∈𝒩_j^- (where y^s_i[k] = 0 and z^s_i[k] = 0 if no message is received). 


Step 2. Event-Trigger Conditions 1: Each node v_j, checks the following conditions for every v_i ∈𝒩_j^-:


  * It checks whether z^s_i[k] is greater than z^s_j[k].

  * If z^s_i[k] is equal to z^s_j[k], it checks whether y^s_i[k] is greater than y^s_j[k].

If one of the above two conditions holds, it sets 

    z^s_j[k+1] =    max_v_i ∈𝒩_j^- z^s_i[k],    and
    
    y^s_j[k+1] =    max_v_i ∈{v_i'∈𝒩_j^- | z^s_i'[k] = z^s_j[k+1]} y^s_i[k],

which means q^s_j[k+1] = y^s_j[k+1]/z^s_j[k+1]. 
Then it broadcasts z^s_j[k+1] and y^s_j[k+1] to every out-neighbor v_l ∈𝒩_j^+.


Step 3. Event-Trigger Conditions 2: Each node v_j checks the following conditions:


  * It checks whether z_j[k] is lower than z^s_j[k+1].

  * If z_j[k] is equal to z^s_j[k+1], it checks whether y_j[k] is lower than y^s_j[k+1].

If one of the above two conditions holds, it chooses an out-neighbor v_l ∈𝒩_j^+ according to the order P_lj (in a round-robin fashion) and transmits y_j[k] and z_j[k]. 
Note that no transmission is necessary if z_j[k]=0 (which means that y_j[0] = 0). 
Then, since it transmitted its stored mass, it sets y_j[k] = 0, z_j[k] = 0. 


Step 4. Each node v_j receives messages y_i[k] and z_i[k] from its in-neighbors v_i ∈𝒩_j^- and sums them along with its stored messages y_j[k] and z_j[k] to obtain

    y_j[k+1] = y_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]y_i[k] ,

and 

    z_j[k+1] = z_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]z_i[k] ,

where w_ji[k] = 0 if no message is received from in-neighbor v_i ∈𝒩_j^-; otherwise w_ji[k] = 1.


Step 5. Event-Trigger Conditions 3: Each node v_j checks the following conditions:


  * It checks whether z_j[k+1] is greater than z^s_j[k+1].

  * If z_j[k+1] is equal to z^s_j[k+1], it checks whether y_j[k+1] is greater than y^s_j[k+1].

If one of the above two conditions holds, it sets z^s_j[k+1] = z_j[k+1] and y^s_j[k+1] = y_j[k+1]. Then it broadcasts z^s_j[k+1] and y^s_j[k+1] to every out-neighbor v_l ∈𝒩_j^+.


Finally, it sets q^s_j[k+1] = y^s_j[k+1]/z^s_j[k+1]. Then, k is set to k+1 and the iteration repeats (it goes back to Step 1 of the iterative process). 



Notice here that each node v_j, during time step k, performs two types of transmission, towards its out-neighbors v_l ∈𝒩_j^+: either via broadcasting (to all of its out-neighbors) of its state variables y^s_j[k] and z^s_j[k] (if “Event Trigger Conditions 1 and 3” hold) or via transmission of its mass variables y_j[k] and z_j[k] to a single out-neighbor, chosen according to the predetermined order P_lj (if “Event Trigger Conditions 2” hold). 
The event trigger conditions effectively imply that no transmission is performed if no set of conditions holds in Steps 2, 3 and 5. 




    
3
Deterministic Quantized Average Consensus with Minimum Mass Summation
Input 

 1) A strongly connected digraph 𝒢_d = (𝒱, ℰ) with n=|𝒱| nodes and m=|ℰ| edges. 

 2) For every v_j we have y_j[0] ∈ℤ. 


Initialization 

 Every node v_j ∈𝒱 does the following:

 1) It assigns to each of its outgoing edges v_l ∈𝒩^+_j a unique order P_lj in the set {0,1,..., 𝒟_j^+ -1}.

 2) It sets z_j[0] = 1, z^s_j[0] = 1 and y^s_j[0] = y_j[0] (which means that q^s_j[0] = y_j[0] / 1). 


 3) It broadcasts its state variables z^s_j[0] and y^s_j[0] to every out-neighbor v_l ∈𝒩_j^+.


Iteration

 For k=0,1,2,…, each node v_j ∈𝒱 does the following: 

 1) It receives y^s_i[k] and z^s_i[k] from its in-neighbors v_i ∈𝒩_j^- 
(where y^s_i[k] = 0 and z^s_i[k] = 0 if no message is received). 

 2) Event Trigger Conditions 1: Node v_j checks if there exists v_i ∈𝒩_j^- for which one of the following two conditions hold:

 Condition (i): z^s_i[k] > z^s_j[k].

 Condition (ii): z^s_i[k] = z^s_j[k] and y^s_i[k] > y^s_j[k].

 If one of the two conditions above holds, node v_j sets 

    z^s_j[k+1] = max_v_i ∈𝒩_j^- z^s_i[k] ,   and
 

    y^s_j[k+1] = max_v_i ∈{v_i'∈𝒩_j^- | z^s_i'[k] = z^s_j[k+1]} y^s_i[k] ,
 
which means q^s_j[k+1] = y^s_j[k+1]/z^s_j[k+1]. 


 3) Event Trigger Conditions 2: Node v_j checks if one of the following two conditions hold:

 Condition (i): 0 < z_j[k] < z^s_j[k+1].

 Condition (ii): z_j[k] = z^s_j[k+1] and y_j[k] < y^s_j[k+1]. 
If one of the two conditions above holds, then node v_j chooses an out-neighbor v_l ∈𝒩_j^+ according to the order P_lj (in a round-robin fashion) and transmits y_j[k] and z_j[k]. Then it sets y_j[k] = 0 and z_j[k] = 0.

 4) It receives y_i[k] and z_i[k] from its in-neighbors v_i ∈𝒩_j^- and sets 

    y_j[k+1] = y_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]y_i[k] ,

and 

    z_j[k+1] = z_j[k] + ∑_v_i ∈𝒩_j^- w_ji[k]z_i[k] ,

where  w_ji[k] = 0 if no message is received (otherwise w_ji[k] = 1).

 5) Event Trigger Conditions 3: Node v_j checks if one of the following two conditions hold:

 Condition (i): z_j[k+1] > z^s_j[k+1].

 Condition (ii): z_j[k+1] = z^s_j[k+1] and y_j[k+1] > y^s_j[k+1].
If one of the two conditions above holds, then node v_j sets z^s_j[k+1] = z_j[k+1] and y^s_j[k+1] = y_j[k+1] which means q^s_j[k+1] = y^s_j[k+1]/z^s_j[k+1]. 

 6) If either “Event Trigger Conditions 2” or “Event Trigger Conditions 3” hold, it broadcasts z^s_j[k+1] and y^s_j[k+1] to every out-neighbor v_l ∈𝒩_j^+.

 7) It repeats (increases k to k + 1 and goes back to Step 1).








We now analyze the functionality of the distributed algorithm and prove that it allows all agents to reach quantized average consensus after a finite number of steps. 
Furthermore, we will also show that once quantized average consensus is reached transmissions are ceased from each agent. 
Depending on the graph structure and the initial mass variables of each node, we have the following two possible scenarios: “Full Mass Summation” or “Partial Mass Summation” (as presented in Section <ref>). 
An example regarding the scenario of “Partial Mass Summation” is given below. 




Consider a strongly connected digraph 𝒢_d = (𝒱, ℰ), shown in Fig. <ref>, with 𝒱 = { v_1, v_2, v_3, v_4 } and ℰ = { m_31, m_41, m_12, m_13, m_43, m_24} where each node has an initial quantized value y_1[0] = 2, y_2[0] = 4, y_3[0] = 7 and y_4[0] = 9 respectively. 
The average of the initial values, is equal to q = 22/4. 



Each node v_j ∈𝒱 follows the Initialization steps (1-2) in Algorithm <ref>, assigning to each of its outgoing edges v_l ∈𝒩^+_j a unique order P_lj in the set {0,1,..., 𝒟_j^+ -1}. 
Assume that the unique orders assigned by each node are the following:

    v_1:     P_41 = 0,      P_31 = 1, 
    
    v_2:     P_12 = 0,     
     
    v_3:     P_13 = 0,      P_43 = 1,  
     
    v_4:     P_24 = 0.

Furthermore, each node broadcasts its state variables z^s_j[0] and y^s_j[0] to every out-neighbor v_l ∈𝒩_j^+.
The initial mass and state variables, at time step k=0, for nodes v_1, v_2, v_3, v_4 are shown in Table <ref>. 



tableInitial Mass and State Variables for Fig. <ref>


Node    5c|Mass and State Variables for k=0

    y_j[0]   z_j[0]   y^s_j[0]   z^s_j[0]   q^s_j[0]

1-6
                         

v_1     2     1     2     1     2 / 1

v_2     4     1     4     1     4 / 1

v_3     7     1     7     1     7 / 1

v_4     9     1     9     1     9 / 1








During the operation of Algorithm <ref>, at time step k=0, each node v_j will receive the state variables z^s_i[0] and y^s_i[0] from every in-neighbor v_i ∈𝒩_j^-. 
According to the “Event Trigger Conditions 1”, each node will update its state variables. 
Here, we have that nodes v_1 and v_2 will update them. 
Furthermore, following “Event Trigger Conditions 2”, nodes v_1 and v_2 will transmit their mass variables according to their unique predetermined order (nodes v_3 and v_4 will not transmit their mass variables because “Event Trigger Conditions 2” do not hold for them). 
Then, nodes v_1 and v_4 will receive the mass variables from their in-neighbors (i.e., from v_2 and v_1 respectively) and, following “Event Trigger Conditions 3”, they will update (and broadcast) their state variables. 
The mass and state variables, at time step k=1, for nodes v_1, v_2, v_3, v_4 are shown in Table <ref>. 

During time step k=1, each node v_j will receive the state variables from every in-neighbor and following “Event Trigger Conditions 1”, v_1 and v_2 will update their state variables. 
Then, following “Event Trigger Conditions 2”, node v_1 will transmit its mass variables (according to its unique predetermined order) towards node v_3. 
Node v_3 will receive the mass variables from node v_1 and, following “Event Trigger Conditions 3”, it will update (and broadcast towards its out-neighbors) its state variables. 
The mass and state variables, at time step k=2, for nodes v_1, v_2, v_3, v_4 are shown in Table <ref>. 



tableMass and State Variables for Fig. <ref> for k=1


Node    5c|Mass and State Variables for k=1

    y_j[1]   z_j[1]   y^s_j[1]   z^s_j[1]   q^s_j[1]

1-6
                         

v_1     4     1     7     1     7 / 1

v_2     0     0     9     1     9 / 1

v_3     7     1     7     1     7 / 1

v_4     11     2     11     2     11 / 2











tableMass and State Variables for Fig. <ref> for k=2


Node    5c|Mass and State Variables for k=2

    y_j[2]   z_j[2]   y^s_j[2]   z^s_j[2]   q^s_j[2]

1-6
                         

v_1     0     0     9     1     9 / 1

v_2     0     0     9     1     9 / 1

v_3     11     2     11     2     11 / 2

v_4     11     2     11     2     11 / 2









In Table <ref> we can see that for the set 𝒱^p[2] = {v_3, v_4 } we have y_3[2] = y_4[2] and z_3[2] = z_4[2] while, for the set 𝒱 - 𝒱^p[2] = {v_1, v_2 } we have 
y_1[2] = y_2[2] = 0 and z_1[2] = z_2[2] = 0. 
This means that we have a “Partial Mass Summation” scenario. 
In this case, we will see that “Event Trigger Conditions 3” will not hold again for any node for time steps k > 2 (i.e., no node will transmit again its mass variables). 


In the next time step (k=2), once each node receives the state variables from every in-neighbor, v_2 will update and broadcast its state variables (according to the “Event Trigger Conditions 1”). 
Then, since the “Event Trigger Conditions 2” do not hold for any node, no transmissions of mass variables will be performed; thus, no node will receive any mass variables.
This means that the “Event Trigger Conditions 3” also do not hold for any node. 
The mass and state variables, at time step k=3, for nodes v_1, v_2, v_3, v_4 are shown in Table <ref>. 



tableMass and State Variables for Fig. <ref> for k=3


Node    5c|Mass and State Variables for k=3

    y_j[3]   z_j[3]   y^s_j[3]   z^s_j[3]   q^s_j[3]

1-6
                         

v_1     0     0     9     1     9 / 1

v_2     0     0     11     2     11 / 2

v_3     11     2     11     2     11 / 2

v_4     11     2     11     2     11 / 2








In time step k=3, we have that v_1 will update and broadcast its state variables (according to the “Event Trigger Conditions 1”). 
Then, since the “Event Trigger Conditions 2” and “Event Trigger Conditions 3” do not hold for any node no transmissions will be performed. 
The mass and state variables, at time step k=4, for nodes v_1, v_2, v_3, v_4 are shown in Table <ref>. 



tableMass and State Variables for Fig. <ref> for k=4


Node    5c|Mass and State Variables for k=4

    y_j[4]   z_j[4]   y^s_j[4]   z^s_j[4]   q^s_j[4]

1-6
                         

v_1     0     0     11     2     11 / 2

v_2     0     0     11     2     11 / 2

v_3     11     2     11     2     11 / 2

v_4     11     2     11     2     11 / 2









In Table <ref>, we can see that (<ref>) and (<ref>) hold for every node for α = 2 (i.e., every node has reached quantized average consensus). 
Notice that no set of event trigger conditions holds for any node for time steps k ≥ 4. 
This means that no node will perform any transmissions of its state or mass variables for time steps k ≥ 4.  □
 



It is interesting to note here that if, during the Initialization of Algorithm <ref>, node v_1 sets its priorities as P_31 = 0 and P_41 = 1, then we will notice the scenario of “Full Mass Summation” for node v_4 (i.e., (<ref>) and (<ref>) hold for every node for α = 1) instead of the scenario of “Partial Mass Summation”. 





 §.§ Deterministic Convergence Analysis


The setup is identical to the one presented in Section <ref>, where the mass variables of node v_j for which (<ref>) and (<ref>) hold at time step k are called the “leading mass”. 
Furthermore, we will call the mass variables of every node v_i ∈𝒱, for which z_i[k] > 0 and for which neither (<ref>) nor (<ref>) hold at time step k, as the “follower mass”. 


If, during time step k_0 of Algorithm <ref>, the mass variables of node v_j fulfil (<ref>) and (<ref>), then the state variables of every node v_i ∈𝒱 satisfy 

    z_i^s[k_0] ≤ z_j[k_0] ,

or 

    z_i^s[k_0] = z_j[k_0]   and  y_i^s[k_0] ≤ y_j[k_0].




Let us consider the variable

    z^(m)[k] = max_v_l ∈𝒱 z_l[k] .

From Iteration Step 4 of Algorithm <ref> we have that z^(m)[k] is non-decreasing (i.e., z^(m)[k+1] ≥ z^(m)[k], for every k). 
Furthermore, since the mass variables of node v_j fulfill (<ref>) and (<ref>), then, during every time step k, it holds that  

    z_j[k] = z^(m)[k].


In addition, for every k, during Iteration Steps 2 and 5 of Algorithm <ref>, for every node v_i ∈𝒱, we have that z_i^s[k] is either less than z^(m)[k] (i.e., z_i^s[k] < z^(m)[k]) or equal to z^(m)[k] (i.e., z_i^s[k] = z^(m)[k]). 
As a result, at time step k, the state variables of every node v_i ∈𝒱 satisfy 

    z_i^s[k] ≤ z_j[k] .


Finally, from Iteration Steps 2 and 5, (for every k) if, it holds that z_i^s[k] = z_j[k] for some node v_i then we have that either y_i^s[k] < y_j[k] or y_i^s[k] = y_j[k]. 
[Note here that if z_i^s[k] = z_j[k] and y_i^s[k] > y_j[k], then the mass variables of v_j do not fulfil (<ref>) and (<ref>) which is a contradiction.]
As a result we have that if the mass variables of node v_j fulfil (<ref>) and (<ref>), then the state variables of every node v_i ∈𝒱 satisfy (<ref>) or (<ref>). 






































If, during time step k_0 of Algorithm <ref>, the mass variables of each node v_j with nonzero mass variables fulfill (<ref>) and (<ref>), then we have only “leading masses” and no “follower masses”. 
This means that the “Event Trigger Conditions 2” will never hold again for future time steps k ≥ k_0. 
As a result, the transmissions that (may) take place will only be via broadcasting (from “Event Trigger Conditions 1 and 3”) for at most n-1 time steps and then they will cease. 



Let us assume that during time step k_0 two (or more) mass variables merge at nodes v_j, v_i, so that these two nodes simultaneously become “leading masses” (more generally, we could have more than two leading masses) and all other nodes have zero mass variables. 
Since the mass variables of nodes v_j, v_i, during time step k_0, become “leading masses” then there exists a set 𝒱^p[k_0] ⊆𝒱 in which we have y_j[k_0] = y_i[k_0] and z_j[k_0] = z_i[k_0], ∀ v_j, v_i ∈𝒱^p[k_0] and y_l[k_0] = 0    and  z_l[k_0] = 0, for each v_l ∈𝒱 - 𝒱^p[k_0].
Once this “merge” occurs then we have that for both v_j and v_i the “Event Trigger Conditions 1” and the “Event Trigger Conditions 2” do not hold, but “Event Trigger Conditions 3” do hold. 
This means that v_j and v_i do not transmit their mass variables but rather they broadcast their new state variables to their out-neighbors. 
Then, their out-neighbors, v_l_j and v_l_i respectively, will update their state variables and broadcast their new state variables towards their out-neighbors. 
The updating and broadcasting of state variables will continue, until all nodes obtain state variables equal to z^s_j[k_0] and y^s_j[k_0]. 
Note that during this update and broadcasting of state variables, no node transmits its mass variables. 
After at most n-1 steps, all nodes will be aware of the values z^s_j[k_0] and y^s_j[k_0], and at that point all transmissions will seize.






























The execution of Algorithm <ref> allows each node v_j ∈𝒱 to reach quantized average consensus after a finite number of steps, bounded by O(nm^2). 
Furthermore, once quantized average consensus is reached, each node stops transmitting towards its out-neighbors. 
 



Before starting the analysis of Algorithm <ref>, it is important to notice that the “leading mass” will not fulfill “Event Trigger Conditions 2” in Step 3 of the Iteration of Algorithm <ref> which means that the corresponding node (say v_j) will not transmit its mass variables to its out-neighbors v_l ∈𝒩_j^+ according to its predetermined priority. 
In this proof, we will show that there exists k_0 ∈ℤ_+, where for every k ≥ k_0, the mass variables of every node v_j, for which z_j[k] > 0, fulfill (<ref>) and (<ref>) (i.e., for k ≥ k_0 we have only “leading masses”). 
Furthermore, from Lemma <ref>, we have that there exists k_1 > k_0, where for every k ≥ k_1 the state variables of every node v_j ∈𝒱 fulfill (<ref>) and (<ref>) for α∈ℤ_+ (i.e., every node has reached quantized consensus) and thus transmissions cease. 


During the Initialization steps of Algorithm <ref>, we have that each node will broadcast its state variables to every out-neighbor. 
Then, during Iteration Step 1, each node will receive and update its state variables, while during Step 2 (i.e., “Event Trigger Conditions 1”), it will broadcast towards its out-neighbors the updated values (of the state variables). 
This means that after n iterations (assuming, that no other mass variables “merged” during n time steps), the state variables of each node v_i ∈𝒱, satisfy

    z^s_i[n] = z_j_1[0],   and  y^s_i[n] = y_j_1[0] ,

where the mass variables of node v_j_1 are the “leading mass”. 
As a result we have that, after n iterations, the “Event Trigger Conditions 2” will hold for every node v_i ∈𝒱 - { v_j_1}, and thus every node (except node v_j_1 which is the “leading mass”) will transmit its mass variables toward its out-neighbors according to its unique priority. 
Note here that the number of iterations required for the “follower mass” to reach every node v_i ∈𝒱 is bounded by m^2, where m = | ℰ | is the number of edges of the given digraph 𝒢 (in this case Proposition 3 in <cit.>, provides a bound for the “follower mass” to travel via each edge in the graph and thus necessarily also reach every other node).
Let us assume now that, after executing Algorithm <ref> for additional m^2 steps, we have that the mass variables z_i_1[0], y_i_1[0] and z_i_2[0], y_i_2[0] of nodes v_i_1 and v_i_2 respectively, meet (and “merge”) in node v_j_2, and after this merge they become the “leading mass”.  
This means that, during time step n + m^2, node v_j_2 will not transmit its mass variables (because “Event Trigger Conditions 2” do not hold) but it will broadcast its state variables to every out-neighbor (because “Event Trigger Conditions 3” hold). 
Thus, after additional n iterations, the state variables of each node v_i ∈𝒱 satisfy

    z^s_i[2n + m^2] = z_j_2[n + m^2],

and

    y^s_i[2n + m^2] = y_j_2[n + m^2] ,

where the mass variables of node v_j_2 are now the “leading mass”. 
This means that the “Event Trigger Conditions 2” will hold for every node v_i ∈𝒱 - { v_j_2}, and thus every node (except node v_j_2 which is now the “leading mass”) will transmit its mass variables toward its out-neighbors according to its unique priority. 
Note here that also node v_j_1 will transmit its mass variables toward its out-neighbors (since the state variables of v_j_1 are equal to the mass variables of the “leading mass” v_j_2 this means that “Event Trigger Conditions 2” will also hold for v_j_1). 
Let us assume now that, after executing Algorithm <ref> for additional m^2 steps, the mass variables z_i_3[0], y_i_3[0] and z_i_4[0], y_i_4[0] of nodes v_i_3 and v_i_4 respectively, meet (and “merge”) in node v_j_3, and after this merge they become the “leading mass”. 
Again, this means that during time step 2n + 2m^2, node v_j_3 will not transmit its mass variables (because “Event Trigger Conditions 2” do not hold) but it will broadcast its state variables to every out-neighbor (because “Event Trigger Conditions 3” hold). 
After additional n iterations, the state variables of each node v_i ∈𝒱 satisfy

    z^s_i[3n + 2m^2] = z_j_3[2n + 2m^2],

and 

    y^s_i[3n + 2m^2] = y_j_3[2n + 2m^2] ,

where the mass variables of node v_j_3 are now the new “leading mass”. 
By continuing this analysis, we can see that every n + m^2 time steps at least two “follower masses” “merge” and become the “leading mass”. 
Since, during the Initialization steps of Algorithm <ref>, we have n initial mass variables this means that after (n-1)n + (n-1)m^2 time steps all initial mass variables will “merge” into one mass (obviously the mass variables in which every initial mass has “merged” is the “leading mass”). 
As a result, at time step (n-1)n + (n-1)m^2 we have only “leading masses” and no “follower masses”. 
Thus, from Lemma <ref>, we have that after additional n time steps every node will have state variables equal to the “leading mass” (i.e., z^s_i[n^2 + (n-1)m^2] = n and y^s_i[n^2 + (n-1)m^2] = ∑_l=1^ny_l[0], for every v_i ∈𝒱) and then transmissions will be ceased. 


Note that so far we considered the scenario where there is only one “leading mass” during every time step k and it “merges” with only one nonzero mass variable every n + m^2 time steps. 
In other scenarios, we can consider multiple “leading masses” (i.e., when the nonzero mass variables fulfill (<ref>) and (<ref>) for more than one node) which will also speed up the convergence since the “follower masses” will “merge” more frequently. 




It is important to note here that the operation of Algorithm <ref> follows an opposite scenario than the operation of Algorithm <ref>. 
In Algorithm <ref>, the “leading mass” always fulfills the “Event Trigger Conditions”, and thus it is always transmitted from each node according to its unique priority. 
However, in Algorithm <ref>, the “leading mass” does not fulfill “Event Trigger Conditions 2” which means that it will not be transmitted. 
This means that the operation of Algorithm <ref> leverages on the fact that the number of initial masses is finite (and equal to n) and thus their summation into one (or multiple) “leading mass” (or “leading masses”) will occur after a finite number of steps. 
Once this happens, transmissions between nodes will continue for a maximum of n time steps (from “Event Trigger Conditions 1”) and then will cease. 





§ SIMULATIONS AND COMPARISONS
 

In this section, we illustrate the behavior of the proposed distributed algorithms for a random graph of size n = 20 nodes, a ring-shaped directed graph of size n = 20 nodes and a ring-shaped undirected graph of size n = 20 nodes. 
We also compare the proposed algorithms against the current state-of-the-art, trying to point out key differences and limitations in each approach.
Specifically, we first illustrate the operation of Algorithms <ref>, <ref> and <ref> in digraphs of size n=20 nodes. 

Figure <ref> shows what happens in the case of a randomly, created graph of 20 nodes in which the average of the initial values is equal to q = 50020 = 25. 
We can see that Algorithm <ref> outperforms Algorithms <ref> and <ref>. 














In Figure <ref>, we observe that the operation of Algorithm <ref> allows agents, after a small amount of steps, to reach consensus to a value that is close but not necessarily equal to the average of the initial values. 
Eventually, this consensus value changes (around time step 90) and becomes equal to the average of the initial values. 
This feature of Algorithm <ref> may be useful in situations in which the agents of a network need to coordinate their operations fast (i.e., reach a common decision) so the overall operation of the network is not disrupted greatly during the calculation of the exact average of the initial values (e.g., UAV flocking). 
However, similar behavior (i.e., consensus to a common value during the calculation of the average) can be observed in Algorithms <ref> and <ref> if we modify them so they perform, along with their protocols, a “leading mass” max-voting (this effectively implies that the node that has the “leading mass” broadcasts is state variables to its out-neighbors).  



Figures <ref> and <ref> show what happens in the cases of a ring-shaped digraph of 20 nodes and a ring-shaped undirected graph of 20 nodes, respectively, in which the average of the nodes initial values is equal to q = 48020 = 24. 
Again Algorithm <ref> appears to outperform Algorithms <ref> and <ref>. 
















Now, we compare the performance of the proposed algorithms against three other algorithms: (a) the quantized gossip algorithm presented in <cit.> in which, at each time step k, one edge[Note here that the algorithm presented in <cit.> requires the underlying graph to be undirected. For this reason, in Figure <ref>, we consider, for the algorithm in <cit.>, the underlying graph to be undirected (i.e., if (v_j, v_i) ∈ℰ then (v_i, v_j) ∈ℰ) while, for the algorithms in <cit.> we consider the underlying graph to be directed.] is selected at random, independently from earlier instants and the values of the nodes that the selected edge is incident on are updated, (b) the quantized asymmetric averaging algorithm presented in <cit.> in which, at each time step k, one edge, say edge (v_l, v_j), is selected at random and, node v_j sends its state information and surplus and node v_l performs updates 
over its own state and surplus values, (c) the distributed averaging algorithm with quantized communication presented in <cit.> in which, at each time step k, each agent v_j broadcasts a quantized version of its own state value towards its out-neighbors. 





Figure <ref> presents a study of the case of 1000 digraphs of 20 nodes each, in which the average of the nodes initial values is equal to q = 44020 = 22. 
The results shown are the average results over 1000 graphs. 
The top of Figure <ref> shows that Algorithm <ref> and Algorithm <ref> outperform the quantized gossip algorithm presented in <cit.> (for which the underlying graph is undirected), while Algorithm <ref> requires a relatively larger number of iterations to converge. 
Furthermore, we can see that Algorithm <ref>, Algorithm <ref> and Algorithm <ref> outperform the quantized asymmetric averaging algorithm presented in <cit.>. 
However, the distributed averaging algorithm presented in <cit.> is able to outperform all the aforementioned algorithms due to the fact that nodes can process real numbers and use a set of weights that form a doubly stochastic matrix (which guarantees convergence proportional to the second largest magnitude of its eigenvalues). 
Notice that obtaining a set of weights that forms a doubly stochastic matrix is an easy task in undirected graphs but becomes challenging in directed graphs <cit.>.








§ CONCLUDING REMARKS



In this work, we have considered the quantized average consensus problem for a distributed system that forms a directed graph in which the agents can exchange quantized information in a distributed fashion. 
Quantized average consensus plays a key role in a number of applications, which aim at more efficient usage of network resources. 
We proposed three distributed algorithms for solving the quantized average consensus problem. 
For the first probabilistic distributed algorithm, we showed that each agent achieves quantized average consensus with probability one. 
For the second and third deterministic distributed algorithms, we showed that quantized average consensus is achieved after a finite number of iterations that we explicitly bounded; for the latter, we also showed that once quantized average consensus is achieved, transmissions are ceased from each agent. 
To the best of our knowledge, these are the first deterministic algorithms which allow convergence to the quantized average of the initial values after a finite number of time steps without any specific requirements regarding the network that describes the underlying communication topology (see <cit.>). 


In the future, we plan to extend the proposed algorithms over other types of quantized consensus, such as quantized average consensus on networks with time-varying topologies or networks with bounded or unbounded (packet drops) transmission delays over the communication links. 
Furthermore, we plan to design distributed strategies under which every agent in the network will be able to determine whether quantized average consensus has been reached (and thus proceed to execute more complicated control or coordination tasks). 
Finally, we also plan to design algorithms that achieve quantized average consensus by preserving the privacy of the participating agents.








IEEEtran





[
    < g r a p h i c s >
]Apostolos I. Rikos (M'16) received the B.Sc., M.Sc and Ph.D. degrees in Electrical Engineering from the Department of Electrical and Computer Engineering, University of Cyprus in 2010, 2012 and 2018 respectively.
In 2018, he joined the KIOS Research and Innovation Centre of Excellence in Cyprus. 
Since February 2020, he has been a postdoctoral researcher at the Automatic Control Department of KTH Royal Institute of Technology. 
His research interests are in the area of distributed systems, coordination and control of networks of autonomous agents, sensor networks, stochastic processes, optimization and graph theory.





[
    < g r a p h i c s >
]Christoforos N. Hadjicostis
(M'99, SM'05) received the S.B. degrees in electrical engineering, computer science and engineering, and in mathematics, the M.Eng. degree in electrical engineering and computer science in 1995, and the Ph.D. degree in electrical engineering and computer science in 1999, all from Massachusetts Institute of Technology, Cambridge. In 1999, he joined the Faculty at the University of Illinois at Urbana–Champaign, where he served as Assistant and then Associate Professor with the Department of Electrical and Computer Engineering, the Coordinated Science Laboratory, and the Information Trust Institute. Since 2007, he has been with the Department of Electrical and Computer Engineering, University of Cyprus, where he is currently Professor. His research focuses on fault diagnosis and tolerance in distributed dynamic systems, error control coding, monitoring, diagnosis and control of large-scale discrete-event systems, and applications to network security, anomaly detection, energy distribution systems, medical diagnosis, biosequencing, and genetic regulatory models. He currently serves as Departmental Editor of the Journal of Discrete Event Systems and as Associate Editor of Automatica and the Journal of Nonlinear Analysis of Hybrid Systems. In the past, he had served as Associate of IEEE Transactions on Automatic Control, IEEE Transactions on Automation Science and Engineering, IEEE Transactions on Control Systems Technology, and IEEE Transactions on Circuits and Systems I.








