{'fraction_non_alphanumeric': 0.04704661729455118, 'fraction_numerical': 0.01194948302386319, 'mean_word_length': 4.047309498013723, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Resilient Self/Event-Triggered Consensus Based on Ternary Control

The paper considers the problem of multi-agent consensus in the presence of adversarial agents which may try to prevent and introduce undesired influence on the coordination among the regular agents. To our setting, we extend the so-called mean subsequence reduced algorithms with the aim to reduce the amount of communication via two measures: The agents exchange information in the form of ternary data at each transmission and moreover keep the frequency of data exchange low by employing self- and event-triggered communication. We will observe that in hostile environments with adversaries, the self-triggered approach can bring certain advantages over the event-triggered counterpart.


I. INTRODUCTION
The study of multi-agent systems for distributed coordination has received a lot of attention in the field of systems control. In such systems, a number of agents form a network over which they communicate with each other using wired or wireless channels and individually make decisions to achieve their global objectives [1]. The increase in networking has brought about new critical issues related to cybersecurity to multi-agent systems [2], [3]. Even if the adversarial attacks are local and limited to a small portion of the agents, misbehaviors of them can potentially harm the overall system performance. Thus, development of methods robust to such attacks has become of great importance.
Resilience in consensus-type algorithms against malicious adversaries has been long studied in the area of fault-tolerant distributed algorithms in computer science [4]. Our approach follows this line of research, which has recently become active in the systems control community. The basic problem setting is as follows: The agent network is known to contain up to F adversarial agents whose identities are unknown to the nonfaulty, regular agents. The adversarial agents may harm the consensus process as they can transmit false data to their neighbors to be used in their updates. The result can be that consensus takes place at dangerous values or the agents may even be split into disconnected groups.
For resilient consensus, the class of mean subsequence reduction (MSR) algorithms is effective to mitigate the influence of adversaries. With the knowledge of the bound F on the number of adversaries, the agents will disregard neighbors whose states take especially large or small values. This type of algorithms has been applied to consensus problems with agents' states taking real values (e.g., [5]  though most of the past studies have been limited to networks of complete graphs; however, the use of such networks is very limited in practice. More recently, noncomplete graph cases have been addressed and topological conditions in terms of robust graphs have been obtained [6], [7]. The MSR approach for multi-agent consensus has been extended to quantized states [8], agents with higher order dynamics [9], [10], and applications to robotic networks [11] and clock synchronization of wireless sensor networks [12].
In this paper, we place special emphases on the reduction of communication load for the interactions among agents. This is to be achieved by two measures: One is by transmissions of very coarse data by quantization using only ternary outputs [13], [14]. The simple data expression is helpful not only in keeping the information minimal in each data sent, but also in reducing the number of transmissions; if the data to be sent is the same as the previous time, this communication can be accomplished implicitly.
The other is to reduce the transmission frequency via event-based communication techniques (e.g., [15], [16]). In particular, we employ the self-triggered control approach [14], [16]- [18], under which the agents determine their next update and transmission times dynamically according to the values received from other agents and its own. This enables the system not to respond to data received before the next update instant comes. It turns out that this feature is useful in hostile environments, where adversaries may make unnecessary communication to disturb others or to jam the communication. By contrast, in the similar, but more popular approach of event-triggered control (e.g., [16], [19], [20]), agents must make updates in their values each time data is received; this is because the agents must check if the current state is sufficiently different from the one last transmitted, in which case the next transmission will be made.
For comparison reasons, in this paper, we propose resilient consensus protocols by incorporating the MSR algorithm into both self-triggered and event-triggered protocols with ternary control. It will be found that from the theoretical viewpoint, the two protocols can be treated in a similar manner. Both protocols are capable in achieving resilient consensus via asynchronous update even when time delays are present in communication [21]. Furthermore, in both protocols, the control input for each agent is quantized into three values of −1, 0, and 1 [14]. From the perspective of quantized consensus [8], [22]- [24], it is notable that many existing consensus algorithms rely on randomizationbased techniques in the update rules; these are needed for completing consensus in a finite number of updates (in a probabilistic sense). We highlight that our approach is deter-arXiv:2012.13158v1 [eess.SY] 24 Dec 2020 The paper is organized as follows: In Section II, we provide the problem formulation and introduce the selftriggered protocol with ternary control. In Section III, we present the MSR-based algorithm and the result on resilient consensus. Section IV discusses the event-triggered version of the resilient algorithm. In Section V, we compare the two event-based algorithms via a numerical example. We conclude the paper in Section VI.

A. Preliminaries on graphs
Consider the directed graph G = (V, E) with the set V = {1, 2, ..., n} of nodes and the set E ⊂ V × V of edges. The edge (j, i) ∈ E indicates that node j can send a message to node i and is called an incoming edge of node i. Let N i = {j : (j, i) ∈ E} be the set of neighbors and let d i = |N i | be the degree of node i. The graph is said to be connected if for any pair of nodes, there is a sequence of edges from one to the other. Denote by A the Laplacian matrix of G.
To establish resilient consensus results, we introduce an important topological notion of robustness for graphs [6]. Definition 1. The graph G = (V, E) is called (r, s)-robust (r, s < n) if for every pair of nonempty, disjoint subsets V 1 , V 2 ⊆ V, at least one of the following holds: Vi is the set of all nodes in V i which have at least r neighbors outside V i for i = 1, 2. The graph is said to be r-robust if it is (r, 1)robust.
In Fig. 1, we display two example graphs with four nodes. The graph (a) is not 2-robust because any of the nodes in the subgraphs surrounded by the dotted lines has just one neighbor outside the subgraph to which it belongs. On the other hand, it can be confirmed that the graph (b) is 2-robust from the definition.

B. Self-triggered consensus protocol
We introduce the self-triggered consensus protocol based on the ternary controller for the agents to achieve consensus [14]. In this protocol, each agent i has the state variable x i , the control u i (which is quantized to a ternary value), and the local clock variable θ i . All these variables are defined for time t ≥ 0. Each agent triggers update events and transmission events depending on its own clock.
1) Dynamics in the hybrid system format: We express the self-triggered dynamics for each agent i ∈ V as a hybrid system consisting of three variables x i , u i , and θ i . At time t, these states satisfy the following continuous evolution: except for every t such that the timer variable θ i (t) becomes zero. Such time instants are called the self-triggered times and are denoted by {t i m } m∈Z+ with t i 0 = 0 and t i m < t i m+1 . The set of all self-triggered times is given by Moreover, let U(t) be the set of nodes whose self-triggered times are equal to t, that is, At such time instants {t l }, agent i's states follow the discrete evolution given by where the map f ε (z) : R → R with the sensitivity parameter ε > 0 is defined as Also, let ave i (t) be the weighted average of the relative states of the neighbors given by where a ij (t) is the (i, j)th entry of the (possibly timevarying) adjacency matrix A(t) ∈ R n×n corresponding to G, which satisfies α ≤ a ij (t) < 1 when a ij = 0 and α is the lower bound with 0 < α ≤ 1/2. Furthermore, τ i j (t) denotes the time delay in the communication from agent j to agent i at time t. The variable x j (t) is the state value of agent j most recently received and stored by agent i. More specifically, it is given by m of time interval since agent i's last update. Regarding the delay time in communication, we assume that it is upper bounded for any i, j, t by τ as The algorithm for each agent i based on the evolutions (1),(2) can be described as follows: Agent i has the local clock θ i (t), which decreases as time passes by. When its clock reaches 0 at time t, it computes the weighted average ave i (t) based on the states x j (t) received from its neighbors so far. Then, it sends its updated state value x i (t) = x i (t) to its neighbors. This protocol differs from the one proposed in [14] in not using x j (t) but using x j (t) to update. This means that there is no need for agents to send request to neighbors to receive the neighbors' value at time t. As a result, we can apply the protocol to directed graphs.
2) Dynamics in the discrete system formulation: In the dynamics of the hybrid protocol discussed above, for each agent i, the interval time length of the discrete evolution times is at least ε. Also the variable We can interpret the dynamics as a discrete-time system by focusing on the evolution at times {t l }.
To simplify the notation, we denote the variables with discrete time k ∈ Z + as Then the self-triggered algorithm for agent i can be represented in discrete time as Further, the update rule of and regarding the delay time in communication, we assume that it is upper bounded by τ for the given τ in (4) and any i, j, k as

