Mode Consensus Algorithms With Finite Convergence Time

Consider a group of $N$ agents labeled as $\mathcal{V}=\{1,\cdots,N\}$. Every agent has an attribute, which can be thought of as a label. The attribute could be a positive integer, a real vector, a color, a gender, an age group, a brand of car, etc. Two or more agents may have the same attribute (and indeed, in many situations one might expect the number of distinct attributes to be much less than the number of agents). The attribute of agent $i$ will be denoted by $a_{i}$. The vertex set is part of an undirected graph $\mathcal{G}$ with which is also associated a set $\mathcal{E}$ of edges (i.e. vertex pairs), in the usual way. The neighbor set $\mathcal{N}_{i}$ of agent $i$ is the set of vertices which share an edge with agent $i$. The vertex set $\mathcal{V}$, the edge set $\mathcal{E}$, the attributes $a_{i}$, and $\mathcal{N}_{i}$ are assumed to be time-invariant in the bulk of the paper, but at times we open up the possibility, to accommodate a “plug and play” capability, that, following certain rules, means they are piecewise constant. The state $x_{i}$ is updated by an out-distributed control algorithm, that is, at every time $t$, the quantity $\dot{x}_{i}$ is computed as some function of $a_{i}$, $x_{i}(t)$, and $x_{j}(t)$ for all $j\in\mathcal{N}_{i}\left(t\right)$.¹¹1While we choose a continuous time setting in this paper, it seems very probable that a discrete-time setting could be used as an alternative, with very little change to the main assumptions, arguments and conclusions.

The need for connectivity is intuitively obvious. The need for $\mathcal{G}$ to be undirected is less so; note though that virtually all blended dynamics developments rest on an assumption of undirectedness of the underlying graph.

To explain the problem setting, we define first the particular generalization of consensus, viz. $f$-consensus, with which we are working, and then indicate an explicit type of $f$-consensus problem of interest in this paper for which we are seeking an update algorithm. Following this, we provide two illustrative examples of $f$-consensus which are in some way relevant to the problem considered here. For an introduction and the development of $f$-consensus, see e.g. [10, 9, 5].

Average consensus, obtained by setting $\Omega=\mathbb{R}$, $a_{i}=x_{i}(0)$ and $f(a_{1},\cdots,a_{N})=\sum_{i=1}^{N}a_{i}/N$ is a very well known example. Some others are detailed further below, starting with the problem of interest in this paper. In the meantime however, we shall make the following assumption:

To illustrate the practical effect of this assumption, suppose that we are considering an attribute which is a 2-vector of real numbers, being the height and weight of a group of individuals. Such data is always quantized in the real world, with height for example usually being expressed to the nearest number of centimeters. So the vector entry corresponding to height might be an integer number somewhere between 25 and 250, and a number of say 180 would indicate the individual’s height lies in the interval [179.5,180.5). In effect $\Omega$ becomes a finite subset of $\mathbb{R}^{2}$. Then any such finite set $\Omega$ can always be bijectively mapped to $\{1,2,\cdots,|\Omega|\}=\mathcal{D}$. While the possibly unordered set $\Omega$ is mapped to an ordered set $\mathcal{D}$ by the mapping $l$, the order can be arbitrary for our purpose of computing the mode of the attributes.

There are two related problems treatable by $f$-consensus which are similar to the problem just posed, and which have provided to the authors of this paper insights in the formulation of the solution of the mode consensus problem.

Mode consensus is a special class of $f$-consensus problem. Suppose the function $f_{\rm m}:\Omega^{N}\to\Omega$ returns the attribute $a^{*}\in\Omega$ that appear most often among $a_{1},\cdots,a_{N}$ (when multiple distinct values equally appear most often, $f_{\rm m}$ returns any of these values specified by the user). The mode consensus problem as studied in this paper is an $f$-consensus problem with $f=f_{\rm m}$.

In many circumstances, it may be advantageous to have a plug-and-play capability. Specifically, we are interested in a network that can change over time during its operation. Changes cannot be arbitrary, but rather admissible in accord with certain rules.