C. Adversarial model and resilient consensus
Now, we consider the situation where some of the nodes in the network are faulty or even adversarial. The objective here is to keep the nonfaulty, regular nodes from being affected by such adversarial ones. Here, we introduce the class of adversarial nodes considered in this paper.
The nodes in V are partitioned into two sets: R denotes the set of regular nodes and A = V \ R represents the set of adversarial nodes. The regular nodes will update their controls u i following the designed algorithm exactly while the adversarial nodes can update u i arbitrary. Here, let n R = |R|, n A = |A|. The attacker is allowed to know the states of the regular nodes and the graph topology and to choose any node as a member of A under some constraints.
For the class of adversarial nodes, we employ the malicious model defined as follows [6]. Definition 2. (Malicious nodes): We say that an adversarial node is malicious if it sends the same value to all of its neighbors at each transmission.
Adversarial nodes more difficult to deal with are those that can send different values to different neighbors in an arbitrary way. Such nodes are called Byzantine nodes [7].
In our problem setting, the identities of the malicious nodes are unknown, but we assume the prior knowledge on the maximum number of malicious nodes in the network. This is a common assumption employed in the literature of fault-tolerant distributed algorithms [4]. More specifically, we introduce the following models.
Definition 3. (F -total and F -local models): This paper deals with networks of the F -total model. In this context, the notion of resilient consensus for multiagent systems is now given [25].
Definition 4. (Resilient consensus): Given c ≥ 0, the multi-agent system is said to reach resilient consensus at the error level c if for any possible sets and behaviors of the malicious agents and any initial state values of the regular nodes, the following conditions are satisfied.
1. Safety condition: There exists an interval S ⊂ R determined by the initial states of the regular agents such that The multi-agent problem of this paper can be formulated as follows: Given c ≥ 0, design event-based update rules for the regular agents so that they reach resilient consensus at the error level c under the F -total model.

III. SELF-TRIGGERED CONSENSUS PROTOCOL
A. E-MSR algorithm As mentioned above, every agent updates its state value at every time by the ternary input, but only when an update event happens, the auxiliary values will be updated using values from its neighbors. For reaching resilient consensus, we apply an algorithm where each regular agent ignores some neighbors suspected to be behaving maliciously.
The algorithm given below follows the one from [25] called the event-based mean subsequence reduced (E-MSR) algorithm.
1. (Collecting neighbors' values) At time t, every regular node i ∈ R possesses the values x i (t) (or x i (t)), most recently sent from the neighbors as well as its own value x i (t) and sorts them in ascending order. The weight a ij (t) of ignored neighbor j is set to 0 temporarily.

B. Self-triggered resilient consensus protocol
In the self-triggered consensus protocol based on the ternary controller, to reach resilient consensus, the discrete evolution (2) can be replaced by introducing the E-MSR algorithm with the following: Also, in the discrete-time system form, (5) and (6) can be replaced with (13) For ease of notation, we reorder the indices of the agents. Let the regular agents take indices 1, ..., n R and let the malicious agents be n R + 1, ..., n. Then the system variables are partitioned into the regular and malicious parts as As the neighbors' information can be delayed as shown in (8), each agent i updates x i with the state values up to τ steps before. Thus let . And rewrite the update rule (12) for x as Here, W τ [k] is the n × (τ + 1)n matrix defined as follows: where L τ [k] is given by apply E-MSR setp 2 and set M i (t) 12: The input for the malicious agents is given as u A [k] ∈ R n A , which can be manipulated arbitrarily, Here, let ω be the minimum nonzero element of all possible cases of W τ [k] over all k. By the bound α on a ij [k], we have ω ∈ (0, 1). Then we are ready to present the algorithm that each agent follows to reach resilient consensus. The protocol given in Algorithm 1 represents the self-triggered resilient consensus protocol based on the ternary controller.

C. Resilient consensus analysis
By adopting the MSR technique in the ternary event-based control for consensus as in (9), we obtain the following main result of this paper.
Theorem 1: Under the F -total malicious model, the regular agents with the E-MSR algorithm in the multiagent system reach resilient consensus at error level c if the network topology is (2F + 1)-robust. The safety interval is given by S = [min x R [0], max x R [0]], and the error level c is achieved if the parameter ε satisfies Proof: We show that the update rule in (11) meets both safety and consensus conditions. 1) Safety condition: We must prove that the state value of regular agents satisfy x i [k] ∈ S for all i ∈ R, k ∈ Z + . First, we define By (14), x i [k + 1] is given by the convex combination of the entries of z[k] for the regular agent i at step k. If some of the neighbors are malicious and lie outside the range of the regular agents' values, then they will be ignored by step 2 in the E-MSR algorithm. Consequently, max x R [k + 1] ≤ z[k] always holds. Hence, z[k + 1] meets As a result, z[k] is nonincreasing and it holds that . Further, at each step k ∈ (k i l , k i l+1 ] for the regular agent i by the event-based control, it holds either . Thus, it holds: Likewise, we can show and thus the safety condition is satisfied. 2) Consensus condition: We first sort the regular agents' values in the vector z R [k] at step k in ascending order. Denote by s i [k] the index of the agent taking the ith value from the smallest. Hence, the values are sorted as Introduce two sequences of conditions for the bound of gaps between two agents. The condition sequences {ASC l } and {DESC l } are defined as follows: ≤ ε/ω (τ +1)n−1 . Now, denote by j A the minimum j, 1 ≤ j < (τ + 1)n, such that the condition ASC j is not satisfied. Also, denote by j D the maximum j, 1 < j ≤ (τ + 1)n, such that the condition DESC j is not satisfied. Then we have Furthermore, the conditions ASC 1 to ASC j A −1 and DESC j D +1 to DESC (τ +1)n−1 are satisfied. Also, for 0 ≤ k ≤ k , we introduce the following sets: By the nature of these two sets, every entry of the condition sequences ASC, DESC is finally satisfied as step grows and we can show the consensus condition. We study them separately according to the relation of j A , j D and X 1 (k, k), X 2 (k, k). Case 1. j A < j D : There are four subcases, denoted by (1-a) to (1-d), which are separately studied below.
(1-a). X 1 (k, k) = φ, X 2 (k, k) = φ: For a regular agent j / ∈ X 1 (k, k), by definition, it holds , then values less than z[k] = z s1 [k] will be ignored. Additionally since the update is based on the convex combination as shown in (14) and ω is the lower bound of the elements of W τ [k], it holds Using the conditions ASC 1 to ASC j A −1 , we can bound z s1 from below as Substituting this into (19), we can obtain (20) On the other hand, for an agent j / ∈ U[k], we have Thus, we can derive j / ∈ X 1 (k, k) ⇒ j / ∈ X 1 (k, k + 1).
This means that if an agent does not belong to X 1 (k, k), then it will not belong to X 1 (k, k ) at step k > k either. Likewise, for X 2 (k, k), we can show j / ∈ X 2 (k, k) ⇒ j / ∈ X 2 (k, k + 1).
Next, X 1 (k, k) and X 2 (k, k) are disjoint because Thus, the graph being (2F + 1)-robust guarantees that there is at least one agent i satisfying i ∈ X 1 (k, k) with |N i \ X 1 (k, k)| ≥ 2F + 1 or i ∈ X 2 (k, k) with |N i \ X 2 (k, k)| ≥ 2F + 1. Here we first consider the case where i ∈ X 1 (k, k). There exists l such that k ≤ k i l ≤ k + τ and And thus for agent i, it holds that i ∈ X 1 (k, k i l ). By (21), it also holds that |N i \ X 1 (k, k i l )| ≥ 2F + 1. Hence, in the update of agent i at step k i l , there is at least one neighbor j whose value satisfies x j [k i l ] > z sj A [k] + ε. Thus like (20), we have . In this way, using (21) and (23), we have and thus after τ steps, the cardinality of X 1 (k, k + τ ) is smaller than that of X 1 (k, k). Similar results also hold for the case i ∈ X 2 (k, k), and the cardinality of X 2 (k, k + τ ) will be smaller than that of X 2 (k, k) after τ steps. If the two sets are nonempty, we can repeat the steps above. As a result, |X 1 (k, k + τ n)| = 0 or |X 2 (k, k + τ n)| = 0 is derived. It means that z will decrease by ε (or z will increase by ε) after τ n steps.
Case 2. j A ≥ j D : This case is in fact impossible. This is because it would imply that ASC j D −1 and DESC j A −1 are both satisfied. Thus we have ε/ω These inequalities indicate that it must hold j D > (n + 1)/2 and j A < n/2. Consequently, we have j A < j D and it contradicts with the condition j A ≥ j D .
If j A and j D continuously exist, then z[k] − z[k] will become smaller and eventually negative, which cannot happen. Hence, we can conclude that after finite time steps, all conditions of {ASC l } and {DESC l } are satisfied to stop the value z[k] decreasing and z[k] increasing. This completes the proof.
The proof technique used above is inspired by the one in [25], which is for event-triggered communication in resilient consensus. There, we have provided two approaches for the consensus algorithms. In this paper, we adopted one of them (Protocol 2), for which a more tight result can be obtained for approximate consensus. The result in Theorem 1 is more general, allowing time delays in the communications, though with no delay we can establish a necessary and sufficient condition for resilient consensus, stated in terms of (F + 1, F + 1)-robustness, instead of the sufficient condition in Theorem 1. From the technical viewpoint, the presence of delays necessitates a change in the sequences of conditions ASC and DESC. In particular, they are stated in terms of the value z, which includes delayed values. As a result, we must consider the four subcases in Case 1 in the proof. When no delay is present, these subcases reduces to one since neither X 1 (k, k) nor X 2 (k, k) may be empty.
It is also interesting to note that the framework in [25] can be extended to ternary controller of [14] which operates in continuous time. This is because the consensus algorithm under ternary controller can be expressed as a hybrid system, which can be further interpreted as a discrete-time system by focusing on the times when events take place. This proof approach is different from that in [14], which also considers networks operating on undirected graphs.