First, while the potential vertex set $\bar{\mathcal{V}}$ is taken as time-invariant, that is, $\bar{\mathcal{V}}=\{1,\cdots,\bar{N}\}$ is fixed over time for some $\bar{N}$, the actual vertex set $\mathcal{V}$ which is an arbitrary subset of $\bar{\mathcal{V}}$ can be time-varying but piecewise constant; with $N(t)$ denoting its cardinality, $\bar{N}$ is an upper bound for $N(t)$. In this setting, our admissible changes are as follows:

• •

  The set of edges, written as $\mathcal{E}(t)$, is time-varying but piecewise constant. Therefore, at certain time instants, a new edge or edges can be created, and some existing edge or edges can be deleted.

• •

  There can be orphan nodes (meaning a node that has no incident edge). When all the edges that are incident to a node are deleted, we say the node leaves the network.

• •

  We assume that there is only one connected component in the network. In fact, even if there is more than one connected component, our concern is with just one of them. If a connected component of interest splits into two connected components (with some edges being deleted), one of these components still receives our attention, and all the nodes belonging to the other component are regarded as leaving the network.

• •

  The attribute of a node is permitted to be time-varying but must be piecewise constant.

• •

  The node dynamics stop integrating whenever the node is an orphan. One example of the node dynamics is:

  $$\dot{x}_{i}={\mathrm{sgn}}(|\mathcal{N}_{i}(t)|)\cdot\left(g_{i}(x_{i},t)+\sum_{j\in\mathcal{N}_{i}(t)}(x_{j}-x_{i})\right)$$

  (4)

  where $|\cdot|$ for a set implies cardinality of the set. In this way, malfunctioning agents can also be represented by considering them as orphans.

The control algorithm for updating the states of agents is said to be plug-and-play ready if, whenever an abrupt admissible change of the network occurs, (a) the $f$-consensus is recovered (to a new value reflecting the new situation) after a transient, and (b) the recovery is achieved by passive manipulation, together with local initialization of the newly joining agent if necessary. By passive manipulation we mean that, when an individual agent detects the changes in its incident edge set, or equivalently its neighbor set, associated with immediate neighbors leaving or joining the network, the agent can perform some actions that do not require reactions of neighboring agents. An example is (4) because, if $\mathcal{N}_{i}(t^{-})\not=\mathcal{N}_{i}(t^{+})$ at time $t$, the manipulation simply resets the incident edge set or equivalently neighbor set, and this can be done by the individual agent. (Of course, neighbor agents may have to also reset in order to carry out their own updates.) By local initialization we mean that, any initialization following a change must be local only, i.e. it must be global initialization-free. This implies that the algorithm should not depend on a particular initial condition constraining two or more agents in some linked way. A constraint such as $\sum_{i=1}^{N}x_{i}(0)=0$ is an example of global initialization, while the constraint that $x_{i}(0)\in{\mathcal{K}}$, $\forall i\in{\mathcal{V}}$, where $\mathcal{K}$ is a compact set known to every agent, is considered as an example of local initialization (or equivalently it is global initialization-free), and a local initialization is required for the newly joining agent (or, in (4), when $\mathcal{N}_{i}(t)$ becomes non-empty so that the sign function changes from 0 to 1).

The property of plug-and-play ready basically requires that, when the change occurs, no further action is required except for the agents whose incident edge sets are changed. In particular, the requirement of passive manipulation is useful in the case when some agent suddenly stops working (without any prior notification) and cannot function properly anymore.

The message of Lemma 1 is that, if a lower bound of the frequency of the mode is known, that is, ${\mathcal{F}}(a^{*})\geq f^{*}$ with a known $f^{*}$, then, with $K$ such that $f^{*}\geq\lceil\frac{N}{K}\rceil$, the integer $l(a^{*})$ for the mode $a^{*}$ should be one of the $j\left\lceil{\frac{N}{K}}\right\rceil$-th smallest elements, $j=1,\dots,K$, in $\{l(a_{1}),\dots,l(a_{N})\}$. This message yields Algorithm 2, in which, Step 2) identifies the $j\left\lceil{\frac{N}{K}}\right\rceil$-th smallest elements, $j=1,\dots,K$, and then, Step 4) finds the mode by comparing the frequencies among the candidates.