IV. EVENT-TRIGGERED CONSENSUS PROTOCOL
We provide the event-triggered resilient consensus protocol based on ternary controller. This protocol is introduced to compare with the self-triggered protocol because it works in the same setting as the self-triggered one. In this protocol, agent i does not have the local clock variable θ i but instead the triggering threshold η i . Each agent triggers update events when it receives a value and transmits events when its value x i exceeds η i . Let U(t) be the set of agents which trigger a communication event at time t.
For the continuous time t, the system (x, u, η) ∈ R 2n satisfies the following continuous evolution except for every t such that the set U(t) is non-empty.
To define the rule of triggering communication events, we define x j (t) with t j k < t ≤ t j k+1 for agent j by and let the value h i (t) for agent i at time t be Here, agent i communicates at the time instants when h i (t) becomes 0 or more. Then at time instants t = t j k + τ i j (t j k ) (k ≥ 0, j ∈ N i ) for agent i, the system satisfies the following discrete evolution: where ave M i (t) is given by The event-triggered resilient consensus protocol of these evolutions (25) and (26) is the following: Each agent i has own threshold η i . When its error | x i − x i | reaches η i , it sends the value x i = x i to neighbors. At the time when an agent receives values, it updates control u i and η i with value x j = x j to which recently send from its neighbors. This is formally shown in Algorithm 2.
In the event-triggered consensus protocol based on ternary controller, we can also prove to reach the same resilient consensus such as self-triggered one.

V. NUMERICAL EXAMPLE
In this section, we illustrate the effectiveness of the two proposed resilient consensus protocols and compare their performance with the conventional nonresilient counterpart. Algorithm 2 P M eve : Continuous Evolution for agent i ∈ R 1: Initialize: u i (0) ∈ {−1, 0, 1}, η i (0) = 0 2: if agent i receives x j (t) from agent j ∈ N i then 3: agent i stores x j (t) 4: apply E-MSR step 2 and set M i (t) 5: set u i (t + ) = sign(f ε ( ave M i (t))) 6: x i (t) = x i (t) 10: for all j ∈ N i do 11: agent i send x i (t) to agent j 12: end for 13: end if

A. Small network with 3-robust property
First we consider the multi-agent system with 8 nodes whose connectivity graph is shown in Fig. 2. We can check that it meets the condition to be 3-robust. For the three protocols, we use common initial states x(0) = [0, 1 6 , 1 3 , 1 2 , 2 3 , 5 6 , 1, 1 2 ]. The bound on time delay is set as τ = 0.1. The adversary is taken to be agent 8, which will continuously oscillate its state by following a sine curve. We also took the sensitivity parameter ε = 0.1. Here, the malicious agent sends its values once every ε time length.
The conventional self-triggered protocol of [14] is not resilient against the adversary. The time responses of the agents' states are shown in Fig. 3. Also, in the plot, the dots indicate the transmission time instants of the agents, whose colors match those of the states. It is clear that the agents are influenced by the adversary. Their states change over time and transmissions do not stop.
The simulation results for the proposed self-triggered and event-triggered resilient protocols are shown in Figs. 4 and 5, respectively. We observe that these protocols manages to achieve the desired level of error in consensus. Moreover, the regular agents stop transmitting after they reach consensus. These protocols are thus more efficient in the amount of communication in comparison with the sampling-based timetriggered protocols.