While Algorithm 2 outlines the distributed mode consensus algorithm, it also reveals the significance of $K$ in reducing the computational load. Depending on $K$, sometimes Algorithm 2 may involve manipulating or storing fewer variables than Algorithm 1, but the reverse may hold. In fact, Step 2) in Algorithm 2 can be considered as a selection procedure to find an attribute to be inspected. By this, it is expected that the number of inspections in (11) (effectively, the cardinality of $\mathcal{A}$) is smaller than that in (8) (the cardinality of $\Omega$). This is indeed the case when, for example, with $N=10$, $[l(a_{1}),\dots,l(a_{N})]=[1,1,1,1,1,2,3,4,5,6]$, and $|\Omega|=6$. That is, for (8), at least six attributes are inspected in Step 1) of Algorithm 1. For the case of Algorithm 2, assuming that $f^{*}=5$ is known, $K=2$ guarantees that $f^{*}=5\geq\lceil 10/2\rceil=5$, and so two attributes are inspected by Step 3) of Algorithm 2. However, in order to identify the attributes to be inspected, Step 1)-2) of Algorithm 2 needs to be performed, as an overhead. So the total number of variables to be manipulated is $2K+1=5$ which is still less than $\left|\Omega\right|=6$. As a second example, if $[l(a_{1}),\dots,l(a_{N})]=[1,2,3,4,4,5,6,7,8,8]$ with $N=10$ and $\left|\Omega\right|=8$, then $f^{*}=2$ and we have to choose $K=5$. In this case, Algorithm 2 inspects five candidates while Algorithm 1 inspects eight candidates, but the count of the overhead is five so that the total count becomes $2K+1=11$, which is more than $|\Omega|=8$.

A convergence time bound can be established as follows. Suppose Algorithm 2 is executed with parallel computations at Steps 2) and 4), for example at Step 2), each agent runs the $j\left\lceil{\frac{N}{K}}\right\rceil$-th smallest element consensus protocol for every $j=1,2,\cdots,K$ in parallel. Then, the mode consensus is reached within the time ${\mathcal{T}}_{x}+{\mathcal{T}}_{y}+{\mathcal{T}}_{z}$.

It appears from Algorithm 2 that Step $i+1)$ can only be implemented after Step $i)$ has converged. This is actually not the case. All steps may start simultaneously, provided that the parameters used in any step are replaced with their estimated value generated in the previous steps. Indeed, the following equations are one alternative implentation of Algorithm 2 for agent $i$:

where $c_{1}=1$, $c_{i}=0$ for all $i\not=1$, and

in which, $\beta$, $g$, $\gamma_{x}$, $\gamma_{y}$, and $\gamma_{z}$ are predetermined. (When $\left\lceil{\frac{N}{K}}\right\rceil>{\frac{N}{K}}$, the $K$ in the above is interpreted as $K-1$.) Here, $x_{i}$ is the estimate of $N$ by the agent $i$, $z_{k}^{i}$ is the estimate of the $k$-th smallest element, $y_{k}^{i}$ is the estimate of the frequency of $z_{k}^{i}$, and $\widehat{m}^{i}$ is the estimated integer for the mode, i.e., the estimated mode is $a\in\Omega$ such that $l(a)=\widehat{m}^{i}$. In fact, although all the dynamics (12) run altogether, the estimates are sequentially obtained. That is, $z_{k}^{i}$ starts converging to its proper value after $\langle x_{i}\rangle$ becomes $N$, and $y_{k}^{i}$ starts converging to its proper value after $\langle z_{k}^{i}\rangle$ becomes the $k$-th smallest element. Therefore, the required time for getting the mode is still the same as ${\mathcal{T}}_{x}+{\mathcal{T}}_{y}+{\mathcal{T}}_{z}$.

Algorithm 2 that repeats forever, and the alternative algorithm (12) are plug-and-play ready as long as the admissible changes occur with the dwell time ${\mathcal{T}}_{x}+{\mathcal{T}}_{y}+{\mathcal{T}}_{z}$. This is because, with $x_{i}(t_{j})\in{\mathcal{K}}_{x}$, $z_{k}^{i}(t_{j})\in{\mathcal{K}}_{z}$, and $y_{k}^{i}(t_{j})\in{\mathcal{T}}_{y}$ at the time of change $t_{j}$, the same inclusion holds at the next time of change $t_{j+1}$; i.e., $x_{i}(t_{j+1})\in{\mathcal{K}}_{x}$, $z_{k}^{i}(t_{j+1})\in{\mathcal{K}}_{z}$, and $y_{k}^{i}(t_{j+1})\in{\mathcal{T}}_{y}$.

From (12) we see the number of the state variables needed in Algorithm 2 equals $2K+1$ (or $2K-1$ if $\left\lceil{\frac{N}{K}}\right\rceil>{\frac{N}{K}}$). Thus Algorithm 2 uses less state variables than Algorithm 1 if $2K+1<\left|\Omega\right|$ (or $2K-1<\left|\Omega\right|$ when $\left\lceil{\frac{N}{K}}\right\rceil>{\frac{N}{K}}$). In particular, If $K=1$, the mode consensus problem reduces to the max consensus of $\{l(a_{1}),\dots,l(a_{N})\}$ since $l(a^{*})$ is the $N$-th smallest element; If $K=2$, the problem reduces to finding the attributes having larger frequency between the median and the maximum of $\{l(a_{1}),\dots,l(a_{N})\}$ (if $N$ is odd, it is simply the median); If $K=|\Omega|$, Algorithm 2 probably has to do the $k$-th smallest element consensus $|\Omega|$ times, and then it offers no advantage over Algorithm 1. Since $f^{*}\geq\left\lceil\frac{N}{|\Omega|}\right\rceil$, it is not necessary to consider $K>|\Omega|$ because the condition $f^{*}\geq\left\lceil\frac{N}{K}\right\rceil$ is automatically fulfilled. Thus to choose Algorithm 2 over Algorithm 1 it is preferable to have $2K+1\ll|\Omega|$.

When $f^{*}$ is unknown, we are not able to employ Algorithm 2. However, once we determine a value of ${\mathcal{F}}(a)$ for some attribute $a$, then we can immediately infer that $f^{*}\geq{\mathcal{F}}(a)$. Based on this simple fact, we begin with an estimate $F$ of $f^{*}$ with $F=1$, and update $F$ by ${\mathcal{F}}(a)$ whenever an attribute $a$ such that ${\mathcal{F}}(a)>F$ is found. At the same time, we begin with $K=1$ and repeatedly increase $K$ until it holds that $F\geq\lceil\frac{N}{K}\rceil$. Once we have $F\geq\lceil\frac{N}{K}\rceil$, it means that the integer corresponding to the mode $a^{*}$ is among the $j\left\lceil{\frac{N}{K}}\right\rceil$-th smallest elements, $j=1,\dots,K$, of $\{l(a_{1}),\dots,l(a_{N})\}$, so that the previous algorithm can be applied. Putting all this together, we obtain Algorithm 3.

In the algorithm, Steps 5) and 6) can be made more efficient by storing data obtained in the previous loop, but in the worst case scenario, the “While” loop should be run $K^{*}$ times, where $K^{*}$ is the smallest positive integer such that $f^{*}\geq\lceil\frac{N}{K^{*}}\rceil$. Analogously to the analysis for Algorithm 2, the number of state variables needed in Algorithm 3 equals $1+\sum\nolimits_{i=1}^{{K^{*}}}2i=K^{*}\left(K^{*}+1\right)+1$. To choose Algorithm 3 over Algorithm 1 it is preferable to have $K^{*}\left(K^{*}+1\right)+1\ll|\Omega|$. If in addition, Algorithm 3 is executed with parallel computations, the time to reach mode consensus is less than ${\mathcal{T}}_{x}+K^{*}\left({\mathcal{T}}_{y}+{\mathcal{T}}_{z}\right)$.