B. Random networks
Next, we consider a larger multi-agent system with 100 nodes whose underlying graph is a random geometric network. We placed 100 nodes randomly within a field of a unit square. The nodes have a common communication range r and communicate with neighbors within the range.
1) Consensus success rates: First, we demonstrate how the proposed protocols perform over such random graphs where the robustness property cannot be guaranteed since the network is too large. Here, we examined the communication range r ∈ (0, 0.5] and used different numbers for the malicious agents as n A = 0, 3, 5. The malicious agents here changed their controls randomly within the range [−10, 10] and sent a message every ε time length, where the sensitivity parameter was set as ε = 1. Fig. 6 displays the success rates of consensus for the three cases with n A = 0, 3, 5 for the self-triggered resilient protocol obtained from 100 Monte Carlo simulations. The success rate with no malicious agent (n A = 0) matches the rate of the network being connected. Observe that to achieve consensus with more malicious agents, more connectivity is required for the network. However, it is clear that the network need not be complete for the success rate to reach 1. The results for the event-triggered control are almost the same and hence not indicated in the plot.
2) Comparison between the two protocols: Next, we highlight the difference between the two resilient protocols, which has not been evident in the theoretical results or from the experiments so far. We show that the self-triggered approach is advantageous in keeping the number of update events minimal. To this end, we run simulations for both protocols and compare the numbers of updates and transmissions per regular agent until time t = 20. Here, we used the random network with the communication radius at r = 0.4. Table I displays the average numbers over 50 Monte Carlo simulations. The total numbers of messages sent by the regular agents were about the same for both protocols and remain constant regardless of the size of n A .
On the other hand, a clear difference arises in the numbers of updates. For the event-triggered protocol, this number is in general larger than that for the self-triggering protocol. However, we see that it is more vulnerable to the malicious agents; the number of updates increases for larger n A since the agents must make an update each time a message is received from neighbors and in particular, under the setting here, the malicious agents transmitted messages very frequently. In contrast, for the self-triggered protocol, the number did not change by n A and is one fifth of that for the other protocol.

VI. CONCLUSION
We have proposed consensus protocols resilient to attacks from malicious agents based on self-and event-triggered consensus protocols using ternary control. The resilience is achieved by applying the MSR-type techniques while the communication among the agents is efficient and robust to networks in uncertain environments with limited communication resources.