
% This is a template for the fbe_tez.sty, v4.1 (and maybe later).
%
%
\documentclass[12pt]{report}
\usepackage{fbe_tez}

\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsthm}
%\usepackage[a4paper, total={6in, 10in}]{geometry}
%
% LaTeX 2.09 users: Replace the above two lines with the following line
%\documentstyle[12pt,fbe_tez]{report}
%
% Declarations
%
\title{NOVEL FAULT-TOLERANT DISTRIBUTED ALGORITHMS FOR APPROXIMATE BYZANTINE CONSENSUS}
\turkcebaslik{B\"UY\"UK HARFLERLE TEZ\.IN T\"URK\c CE ADI}
\degree{B.S., Electrical-Control Engineering, University of Tabriz, 2011}
\author{Ali Haseltalab}
% The \program declaration is needed only for M.S. theses
\program{Electrical and Electronics Engineering}
%\subyear{20xx}
%
% Declare relevant examiners
%
\supervisor{Associate Professor Dr. Mehmet Akar}
%\cosuperi{Title and Name of Cosupervisor I}
%\cosuperii{Title and Name of Cosupervisor II}
\examineri{Professor Dr. Ya\u{g}mur Denizhan}
\examinerii{Professor Dr. M. Ufuk \c{C}a\u{g}layan}
%\examineriii{Title and Name of Examiner}
%\examineriv{Title and Name of Examiner}
%\examinerv{Title and Name of Examiner}
\dateofapproval{Day.Month.Year}

\begin{document}
\pagenumbering{roman}
%
% Choose the relevant one
\makemstitle        % For M.S. theses
%\makephdtitle      % For Ph.D. theses
%\makeproposaltitle % For Proposals

\makeapprovalpage

\begin{acknowledgements}
This thesis would not have been possible without help of so many people in so many ways. I would like to express my deepest appreciation to my supervisor Assoc. Prof. Mehmet Akar who continually and convincingly conveyed the spirit of adventure in regard to science to me. His patience, support and advice throughout my study for Master of Science degree were outstanding and memorable. 

 I would like to thank Prof. Ya\u{g}mur Denizhan for her invaluable guidance throughout my study and serving as a member of my thesis jury. Furthermore, I thankfully appreciate Prof. Ufuk \c{C}a\u{g}layan for doing me a favor by taking part in my thesis jury.
 
 I am grateful to my dear colleagues in the Networked and Embedded Control Systems Laboratory, \"{O}zlem Feyza Erkan, Onur Cihan, Huzeyfe Esen and Kamil \c{S}enel, for their ultimate support and cooperation throughout the stages of my study. Moreover, I would like to thank my other colleagues and friends especially the Iranian students community at Bo\u{g}azi\c{c}i University for helping me survive all the stress during this study and not letting me give up.
 
 There is no word to describe the priceless and endless support of my family, not only in the last two years, but throughout every single stage of life. I would like to dedicate my sincerest gratitude to my parents Hassan Haseltalab and Faride Ghozat and my brother Omid Haseltalab for pushing me forward in my studies.
 
 Last but not least, as an international student, I am indebted to people of Turkey as a solid and strong nation with a notable background. Their hospitality as well as kindness and support conducted the warm sense of home to me during this era.
 
 This thesis is partially supported by the Scientific and Technological Research Council of Turkey (TUBITAK) under Grant 110E196.
 
 
\end{acknowledgements}

\begin{abstract}
Reaching consensus in a network which contains faulty nodes is a critical problem in the field of distributed and multi-agent systems. A distributed system which intends to do a certain task needs to display robustness against adverse behavior of some of its faulty nodes, known also as Byzantine nodes.

In this thesis, a novel \textit{Mean-Select-Reduced} (MSR) fault tolerant algorithm is proposed for achieving Approximate Byzantine Consensus. It is shown that the topological condition required for the success of the algorithm is more relaxed compared to the previous results. In contrary to results that appeared in the literature, it is proved that synchronicity of networks and presence of delay on communication paths do not change this condition. Subsequently, the convergence rate and time analysis for the proposed fault-tolerant algorithm is carried out and the results are extended to time-varying networks. Furthermore, the existence of a common Lyapunov function for time-varying faulty networks is analyzed.

In most of the fault-tolerant algorithms that have been introduced
for Byzantine networks, it is assumed that each node has knowledge of the maximum number of faulty nodes, $f$, in the network. In this thesis, we also propose a new family of algorithms which do not require this a priori information and evaluate their performance facing Byzantine failures.

\end{abstract}
%
% The usage of the "foreword" and "preface" environments are similar
% the "abstract" and "acknowledgements". See FBE manual for the
% correct order of these pages in the thesis.
%
\begin{ozet}
T\"urk\c ce tez \"ozetini buraya yaz\i n\i z.
\end{ozet}

\tableofcontents
\listoffigures
\listoftables

\begin{symbols}
% The title will be typeset as "LIST OF SYMBOLS/ABBREVIATIONS".
% If you prefer it as "LIST OF SYMBOLS" or "LIST OF ABBREVIATIONS"
% use the environments "symbols" or "abbreviations", respectively.
%
% Use a separate \sym command for each symbols definition.
% First Latin symbols in alphabetical order
\sym{$A$}{The adjacency matrix of graph G}
\sym{$a_{ij}$}{Elements of the adjacency matrix of a graph}
\sym{$C$}{The semi-transition matrix of a network}
\sym{$c_{ij}$}{Elements of matrix $C$}
\sym{$E$}{The set of edges of graph $G$}
\sym{$E_i$}{The set of eliminated values by node $i$ in the MSR algorithm}
\sym{$e$}{The maximum synchronization error}
\sym{$F$}{The set of faulty nodes in a network}
\sym{$f$}{The maximum number of faulty nodes in a network}
\sym{$f_t$}{The number of faulty nodes in a network}
\sym{$f_a$}{The elimination parameter of the MSR algorithm}
\sym{$G$}{The underlying directed graph of a network}
\sym{$H_{\chi_i}$}{The higher bound for convex hull of node $i$}
\sym{$i_{re}$}{The indice of reachability}
\sym{$i_{ro}$}{The indice of robustness}
\sym{$L_{\chi_i}$}{The lower bound for convex hull of node $i$}
\sym{$M$}{The maximum state value of the set of non-faulty nodes}
\sym{$m$}{The minimum state value of the set of non-faulty nodes}
\sym{$N_i$}{The set of neighbors of node $i$}
\sym{$N_i'$}{The set of acceptable state values received by $i$}
\sym{$N_{chi_i}$}{The set of nodes with convex hulls acceptable for node $i$}
\sym{$n$}{Total number of nodes in a graph}
\sym{$\mathbb{R}$}{The set of real values}
\sym{$r$}{The number of update round}
\sym{$t$}{The indice of time}
\sym{$t_r^i$}{The update time of node $i$ at round $r$}
\sym{$t_{M_r}$}{The maximum sequence of time in a network}
\sym{$t_{m_r}$}{The minimum sequence of time in a network}
\sym{$V$}{The set of vertices of graph $G$}
\sym{$W$}{The transition matrix of a network}
\sym{$x$}{The vector of state values}
\sym{$x_i$}{The state value of node $i$}
\sym{$x_{ij}$}{The state value of node $j$ received by node $i$}
\sym{}{}
% Then Greek symbols in alphabetical order
\sym{$\alpha$}{The minimum of $\omega_{ij}$ weights}
\sym{$\alpha_t$}{The maximum update time interval of non-faulty nodes in a network}
\sym{$\alpha_\tau$}{The maximum communication delay between two non-faulty nodes in a network}
\sym{$\beta_t$}{The minimum update time interval of non-faulty nodes in a network}
\sym{$\gamma(W)$}{The ergodicity value of transition matrix $W$}
\sym{$\gamma'(W)$}{The ergodicity value of the network of non-faulty nodes of transition matrix $W$}
\sym{$\Delta t_r^i$}{The time interval between two successive update in state of node $i$}
\sym{$\Delta t_M$}{The sum of maximum update time interval and maximum communication delay in a network}
\sym{$\epsilon$}{A chosen consensus accuracy level}
\sym{$\kappa_M$}{The subset of non-faulty nodes in a network with state value $M$}
\sym{$\kappa_m$}{The subset of non-faulty nodes in a network with state value $m$}
\sym{$ \xi$}{The set of semi transition matrices of a time-varying faulty network}
\sym{$\tau_{ij}$}{The communication delay between two nodes $j$ and $i$}
\sym{$\tau_e$}{The maximum time for decrease of maximum synchronization error $e$}
\sym{$\Phi$}{The set of underlying graphs of a time-varying network}
\sym{$\Phi'$}{The set of underlying graphs in which the network of non-faulty nodes has at least $(f_a+1)$-robust topology }
\sym{$\chi_i$}{The convex hull of node $i$}
\sym{$\omega_{ij}$}{The averaging coefficients}
\end{symbols}
\begin{abbreviations}
\sym{LCA}{Linear Consensus Algorithm}
\sym{MSR}{Mean-Select-Reduced}
\sym{SCH}{Shrinking Convex Hulls}
\sym{SCH-CBN}{Shrinking Convex Hulls for Complete Byzantine Networks}
\sym{SCH-CMN}{Shrinking Convex Hulls for Complete Malicious Networks}
\sym{W-MSR}{Weighted Mean-Select-Reduced} 
\end{abbreviations}

\newtheorem{definition}{Definition}[chapter]
\newtheorem{example}{Example}[chapter]
\newtheorem{remark}{Remark}[chapter]

\chapter{INTRODUCTION}
\pagenumbering{arabic}



In a distributed system in which a common task is intended to be accomplished, the individual nodes of the system are required to reach \textit{Consensus} on one or more common values. The problem of reaching consensus in a network has received considerable attention recently. It is employed in many fields such as collective behavior of flocks and swarms \cite{1605401},\cite{1304923}, formation control \cite{1381658},\cite{1582430},\cite{4140748} and control of distributed systems \cite{Das20102014}, \cite{QuCooperative}, \cite{4760250}, etc.

 One of the most popular distributed algorithms for achieving consensus is the linear consensus algorithm \cite{1205192}, \cite{4118472}. In this algorithm, each node receives the state value of its neighbor nodes in each iteration. Then, it takes a weighted-mean to update its state using its own current state value and the received state values. It is proved that the state values of all nodes converge to a common value if and only if the underlying graph of the network contains a rooted out branching \cite{1205192}, \cite{1393134}, \cite{4118472}. Moreover, this problem has been well considered in networks with time-varying underlying graph \cite{1431045}, \cite{1333204}.

In real-life applications, there might exist some nodes that represent adverse behavior due to malfunctioning. Moreover, a network may face an intruder node which tries to prevent the other nodes reaching consensus. Existence of these faulty nodes necessitates the adoption of fault-tolerant algorithms which allow non-faulty nodes to achieve consensus on a common value.

Reaching consensus in a network which contains faulty nodes is a critical problem in the field of distributed and multi-agent systems. A distributed system which intends to do a certain task needs to display robustness against adverse behavior of some of its faulty nodes, known also as Byzantine nodes. Byzantine failure is intended to model any unbounded malfunction of network components \cite{Lynch:1996:DA:525656}. This problem was first introduced in \cite{Lamport:1982:BGP:357172.357176} in terms of Byzantine generals who need to reach agreement on a common action while some of them are traitors and attempt to prevent the agreement. In \cite{Lamport:1982:BGP:357172.357176}, \cite{Pease:1980:RAP:322186.322188}, it is shown that using the suggested algorithm and decision making rules, reaching consensus is guaranteed if and only if, $n>3f$ where $n$ is the total number of generals and $f$ is the number of traitor generals. Subsequently, in \cite{Lynch:1996:DA:525656}, \cite{Pease:1980:RAP:322186.322188}, it is proved that there exists no algorithm that can tolerate $f$ number of faulty nodes if $n\leq 3f$. It might worth mentioning that more restrictive types of fault are considered in the literature such as stopping \cite{Lynch:1996:DA:525656}, \cite{Agmon:2004:FGA:982792.982951}, non- colluding \cite{5779706}, Malicious \cite{5779706}, \cite{5605238}.

Dolev \textit{et al} \cite{Dolev:1986:RAA:5925.5931} presented the notion of Approximate Byzantine Consensus for averaging-based consensus algorithms. The nature of such algorithms \cite{1205192}, \cite{4118472} imposes such an approximation, since it is not guaranteed that state values of nodes become exactly equal after a certain time. In \cite{Dolev:1986:RAA:5925.5931}, a family of algorithms called Mean-Subsequence (Select)-Reduced (MSR) is proposed for fault-tolerance. Later these algorithms were applied to partially connected networks in \cite{262588}, \cite{Azad}, \cite{Azad2}. MSR algorithms are still considered as the main solution for approximate Byzantine consensus in faulty networks. Recently, Vaidya \textit{et al} \cite{Vaidya:2012:IAB:2332432.2332505} after stating the necessary condition which needs to be satisfied by the underlying graph so that an iterative algorithm can achieve approximate consensus, they proved the correctness of an MSR algorithm in such a graph. Furthermore, an alternate proof for the correctness of their MSR algorithm using matrix representation was provided in \cite{2012arXiv1203.1888V}. In \cite{LeBlanc:2011:CNM:1967701.1967742} and \cite{6481629}, the authors considered a more restrictive type of fault and proved the necessary and sufficient conditions for achieving consensus. Also, in \cite{6481629} the authors proposed a variation of the MSR algorithm for Byzantine fault and proved its success using the notion of robustness in graphs which we adopt in this thesis. 

The problem of approximate Byzantine consensus is well considered in both synchronous and asynchronous networks. Consensus in asynchronous networks is a more realistic case facing practical problems, since agents (nodes) do not update their state at the same time in real environments. Moreover, delay over communication paths (graph edges) is inherited in many systems. The problem of approximate Byzantine consensus in \textit{asynchronous} networks is considered in \cite{Dolev:1986:RAA:5925.5931}, \cite{Azad2}, \cite{Vaidya:2012:IAB:2332432.2332505}. Dolev \textit{et al} \cite{Dolev:1986:RAA:5925.5931}, proposed an MSR algorithm for asynchronous networks with complete underlying graph topology. The problem in partially connected networks is assessed in \cite{Azad2} where topological necessary and sufficient conditions for approximate Byzantine Consensus are presented. These conditions are presented in \cite{Vaidya:2012:IAB:2332432.2332505} as well. In all of the mentioned works, the restriction on the topology of underlying graph of networks is the same. Comparing to synchronous networks, it is shown that the number of non-faulty nodes and communication paths between them should be more in asynchronous networks so that approximate Byzantine consensus can be achieved. 

Most of the mentioned algorithms assume that each node has an initial (and true) knowledge on the maximum number of faulty nodes ($f_t$) in the network. This is a huge initial undistributed assumption and if $f_t$ is not chosen precisely, probability of failure is extremely high. For example, in an MSR algorithm as much as $f_t$ is considered greater probability of consensus in an arbitrary graph is less. On the other hand, if we consider a small $f_t$ then it is more probable that number of Byzantine nodes pass from $f_t$. Since elimination of up to $2f_t$ of received values to each node is key to the performance of these algorithms, it is very common that nodes of a network can not reach consensus in absence of any faulty node because a node may disregard all of the received state values. For different examples, please refer to \cite{6481629} and \cite{LeBlanc:2012:LCR:2185632.2185637}.

In this thesis, we first clarify the notion of Byzantine fault. A more restrictive but common type of fault known as Malicious fault is also introduced. Furthermore, we explain the notion of approximate Byzantine consensus and describe why its presence is necessary. The concept of robustness in graphs is discussed and utilized in developing our contributions. Then, we introduce a novel MSR algorithm and we show many advantages of this algorithm compared to other MSR algorithms that appeared in the literature. Convergence analysis of the proposed MSR algorithm is carried out to justify its success in synchronous and asynchronous networks. Moreover, the case of networks with delay on communication paths (underlying graph edges) is considered and the success of the proposed algorithm is proved. Convergence rate and time analysis of the MSR algorithm is done and a higher bound for convergence time is derived. Finally, a new family of algorithms is introduced and their success in networks with complete underlying graph topology is proved. These algorithms do not employ a priori knowledge on maximum number of faulty nodes. In each chapter, numerical analysis is included, not only for clarifying the problem that we are dealing with, but also, for evaluating our findings.


\section{Contributions of the Thesis}

The contributions of this thesis are as follows:

\begin{itemize}
\item The notion of robustness which first appeared in \cite{6481629} is formulated for ease of use. Moreover, the necessity for existence of approximate Byzantine consensus is clarified.
\item A novel MSR algorithm that requires more relaxed topological condition for its success compared to other algorithms in the literature is introduced. It is shown that synchronicity of networks and presence of delay on communication paths do not affect this condition which is in contrary to the results that appeared previously. Moreover, it is justified that the algorithm succeeds in time-varying networks.
\item Convergence rate and time analysis of the proposed MSR algorithm is carried out. Although convergence rate and time analysis is studied extensively for consensus algorithms, the problem is not considered in detail for fault-tolerant algorithms. We determine upper bounds for the convergence rate of the algorithm. Then, we show that some properties of linear consensus algorithm in non-faulty networks is valid in faulty network that adopt our proposed MSR algorithm. Using these properties and matrix representation we derive more optimized bounds for the convergence rate and time.
\item The above results are also extended to the case of time-varying networks. Furthermore, the existence of a common Lyapunov function for time-varying networks is shown.
\item A new family of algorithms which do not use a priori knowledge on maximum number of faulty nodes is proposed. Two algorithms are introduced for Malicious and Byzantine failures in complete networks and their proof of success along with their numerical analysis are presented. 
\end{itemize}

\section{Organization of the Thesis}

The thesis is organized as follows. In Chapter 2, the notions of Byzantine fault, approximate Byzantine consensus and robustness are defined. Moreover, a well-known averaging-based consensus protocol named Linear Consensus Algorithm is represented. In Chapter 3, our proposed MSR algorithm is presented and its convergence analysis is carried out. In Chapter 4, convergence rate and time of the proposed MSR algorithm is derived and the existence of common Lyapunov function for time-varying networks is assessed. In Chapter 5, a new family of algorithms called \textit{Shrinking Convex Hull} algorithms is proposed. Finally, some concluding remarks are provided in Chapter 6. 


\chapter{APPROXIMATE BYZANTINE CONSENSUS: DEFINITIONS AND MATHEMATICAL PRELIMINARIES}

In this chapter, the notions of Byzantine node, approximate Byzantine consensus and robustness are explained. Furthermore, the Linear consensus protocol is represented and it is shown that it can not resist against adversarial behavior of faulty nodes. Two fault-tolerant algorithms from literature are presented and their necessary and sufficient topological conditions required for success is discussed and evaluated. 

Consider a network of nodes which can be represented with a graph $G=(V,E)$ where $V$ is the set of nodes and $E$ is the set of edges. Suppose each node $i$ communicates with its neighbors by sending its state value $x_i(t)$ and receiving the state value of its neighbor node $j$, $x_{ij}(t)$. The objective of exact consensus is that all nodes reach agreement on a common value for all $t \geq t_0 \geq 0$ i.e. $x_i(t)=x_j(t)$ for all $i$, $j \in V$. In many applications, approximate consensus rather than exact consensus is the objective. Therefore, the goal is developing distributed algorithms so that as $t \rightarrow \infty$, state values of nodes converge asymptotically to a common value i.e. $|x_i(t)-x_j(t)| \leq \epsilon$ where $\epsilon >0$ is pre-assigned value. In the following, we represent a well-known algorithm for reaching approximate consensus and discuss its performance facing faulty nodes.

\section{Linear Consensus Algorithm}

Among diverse approaches to achieve consensus in a network, an averaging-based algorithm which is known as Linear Consensus algorithm has attracted considerable interest due to its applicability in a variety of contexts. In this algorithm, each node receives information from its neighbors at time $t$ and changes its value according to
\begin{equation}
x_i(t+1)= \sum_{j \in N_i(t)} \omega_{ij}(t)x_{ij}(t)
\end{equation}
where $\omega_{ij}(t)$ is the weight assigned to node $j$'s value by node $i$ at time-step $t$. For the algorithm, the following conditions on $\omega_{ij}(t)$ are assumed to hold.
\begin{itemize}
\item $\omega_{ij}(t)=0$ whenever $j \notin N_i(t)$;
\item  $0< \alpha \leq \omega_{ij}(t) \leq 1$, $\forall j \in N_i(t)$;
\item $\sum_{j=1}^n \omega_{ij}[t]=1$, $\forall i \in V$, $\forall j \in N_i(t)$;
\end{itemize}
where $N_i(t)$ is the set of node $i$'s neighbors at time $t$.

\begin{theorem} \cite{4140748}
In a time-invariant network in which the nodes update their state values using the linear consensus algorithm, approximate consensus is guaranteed if and only if the underlying graph of the network has a rooted out-branching.  
\end{theorem}

A rooted out-branching is a directed path that connects all the nodes. The above theorem presents the necessary and sufficient condition required for the success of the linear consensus algorithm in time-invariant networks. The sufficient condition for success of the algorithm in time-varying networks is explained in the following theorem.

\begin{theorem} \cite{1205192}, \cite{1393134}, \cite{1431045}
In a time-varying network, in which the nodes update their state values using the linear consensus algorithm, approximate consensus is guaranteed if there exist infinite bounded sequences that the union of graphs in each sequence has a rooted out branching.
\end{theorem}
%Given these conditions, a necessary and sufficient condition for reaching approximate consensus in time-invariant networks is that the graph should have a rooted out-branching \cite{4140748}. In the case of time-varying networks under the conditions mentioned above, the sufficient condition for reaching consensus is that there exist infinite bounded sequences that the union of graphs in each sequence has a rooted out branching. This problem is examined in \cite{1205192}, \cite{1393134}, \cite{1431045}.

By the following example, we assess the resilience of the algorithm facing Byzantine fault. 

\begin{example} \normalfont
 Consider a network with 4 nodes. Let the underlying graph of the network be complete. We assume that Node 2 is Byzantine and at each iteration sends arbitrary state values to its neighbor nodes. Figure 2.2 illustrates the simulation results of this network. The state values of Nodes 1, 3 and 4 are depicted with respect to time and it can be inferred that these values are not converging to a common value. 

\begin{figure}
\begin{center}
\includegraphics[scale=0.3]{avsim.jpg}
\caption{ Simulation result of a network which contains a Byzantine node and uses linear consensus algorithm \label{fig1}}
\end{center}
\end{figure}
\end{example}

As Example 1 suggests, this well-known algorithm is not capable of resisting against adversarial behavior of Byzantine nodes. Therefore, a Byzantine node can easily prevent the network to reach agreement. This major problem necessitates adoption of averaging-based fault-tolerant algorithms. Hence, the objective is to design a distributed algorithm so the network achieves approximate Byzantine consensus in presence of Byzantine nodes. 

 \section{Byzantine Fault} 
 
 A Byzantine fault models any unbounded behavior of faulty nodes such as, sending different values to different neighbor nodes or taking any arbitrary function instead of averaging \cite{Lynch:1996:DA:525656}. In the literature, various types of fault are introduced that are more restrictive than the Byzantine fault. However, the definition of Byzantine node encompasses all of these types. In this thesis, we define a Byzantine node as a faulty node that can not perform its task precisely.
 
\begin{definition}[Byzantine node] A node is called Byzantine if it can not follow the exact steps of the pre-assigned algorithm that all non-faulty nodes of a network are using.
 \end{definition}
Due to this definition, a node is faulty if and only if it is Byzantine.

  \section{Exact and Approximate Byzantine Consensus}
  
  In this section, we define the Exact and Approximate Byzantine Consensus concepts.

\begin{definition}[Exact Byzantine Consensus] \cite{Lynch:1996:DA:525656}: A network is said to reach Exact Byzantine Consensus if each one of its nodes starts from an arbitrary value and all of its non-faulty nodes reach consensus with the following conditions:
\begin{itemize}
\item \textbf{Agreement:} No two non-faulty nodes decide on different values.
\item \textbf{Validity:} If all non-faulty nodes start with the same initial value $x_0$, then $x_0$ is the only possible decision value for a non-faulty node.
\end{itemize}
\end{definition}

Distributed consensus using averaging protocols has received considerable attention recently. For a review on related literature please refer to \cite{4118472}. The averaging nature of these algorithms necessitates presence of approximate Byzantine consensus in which approximate rather than exact agreement is the desired goal for non-faulty nodes. In networks whose nodes use averaging protocols to reach consensus, it is not guaranteed that all nodes reach consensus on \textit{exactly} the same value after a certain time.

 \begin{definition}[Approximate Byzantine Consensus] \cite{Dolev:1986:RAA:5925.5931}: A network is said to reach Approximate Byzantine Consensus if its nodes start from an arbitrary value $x_i(0)$ and all of its non-faulty nodes reach consensus with the following two conditions:
\begin{itemize}
\item \textbf{Agreement:} For any pre-assigned $\epsilon>0$, all non-faulty nodes eventually decide on output values that are within $\epsilon$ of each other.
\item \textbf{Validity:} The output value of each non-faulty node must be in the range of initial values of the non-faulty nodes.
\end{itemize}
\end{definition}

Next, an example is presented to show that exact consensus is not guaranteed in networks whose nodes adopt averaging-based algorithms to achieve consensus.

\begin{example} \normalfont
Consider the network depicted in Figure 1. In each iteration, Node 1 sends its state value to Nodes 2 and 3 which update their state values by taking the average of the received values and their own state values. Assume that the initial state value of Node 1 is $2$ and the initial state values of Nodes 2 and 3 are $1$. It can be inferred that there exists no time that state values of all nodes become exactly equal. However, the state values of Nodes 2 and 3 converge asymptotically to the state value of Node 1.

\begin{figure}
\begin{center}
\includegraphics[scale=0.5]{Dr1.jpg}
\caption{ A network with three nodes where state values of Nodes 2 and 3 converge asymptotically to state value of Node 1. \label{fig1}}
\end{center}
\end{figure}

\end{example}

\section{Notations and Graph Terminology}

Throughout the thesis, the underlying directed graph of the network is denoted by $G=(V,E)$ where $V$ is the set of vertices and $E$ is the set of edges. The iteration instants of node $i$ is represented by the set $\{t_0^i, t_1^i, t_2^i, ..., t_r^i\}$ where $i \in V$ and $r$, a non-negative integer, is the number of the iteration. The amount of communication delay between node $i$ and its neighbor node $j$ is denoted with $\tau_{ij}$. $x_i(t)$ is the state value of node $i$ at time $t$.  Moreover, $x_{ij}(t)$ is the state value of node $j$ received by node $i$ and $N_i(t)$ is the set of neighbors of node $i$ at time $t$. $F$ is the set of faulty nodes and $|F|=f_t$. Hence, $V\setminus F$ comprises the set of non-faulty nodes. Let $M(t)$ be the maximum state value of the set of non-faulty nodes and $m(t)$ the minimum of them at time $t$. The maximum synchronization error in the network is defined as:
 \begin{equation}
 e(t)=M(t)-m(t)
 \end{equation}
Note that, $e(t) \geq 0$ for all $t \geq 0$. Furthermore, $e(t)=0$ if and only if $M(t)=m(t)$.
 
Hence, a network is said to reach approximate Byzantine consensus if the following conditions are satisfied.
\begin{itemize}
\item \textbf{Agreement:} There exists a $t_0 \geq0$ such that for all $t \geq t_0$, $e(t)\leq \epsilon$
\item \textbf{Validity:} For all $t \geq 0$, $m(0) \leq m(t) \leq M(t) \leq M(0)$. 
 \end{itemize}
 

\section{Robustness of Graphs}

In this part, the robustness of the underlying graph of consensus networks is discussed. 

%Our methodology is inspired by \cite{6481629}, in which, the authors proposed the necessary and sufficient conditions on graph topology that an MSR algorithm succeeds under $f_t$ number of faulty nodes in synchronous networks. However, our proof methods are different here. 

\begin{definition}[Reachability] Given a digraph $G=(V,E)$ and a nonempty subset $S$ of nodes ($S \subset V$) of $G$, we say that $S$ is an r-reachable subgraph if there exists an $i \in S$ such that $|N_i \setminus S| \geq r$, where $r \in \mathbb{N}$.
\end{definition}

Let $A$ be the adjacency matrix of the digraph $G$ and $A_S$ be a matrix with the same dimensions as $A$ which contains the adjacency matrix of $S$ with the condition that if $i$ or $j \notin S$ then $a_{S_{ij}} =0$, where $a_{S_{ij}}$ is an element of $A_S$ at row $i$ and column $j$. We refer to this matrix as adjacency matrix of $S$ in $G$ environment. With this definition, the reachability of the subgraph $S$ can be determined as:
\begin{equation}
i_{re}(G,S)= \max_{i \in S} \bigg( \sum_{j=1}^n(a_{ij}-a_{S_{ij}})\bigg)
\end{equation} 
 
\begin{definition}[Robustness] A digraph $G=(V,E)$ ($n \geq 2$) is $r$-robust with $r \in \mathbb{N}$, if for every pair of nonempty and disjoint subsets of $V$, at least one of the subsets is $r$-reachable.
\end{definition}

Similar to the previous approach, if $S$ and $U$ are two subgraphs of $G$ and $A_{S}$ and $A_{U}$ are their adjacency matrices in $G$ environment respectively, then the robustness of graph $G$ can be calculated as below:
\begin{equation}
i_{ro}(G)=\min_{S,U \subset V}\Bigg(\max_{i \in S \cup U}\bigg(\sum_{j=1}^n(a_{ij}-a_{S_{ij}}-a_{U_{ij}})\bigg)\Bigg)
\end{equation} 
 
The notion of robustness is useful in understanding how total information generated by nodes is accessible for an individual node. The more a node is connected with subgraphs of the underlying graph of its network, the more reliable it can make decisions and as result, the total network behavior is more robust facing failures.

In the following, we present an example regarding the notion of robustness.
\begin{example}\normalfont
Consider the graph depicted in Figure 2.2. The adjacency matrix of the graph $A$ is as below.
\begin{center}

$A= \begin{bmatrix}
1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1
\end{bmatrix}$
\end{center}
Consider a subgraph of the depicted graph which is consisted of Nodes 1 and 2. Since each node in this subgraph has at most one neighbor out of the subgraph, the reachability of the subgraph is $1$. Therefore, we say the subgraph is $1$-reachable.The fact can be verified using (2.2). Moreover, from (2.3), the depicted graph is $1$-robust because for every two disjoint subgraphs at least one of them is $1$-reachable.


\begin{figure}
\begin{center}
\includegraphics[scale=0.5]{ex22.jpg}
\caption{ A graph with four nodes. \label{fig1}}
\end{center}
\end{figure}
\end{example}

\section{Linear Consensus Algorithm}

Among diverse approaches to achieve consensus in a network, an averaging-based algorithm which is known as Linear Consensus algorithm has attracted considerable interest due to its applicability in a variety of contexts. In this algorithm, each node receives information from its neighbors at time $t$ and changes its value according to
\begin{equation}
x_i(t+1)= \sum_{j \in N_i(t)} \omega_{ij}(t)x_{ij}(t)
\end{equation}
where $\omega_{ij}(t)$ is the weight assigned to node $j$'s value by node $i$ at time-step $t$. For the algorithm, the following conditions on $\omega_{ij}(t)$ are assumed to hold.
\begin{itemize}
\item $\omega_{ij}(t)=0$ whenever $j \notin N_i(t)$;
\item  $0< \alpha \leq \omega_{ij}(t) \leq 1$, $\forall j \in N_i(t)$;
\item $\sum_{j=1}^n \omega_{ij}[t]=1$, $\forall i \in V$, $\forall j \in N_i(t)$;
\end{itemize}
where $N_i(t)$ is the set of node $i$'s neighbors at time $t$.

Given these conditions, a necessary and sufficient condition for reaching approximate consensus in time-invariant networks is that the graph should have a rooted out-branching \cite{4140748}. In the case of time-varying networks under the conditions mentioned above, the sufficient condition for reaching consensus is that there exist infinite bounded sequences that the union of graphs in each sequence has a rooted out branching. This problem is examined in \cite{1205192}, \cite{1393134}, \cite{1431045}.

By the following example, we assess the resilience of the algorithm facing Byzantine fault. 

\textit{Example 2}: Consider a network with 4 nodes. Let the underlying graph of the network be complete. We assume that Node 2 is Byzantine and at each iteration sends arbitrary state values to its neighbor nodes. Figure 2.2 illustrates the simulation results of this network. The state values of Nodes 1, 3 and 4 are depicted with respect to time and it can be inferred that these values are not converging to a common value. 

\begin{figure}
\begin{center}
\includegraphics[scale=0.3]{avsim.jpg}
\caption{ Simulation result of a network which contains a Byzantine node and uses linear consensus algorithm \label{fig1}}
\end{center}
\end{figure}

As Example 2 suggests, this well-known algorithm is not capable of resisting against adversarial behavior of Byzantine nodes. Therefore, a Byzantine node can easily prevent the network to reach agreement. This major problem necessitates adoption of averaging-based fault-tolerant algorithms. Hence, the objective is to design a distributed algorithm so the network achieves approximate Byzantine consensus in presence of Byzantine nodes. 

\section{Summary of the Chapter}

In this chapter, we have first clarified the notion of Byzantine fault. Then, the approximate Byzantine consensus has been defined and it has been shown that use of approximate agreement is essential since exact agreement is not guaranteed in networks which adopt averaging-based algorithms.

After presenting our graph terminology and formulating the type of fault that we use, we have represented and formulated the notions of reachability and robustness. Finally, a well-known averaging-based algorithm is presented and it has been discussed that this algorithm can not resist against adverse behaviors of Byzantine nodes. 

In the next chapter, we propose a novel fault-tolerant algorithm and prove its success in asynchronous and synchronous networks. 

\chapter{THE PROPOSED MSR ALGORITHM}

In this chapter, we present our MSR algorithm and derive the necessary and sufficient conditions for its success using the notion of robustness. Some numerical examples are included to evaluate the performance of the algorithm.

 \section{The MSR Algorithm}
 
 In this part, a novel fault-tolerant MSR algorithm is proposed. This algorithm injects the capability of resisting against adversarial behavior of Byzantine nodes to non-faulty nodes in asynchronous and synchronous networks with or without time delay on communication paths. 
 
 \textbf{MSR Fault-Tolerant Algorithm:}
\begin{enumerate}
\item[(S1)] Each non-faulty node $i$ sends its state value $x_i(t_r^i)$ at $t_r^i$.
\item[(S2)] Each non-faulty node $i$ saves the values that it has received in time interval $\Delta t_r^i$. If it has received more than one state value from a node, it considers the most recent value that it has received. If it has not received any value from its neighbor node in its update time interval $\Delta t_r^i$, it uses the old received values. Then, it sorts the received values in the increasing order.
\item[(S3)] Node $i$ eliminates $f_a$ number of maximum values in the sorted list that are greater than its current state value. If the number of greater values is less than $f_a$, it eliminates all of them. Similarly, it deletes the $f_a$ number of minimum values in the list that are less than its state value. Let $E_i(t)$ be the set of nodes with deleted state values
\item[(S4)] Node $i$ updates its state value as follows.
\begin{equation}
x_i(t_{r+1}^i)= \sum_{j \in N_i(t_{r}^i)\setminus E_i(t_{r}^i)} \omega_{ij}(t_{r}^i)x_{ij}(t_{r}^i)
\end{equation}
\end{enumerate}
Each node uses its state value in the update, i.e. $x_i(t_{r}^i) \in N_i(t_{r}^i)$.

The averaging coefficients $\omega_{ij}(t_{r}^i)$ are supposed to satisfy the following conditions:
\begin{itemize}
\item $\omega_{ij}(t_{r}^i)=0$ whenever $j \notin N_i(t_{r}^i)\setminus E_i(t_{r}^i)$;
\item  $0<\alpha \leq \omega_{ij}(t_{r}^i)\leq 1$, $\forall j \in N_i(t_{r}^i)\setminus E_i(t_{r}^i)$;
\item $\sum_{j=1}^n \omega_{ij}(t_{r}^i)=1$, $\forall i \in V$, $\forall j \in N_i(t_{r}^i)\setminus E_i(t_{r}^i)$;
\end{itemize}

Note that, the above algorithm with $f_a=0$ reduces to the Linear Consensus algorithm which is proposed in Chapter 2 and widely discussed in the literature (see e.g. \cite{1205192}, \cite{4118472}, \cite{1393134} and the references there). 

The proposed algorithm is an MSR algorithm due to the the following reasons:
\begin{itemize}
\item[($i$)] It eliminates at most $2f_a$ number of received state values at (S3). Therefore, it \textit{reduces} the cardinality of $N_i(t)$. 
\item[($ii$)] It \textit{selects} the state values that are in $N_i(t)\setminus E_i(t)$ at (S4). 
\item[($iii$)] It takes the weighted \textit{mean} of the selected values at (S4).
\end{itemize}


Our proposed MSR algorithm has several differences with the other fault-tolerant algorithms in the literature. The above algorithm does not necessarily delete $2f_a$ number of received state values at each iteration. Each non-faulty node does not wait to receive a certain number of state values to update its state. Messages are not tagged by time. Furthermore, taking weighted rather than just arithmetic mean is possible for non-faulty nodes and they can change the weights in each iteration respect to (4).


\section{Proof of Success}

 Considering the definition of Byzantine fault that has appeared in Section 2 and the MSR algorithm, the overall network dynamics can be represented as a non-autonomous nonlinear system because (i) control over the behavior of a Byzantine node is not possible (it may behave non-linearly), (ii) it is not guaranteed that in any iteration a non-faulty node eliminates the received state values of its Byzantine neighbor(s) using MSR algorithm and (iii) the nature of the MSR algorithm and asynchronous behavior of the system, makes it a time dependent system. 
 
 Let us define the network of non-faulty nodes as a subgraph which contains all of the non-faulty nodes. In the following, we show that if the number of Byzantine nodes ($f_t$) is less than or equal to $f_a$, the state values of non-faulty nodes will stay bounded for all $t \geq 0$ within bounds $M(0)$ and $m(0)$. Moreover, we prove that if the network of non-faulty nodes is $(f_a+1)$-robust then reaching approximate Byzantine consensus is guaranteed.

 In an asynchronous Byzantine network, each non-faulty node might update its state at arbitrary times. However, the interval between the update instants is bounded. Let
\begin{equation}
\Delta t_r^i=t_{r+1}^i-t_r^i
\end{equation}
denote the time interval between two successive updates in the state of node $i$ at round $r$. Since this time interval is bounded for all of the non-faulty nodes, we can claim there exists an $\alpha_t \in \mathbb{R}$ such that $ \Delta t_r^i \leq \alpha_t$, for all $i \in V \setminus F$ and non-negative integers $r$. Moreover, because of inherent discrete dynamics of consensus networks, there exists a $\beta_t \in \mathbb{R}$ such that $ \Delta t_r^i \geq \beta_t$. Communication delay between non-faulty nodes is assumed to be bounded. As result, there exists an $\alpha_{\tau} \in \mathbb{R}$ such that $0 \leq \tau_{ij} \leq \alpha_\tau$, for all $i$, $j \in V \setminus F$. In this way, we define $\Delta t_{m} = \beta_t$ which is the minimum update time interval in the network. In addition, $\Delta t_{M} = \alpha_t + \alpha_\tau$ is defined as the sum of maximum update time interval and maximum communication delay between non-faulty nodes. $\{ 0, t_{M_1}, t_{M_2}, ...\}$ is defined as the set of time sequences with $t_{M_{r+1}}=t_{M_r}+\Delta t_{M}$. Consequently, it can be inferred that a non-faulty node in $\Delta t_{M}$ interval is guaranteed to receive at least one state value from each of its non-faulty neighbors. Similar to $t_{M_r}$ we define, $t_{m_{r+1}}=t_{m_r}+\Delta t_{m}$. 

In \cite{Dolev:1986:RAA:5925.5931}, \cite{Azad2}, \cite{Vaidya:2012:IAB:2332432.2332505} it is assumed that non-faulty nodes can not consider a bound in which they are guaranteed to receive all values of their non-faulty neighbors. However, as discussed above, it is reasonable to assume that there exist bounded sequences of time that each node is guaranteed to receive at least one value from each of its non-faulty neighbors. But they have no knowledge about this bound ($\Delta t_{M}$). We use this bound and its related sequences to analyze the convergence of the algorithm.

\newtheorem{lemma}{Lemma}[chapter]
%\newtheorem*{proof}{Proof}

\begin{lemma}
In an asynchronous network with bounded delay on communication links and $f_t$ number of Byzantine nodes, in which, nodes update their state values using the MSR algorithm with parameter $f_a$, it is guaranteed that $M(t_{m_{r+1}})\leq M(t_{m_{r}})$ and $m(t_{m_{r+1}})\geq m(t_{m_{r}})$, for all non-negative integer $r$, if and only if $f_a \geq f_t$.
\end{lemma}
\begin{proof}
\textit{(Sufficiency)} Suppose the MSR algorithm is applied to the system with $f_a \geq f_t$. Note that, at any time $t_{m_r}$, there is no non-faulty node $i$ that accepts any value greater than $M(t_{m_r})$ or less than $m(t_{m_r})$ because $f_a \geq f_t$. By utilizing (3) with its conditions on the weights, we have $m(t_{m_r}) \leq x_i(t_{m_{r+1}}) \leq M(t_{m_r})$ for each non-faulty node $i$. As result, $M(t_{m_{r+1}})\leq M(t_{m_{r}})$ and $m(t_{m_{r+1}})\geq m(t_{m_{r}})$.

\textit{(Necessity)} Suppose $f_a < f_t$. Consider a network with $f_t$ number of Byzantine nodes that send values strictly greater than $M(t_{m_{r}})$ to non-faulty node $i^\star$ at time $t_{m_r}$. Node $i^\star$ has state value $x_{i^\star}(t_{m_{r}})=M(t_{m_{r}})$ and no non-faulty node as neighbor. Also, suppose that node $i^\star$ updates its state value at time $t_{m_{r+1}}$ using the MSR algorithm with parameter $f_a$. From (3), we have: \\
%\begin{center}
\begin{gather*}
x_{i^\star}(t_{m_{r+1}})= \sum_{j \in N_i(t_{m_{r+1}})\setminus E_i(t_{m_{r+1}})} \omega_{ij}(t_{m_{r+1}})x_{ij}(t_{m_{r+1}})
\\ = \omega_{ii}(t_{m_{r+1}})x_{i}(t_{m_{r+1}}) 
\\ +
\sum_{{j \in N_i(t_{m_{r+1}})\setminus E_i(t_{m_{r+1}})}, {j \neq i}} \omega_{ij}(t_{m_{r+1}})x_{ij}(t_{m_{r+1}}) >M(t_{m_{r}})
\end{gather*}
%\end{center}
Therefore, $M(t_{m_{r+1}})>M(t_{m_{r}})$ which leads to a contradiction. A similar approach can be adopted for $m(t_{m_{r}})$. 
\end{proof}
 
\newtheorem{corollary}{Corollary}[chapter] 
 
\begin{corollary}
In an asynchronous network with bounded delay on communication links and $f_t$ number of Byzantine nodes in which nodes use the MSR algorithm to update their state values with parameter $f_a$ ($f_a \geq f_t$), we have $m(0) \leq x_i(t) \leq M(0)$, for all $ t \geq 0 $ and for all $ i \in V \setminus F$.
\end{corollary}

Lemma 1 implies that using the MSR algorithm with parameter $f_a$, the maximum synchronization error $e(t)$ stays bounded in any graph topology for all $t \geq 0$ if and only if the number of Byzantine nodes ($f_t$) is less than or equal to $f_a$. Corollary 1 indicates that state values of non-faulty nodes will remain within bounds $m(0)$ and $M(0)$ if the stated condition in Lemma 1 holds. 
 
\newtheorem{theorem}{Theorem}[chapter]  
 
 
\begin{theorem}
In an asynchronous network with bounded delay on communication links and maximum $f_t$ number of Byzantine nodes, approximate Byzantine consensus is guaranteed using the MSR algorithm with parameter $f_a$ ( $f_a \geq f_t$), if and only if the network of non-faulty nodes is at least $(f_a+1)$-robust.
\end{theorem}
 
 \begin{proof}
 \textit{(Sufficiency)}  From Corollary 1, it is known that any state value of non-faulty nodes is bounded by $M(0)$ and $m(0)$. Furthermore, from Lemma 1, $e(t)$ is a non-increasing function, upper bounded by $e(0)=M(0)-m(0)$ and lower bounded by $0$. Hence, $lim_{t \rightarrow \infty} e(t)= \epsilon$, $\epsilon \in \mathbb{R}$ \cite{Ponnusamy:1498659}. Now, we show by contradiction that if network of non-faulty nodes topology is at least $(f_a+1)$-robust then $\epsilon =0$ and asymptotic Byzantine consensus is guaranteed.

 Assume that $\epsilon >0$. In this way, there exists a non-negative integer $r^{'}$ that for all $r \geq r^{'}$, $M(t_{M_r})\geq L_M$ and $m(t_{M_r}) \leq L_m$, where $L_M,L_m \in \mathbb{R}$, $L_M>L_m$ and $(L_M-L_m) \geq \epsilon$. Suppose the networks of non-faulty nodes with values greater than or equal to $L_M$ and less or equal to $L_m$ are denoted by $ \kappa_M$ and $\kappa_m$, respectively. From (3), the required conditions for nodes of $\kappa_M$ to be able to keep their values greater or equal to $L_M$ for all time sequences $t_{M_r}$, $r \in \{r^{'}, r^{'}+1, r^{'}+2, ... \}$, are that $\kappa_M$ should be connected and there exists no $i \in \kappa_M$ that $| N_i(t_{M_r})\setminus \kappa_M| \leq f_a$. So, by definition of MSR algorithm with value $f_a$, none of the nodes in $\kappa_M$ can accept values from the nodes which are not member of $\kappa_M$. Similarly, this condition should be held for all nodes in $\kappa_m$ so that $L_M > L_m$ for all $t_{M_r}$. It emphasizes that at most $\kappa_M$ and $\kappa_m$ can be $f_a$-reachable. On the other hand, since the overall structure of the network of non-faulty nodes is $(f_a+1)$-robust, due to the definition of robustness, $f_a$-reachability of $\kappa_M$ and $\kappa_m$ at the same time is not possible. So, the condition on the bounds ($L_M > L_m$) is not valid and $L_M=L_m$.

\textit{(Necessity)} Suppose the structure of the network of non-faulty nodes is not at least $(f_a+1)$-robust. From the definition of robustness, there exist two disjoint subsets $S_1$ and $S_2$ with reachability less than or equal to $f_a$. Now, suppose that nodes of $S_1$ and $S_2$ have initial state values $a$ and $b$ respectively. Also, assume the Byzantine nodes do not send any value to their neighbors. Due to the definition of the MSR algorithm with parameter $f_a$, under these assumptions the asymptotic Byzantine consensus is impossible since nodes of $S_1$ and $S_2$ eliminate all the received values.
\end{proof}
 
 Theorem 1 states that the proposed MSR algorithm achieves approximate Byzantine consensus in asynchronous networks with delay on communication paths if and only if the network of non-faulty nodes is at least $(f_a+1)$-robust with $f_a \geq f_t$. This condition is the same condition that is presented in \cite{Azad2}, \cite{6481629}, \cite{Dolev:1986:RAA:5925.5931}, \cite{Vaidya:2012:IAB:2332432.2332505} for synchronous systems without time delay. Indeed, the main difference between the previous fault-tolerant algorithms and the proposed algorithm in this thesis is that \textit{the synchronicity of the network and presence of delay on communication paths do not affect the topological condition required for the success of the algorithm}. 
 %In other words, Theorem 1 indicates that the proposed MSR algorithms is capable of execution in asynchronous networks with the same topological condition as synchronous networks if they are well regulated.
 
 In the following, we show that the algorithm can also be applied to synchronous networks while the topological required condition for the success of the algorithm remains unchanged.
 
 \begin{theorem}
In a synchronous network with bounded delay on communication links and $f_t$ number of Byzantine nodes, approximate Byzantine consensus is guaranteed using the MSR algorithm with parameter $f_a$ ($f_a \geq f_t$) if and only if the network of non-faulty nodes is at least $(f_a+1)$-robust.
\end{theorem}

\begin{proof}
The proof is similar to the proof of Theorem 1 with $t_r^i=t_r^j$, for all $i, j \in V \setminus F$ and $r \in \mathbb{N}$. 
\end{proof}
 
It is worthy to mention that the required topological condition for success of the algorithm is the same in the absence of delay in networks. In \cite{Vaidya:2012:IAB:2332432.2332505}, \cite{6481629}, the authors obtained the same result for case of synchronous networks without delay on communication paths. This fact can be inferred from Theorem 1 and 2 by taking $\alpha_\tau = 0$. 
 
%\subsection{Approximate Byzantine Consensus for Time-Varying Networks}
\section{Extension to Time-Varying Networks}

The results can be extended to the case where the underlying graph of the network is time-varying. It is well known that the problem of consensus for networks with switching topology is not as straightforward as fixed topology. This problem is examined in \cite{1205192}, \cite{1393134}, \cite{1431045}. The necessary and sufficient condition for reaching consensus in this case is that there exist infinite bounded sequences that the union of graphs in each sequence has a rooted out branching. 

By adopting this fact, we present necessary and sufficient conditions for reaching approximate Byzantine consensus in time varying faulty networks.

\begin{theorem}
In an asynchronous network with bounded delay on communication links and $f_t$ number of Byzantine nodes, in which, the underlying graph topology is time-varying, if $\{t_l\}$ with $l=1, 2 , ...$ is the set of time instances that the topology of the network of non-faulty nodes is at least $(f_a+1)$-robust with bounded $\Delta t_l$ and $\{t_r^i \}$ is the set of update time steps of node $i$, approximate Byzantine consensus is guaranteed using the proposed MSR algorithm with parameter $f_a$ ($f_a \geq f_t$) if $|\{t_l\} \cap \{t_r^i\}| \rightarrow \infty$ as $t \rightarrow \infty$, for all $i \in V \setminus F$.
\end{theorem}

\begin{proof}
Assume each sequence of the set $\big\{ \{t_l\} \cap \{t_r^i\}\big\}$ is bounded by $\alpha_l$. We take $\Delta t_{M} = \alpha_t + \alpha_\tau+\alpha_l$. The remainder of the proof is the same as the sufficiency part for the proof of Theorem 3.1.
\end{proof}

\section{Numerical Analysis}

In this section, we examine some examples to evaluate the performance of the proposed algorithm. 

%It is shown that under $f_t$ number of Byzantine nodes the algorithm has superior performance with parameter $f_a \geq f_t$ if and only if the network of non-faulty nodes is at least $(f_a+1)$-robust.

 \begin{example} \normalfont
  Consider a complete graph with $4$ nodes in which Node 4 is Byzantine. From the definition of robustness, the non-faulty network is $2$-robust. Suppose that Nodes 1, 2 and 3 update their states every 5, 2 and 3 seconds, respectively. Additionally, we assume that the Byzantine node sends its state value every 4 seconds. The maximum communication delay between any node $i$ and $j$ is 5 seconds. the initial values of non-faulty nodes are $x_N(0)=[1, 3, 5]^T$. The maximum update sequence ($t_{M_r}$) is $\{0, 10, 20, ... \}$. Table 1 shows the progress of the algorithm.
 
\begin{table}[h]
\caption{Progress of the MSR algorithm in a complete network with four nodes.}
\begin{center}
\begin{tabular}{|c||c||c||c|}
\hline $t_{M_r}$ & Received values & Received values  & Received values \\ & by Node 1 & by Node 2 & by Node 3 \\ \hline 0 & - & - & - \\ \hline 10 & $\{3, 3.3, 5^{\star} \}$ & $\{1, 5, 5^{\star} \}$  & $\{1, 2.5, 5^{\star} \}$ \\ \hline 20 & $\{3.43, 2.63, 2^{\star} \}$ & $\{2.76, 2.83, 4^{\star} \}$ & $\{2.76, 2.7, 2^{\star} \}$ \\ \hline 30 & $\{2.73, 2.73, 2^{\star} \}$ & $\{2.71, 2.72, 1^{\star} \}$ & $\{2.71, 2.73, 1^{\star} \}$ \\ \hline 40 & $\{2.72, 2.72, 4^{\star} \}$ & $\{2.72, 2.72, 2^{\star} \}$ & $\{2.72, 2.72, 3^{\star} \}$ \\ \hline
\end{tabular}
\end{center}
\end{table}

In Table 1, the values sent by the Byzantine node are represented with a star index. At each time instant the stored state value of a non-faulty node by different nodes might not be equal. This is due to the asynchronous behavior of the network and the different amount of delay in the communication paths. The simulation result of this network is depicted in Fig. 2 which illustrates the convergence of state values of the non-faulty nodes to a common value.

\end{example}

\begin{example}
\normalfont Consider the partially connected network that is illustrated in Fig. 3 (which is also considered in \cite{6481629}). The network of non-faulty nodes structure is $2$-robust. The delay between the communication links are generated by \textsf{randi(5,n,n)} (we use Matlab notations) where $n$ is the number of the total nodes. The values that are sent to different nodes by the Byzantine node (which is Node 2 in this example) are obtained by \textsf{5*rand}. Moreover, the interval between two successive update in each node is assumed to be irregular and in each iteration is updated as \textsf{randi(10,1,n)}. The result of simulation for this example is illustrated in Fig. 4 which shows that the state value of the non-faulty nodes converges to a common value. 

\begin{center}
\begin{figure}
\includegraphics[scale=0.3]{SimA.jpg} \caption{ The simulation results of a complete network with 3 non-faulty nodes and one Byzantine node.}
\end{figure}
\end{center} 

\begin{figure}
\begin{center}
\includegraphics[scale=0.8]{Fig1.jpg}
\caption{Network with seven normal nodes and one Byzantine node. \label{fig1}}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[scale=0.3]{Net8.jpg}
\caption{Simulation result of the partially connected network of Fig. 3 which shows the convergence of non-faulty nodes to a common value. \label{fig1}}
\end{center}
\end{figure}

\end{example}

\section{Summary of the Chapter and Concluding Remarks}

In this chapter, we have proposed a new MSR algorithm which has many advantages compared to similar algorithms that appeared in the literature. We have proved that this algorithm succeeds if and only of the underlying graph topology of the network is at least ($f_a+1$)-robust.

We prove that synchronicity of networks does not affect the topological condition required for the convergence of the algorithm. Furthermore, the same fact is concluded for networks with delay on communication paths. These results are in contrary to the previous results in the literature \cite{Dolev:1986:RAA:5925.5931}, \cite{Vaidya:2012:IAB:2332432.2332505}. We have extended our results to networks with time-varying underlying graph topology and extracted the required condition for success of the proposed algorithm. Finally, some numerical examples have been presented to evaluate the performance of the algorithm.  

In the next chapter, we analyze the convergence rate and time of the proposed algorithm in time-invariant and varying networks.


\chapter{CONVERGENCE ANALYSIS OF THE PROPOSED MSR ALGORITHM}

In this chapter, analysis over convergence properties of our proposed fault-tolerant algorithm is carried out. We derive two sets of higher bounds for the convergence rate and time of the proposed MSR algorithm. First, bounds for the convergence rate and time of the algorithm are extracted based on the assumption that the overall system is non-linear. Then, it is shown that some properties of non-faulty networks which use linear consensus algorithm (or the proposed MSR algorithm with parameter $f_a=0$) are valid in faulty networks which adopt the proposed MSR algorithm. Using these properties and matrix representation, we calculated more optimized bounds for the convergence rate and time. Later, the results are extended to time-varying networks and the existence of a common Lyapunov function is shown. Throughout the chapter, it is shown that the extracted bounds and other results are applicable to both asynchronous and synchronous networks with or without time delay on communication paths. Furthermore, it is proved that the bounds can be applied to non-faulty networks which adopt linear consensus algorithm.

% We use Lyapunov stability method to derive the rate of convergence. Furthermore, graph based analysis methods are adopted to calculate the time of convergence.

\section{Convergence Rate and Time Analysis}

Due to the non-linear behavior of networks that contain Byzantine node(s) (explained in Section 3.2), we can not apply linear properties of row stochastic matrices. So, the methods that were used in \cite{Olshevsky:2009:CSD:1654147.1654158}, \cite{Landau19815}, \cite{1582620} can not be adopted here. Instead, in this section, we try to derive bounds for convergence rate and time based on the assumption that the overall system dynamics are non-linear.

\begin{theorem}
In an asynchronous network with bounded delay on communication links and maximum $f_t$ number of Byzantine nodes, in which, each non-faulty node updates its state value using the proposed MSR algorithm with parameter $f_a$ ($f_a \geq f_t$)
\begin{equation}
e \Bigg( t+(n-f_a-1)\Delta t_M \Bigg) < e(t)
\end{equation}
if and only if the structure of the network of non-faulty nodes is $(f_a+1)$-robust.
\end{theorem}

\begin{proof}
\textit{(Sufficiency)} Let $S_M(t)$ and $S_m(t)$ denote the set of non-faulty nodes with values $M(t)$ and $m(t)$, respectively. Due to the definition of robustness, either $S_m(t)$ or $S_M(t)$ is at least $(f_a+1)$-reachable. Without loss of generality, suppose $S_m(t)$ is $(f_a+1)$-reachable which implies that
%\begin{equation*}
%|S_M(t)|\geq f_a+1
%\end{equation*}
\begin{equation*}
|S_m(t)| \leq n-(f_a+1).
\end{equation*}
Considering the system properties and (3.1) after $\Delta t_M$, cardinality of $S_m$ would be:
\begin{equation*}
|S_m(t+\Delta t_M)| \leq |S_m(t)|-1
\end{equation*}
\begin{equation*}
\implies |S_m\big(t+(n-f_a-2)\Delta t_M\big)| \leq 1
\end{equation*}
The above equations imply that after $(n-f_a-1)\Delta t_M$, $m(t)$ increases so $e(t)$ decreases which results in (4.1).

\textit{(Necessity)} Suppose the structure of the network of non-faulty nodes is not at least $(f_a+1)$-robust. Regarding the definition of robustness, there exist two disjoint subsets $S_1$ and $S_2$ with reachability less than or equal to $f_a$. Now, assume $S_1$ is $S_m$ and $S_2$ is $S_M$ with initial state values $m$ and $M$ respectively. Also, assume the Byzantine nodes do not send any value to their neighbors. Due to the MSR algorithm with parameter $f_a$, under these assumptions the asymptotic Byzantine consensus is impossible because nodes of $S_m$ and $S_M$ eliminate all of the received values that come from other sets. Consequently, occurrence of (4.1) is not guaranteed. 
\end{proof}

Theorem 4.1 is valid for asynchronous networks without delay on communication links as well as synchronous networks with and without delay. In networks which delay on communication links does not exist, one can take $\alpha_\tau =0$ in the proof. Furthermore, in synchronous networks without delay on communication links, $\Delta t_{r}^i=\Delta t_{M}$ for all $i \in V \setminus F$. Note that, Theorem 4.1 suggests a bound which is $\tau_e=(n-f_a-1)\Delta t_M $ on decrease of the maximum synchronization error.

In Theorem 4.1, we proved that after $\tau_e$, the overall synchronization error decreases. In the next theorem, we find a maximum bound on the amount of this decrease.

\begin{theorem}
In a network with maximum $f_t$ number of faulty nodes and $(f_a+1)$-robust structure ($f_a \geq f_t$), in which, each node updates its state value using the MSR algorithm,
\begin{equation}
e(k)\leq\big(1-\frac{\alpha \epsilon}{e(0)}\big)^k e(0)
\end{equation}
where $\alpha$ is the lower bound on $\omega_{ij}$ coefficients defined in (3.1) and $k=\lfloor \frac{t}{\tau_e} \rfloor $. $y=f(x)=\lfloor x \rfloor$ is the greatest integer function.
\end{theorem}
\begin{proof}
We take $v(e(k))=e(k)$ as the Lyapunov function. Due to the definition of $e$ in (1), $v \geq 0$, for all $k$. Moreover, Theorem 2 implies that $\Delta v= e(k+1)-e(k) < 0$. As result, (6) is stable and $e(t)$ converges to zero as $t$ increases. Without loss of generality, we assume that the rate of convergence is $c$ so:
\begin{equation*}
v\big(e(k+1)\big)-v\big(e(k)\big) \leq -c v\big(e(k)\big)
\end{equation*}
\begin{equation}
e(k+1)-e(k) \leq -c e(k).
\end{equation}
So, the main challenge is finding $c$. 
\begin{equation}
\frac{e(k+1)}{e(k)} \leq 1-c
\end{equation} 
Due to Theorem 4.1, it is guaranteed that after $\tau_e$ amount of time, $M(t)$ decreases or $m(t)$ increases or both. Let us assume just one of them changes its value and it changes just once. Considering (1) and (3):
\begin{equation}
\frac{e(k+1)}{e(k)} \leq \frac{\bigg[M(k)-\sum\limits_{j \in N_i(k)\setminus E_i(k), j\neq i} \omega_{ij}(t_{r}^i) \big( M(k)- x_{ij}(t_{r}^i) \big) \bigg]-m(k)}{M(k)-m(k)}
\end{equation}
where $ k \leq t_{r}^i \leq k+1$ and $i$ is the node with maximum value.
\begin{equation}
\frac{\bigg[M(k)-\sum\limits_{j \in N_i(k)\setminus E_i(k), j\neq i} \omega_{ij}(t_{r}^i) \big( M(k)- x_{ij}(t_{r}^i) \big) \bigg]-m(k)}{M(k)-m(k)} \leq \big(1-\frac{\alpha \epsilon}{e(0)}\big)
\end{equation}
 $\omega_{ij}$ is replaced by $\alpha$, $\epsilon$ is used instead of $M(k)- x_{ij}$ and $e(0)$ is written instead of $e(k)$. As result, $c=\frac{\alpha \epsilon}{e(0)}$, which concludes the proof. 
\end{proof} 

Theorem 4.1 and 4.2 suggest a bound on the convergence rate of the MSR algorithm. Using Theorem 4.2, the time of convergence can be found as below:
\begin{equation*}
\epsilon \leq\big(1-\frac{\alpha \epsilon}{e(0)}\big)^k e(0)
\end{equation*}
\begin{equation}
k \leq \log^{\frac{\epsilon}{e(0)}}_{\big(1-\frac{\alpha \epsilon}{e(0)}\big)}
\end{equation}


\section{ Convergence Rate and Time Analysis Using Matrix Representation}

In this section, we extract better bounds for the convergence rate and time using matrix representation.
% In Section 3.2, we mentioned that the overall system is non-autonomous non-linear system. However, in this section, we show that some properties of non-faulty consensus networks (which can be considered as linear systems) are applicable to faulty networks that adopt the proposed MSR algorithm. Using these properties, a better higher bounds for the convergence rate and time are found.

\begin{definition}[Ergodicity]
A stochastic matrix $W$ is called \textit{ergodic} if $\lim_{t \rightarrow \infty} W^t= \textbf{1}d^T$. Where \textbf{1} is a vector with all elements equal to $1$ and $d$ is a vector with elements $0 \leq d_i \leq 1$ and $\textbf{1}^Td=1$.
\end{definition}

\begin{lemma} \cite{markov}
Let $y$ be a non-negative vector and $W$ a stochastic matrix. If $z=Wy$ then
\begin{equation}
\max_iz -\min_iz \leq \gamma(W) \max_iy - \min_iy
\end{equation}
where
\begin{equation}
\gamma(W)=\frac{1}{2} \max_{i,j}\sum\limits_k|\omega_{ik}-\omega_{jk}| = 1- \min_{i,j} \sum\limits_k \min\{\omega_{ik},\omega_{jk}\}
\end{equation}
$\gamma(W)$ is called the coefficient of ergodicity of $W$. Furthermore, if $\gamma(W)<1$, $W$ is scrambling. 
\end{lemma}

Let $W(t)$ be defined as the transition matrix of network, constructed using the coefficients that are presented in (3.1). $W(t)$ is a non-negative row-stochastic matrix for all $t\geq0$. In the transition matrix of a network one can assign $\omega_{ii}=1$ if $i \in F$.

Considering Definition 4.1 and Lemma 4.1, it is not guaranteed that matrix $W(t)$ is ergodic since there might exist more than one faulty nodes and the matrix $W(t)$ would have more than one zero eigenvalue.

As mentioned before, the proposed MSR algorithm with $f_a=0$ resembles Linear Consensus algorithm. From Theorem 4.1 and Lemma 4.1, the following lemma can be concluded.

\begin{lemma}
In an asynchronous network with bounded delay on communication links, no Byzantine node ($f_t=0$) and $W(t)$ as the transition matrix at time $t$, in which, nodes update their state value using the proposed MSR algorithm with parameter $f_a=0$ (or using Linear Consensus algorithm), if
\begin{equation*}
C=W(t)W(t+\Delta t_M) ... W\big(t+(n-r)\Delta t_M\big)
\end{equation*}
then C is scrambling if and only if the structure of the network is $r$-robust.
\end{lemma}

Lemma 4.2 implies that using Linear Consensus algorithm, the property presented in Theorem 4.1 for faulty networks, is valid in non-faulty networks as well. In the following theorem, using the facts that are presented in this chapter, we show that the property of ergodicity value is valid for the network of non-faulty nodes in a faulty network.

\begin{theorem}
In an asynchronous network with bounded delay on communication links, maximum $f_t$ number of Byzantine nodes, in which, nodes update their state values using the MSR algorithm with parameter $f_a$ ($ f_a\geq f_t$),
\begin{equation}
e(t+\tau_e) \leq (1-\alpha) e(t) 
\end{equation}
if and only if the network of non-faulty nodes is ($f_a+1$)-robust where $\alpha$ is the minimum of the averaging coefficients $\omega_{ij}(t_{r}^i)$ in (3.1) and $\tau_e=(n-f_a-1)\Delta t_M $.
\end{theorem}

\begin{proof}
\textit{(Sufficiency)}We divide the sufficiency in two parts for better understanding. First, we assume that non-faulty nodes eliminate all the received values by Byzantine nodes or Byzantine nodes do not send different values at the same time to non-faulty nodes. Let
\begin{equation*}
C(t)=W(t)W(t+\Delta t_M) ... W\big(t+(n-f_a-1)\Delta t_M\big)
\end{equation*}
and
\begin{equation*}
\gamma'(C)=\frac{1}{2} \max_{i,j \in V \setminus F}\sum\limits_k|c_{ik}-c_{jk}|
\end{equation*}
\begin{equation}
 = 1- \min_{i,j \in V \setminus F} \sum\limits_k \min\{c_{ik},c_{jk}\}
\end{equation}
where
\begin{equation*}
0\leq\gamma'(C)\leq 1.
\end{equation*}

 If $x_l(t)=M(t)$ and $x_{l'}(t)=m(t)$, from Lemma 3.1 and Theorem 4.1, we have:
\begin{equation*}
 x_l(t+\tau_e) -x_{l'}(t+\tau_e) < x_l(t) -x_{l'}(t)
\end{equation*}
Since $f_a \geq f_t$ and the structure of the network of non-faulty nodes is $(f_a+1)$-robust, we have:
\begin{equation*}
x_l(t+\tau_e)-x_{l'}(t+\tau_e) \leq \sum\limits_{j} u_j x_j(t)
\end{equation*} 
where $u_j=c_{lj}-c_{l'j}$ and $x_j(t)=x_{lj}(t)=x_{lj'}(t)$. Note that $\sum\limits_{j} u_j=0$. Let $j'$ represent the indices $j$ that $u_j>0$ and $j"$ the indices for which $u_j<0$. Hence,
\begin{equation*}
\theta = \sum\limits_{j'} u_{j'} = - \sum\limits_{j"} u_{j"} = \frac{1}{2}\sum\limits_{j} |u_j| = \frac{1}{2} \sum\limits_{j} |c_{lj} - c_{l'j}|.
\end{equation*}
Then,
\begin{equation*}
x_l(t+\tau_e)-x_{l'}(t+\tau_e)\leq \theta \Bigg( \frac{\sum\limits_{j'} |u_{j'}|x_{j'}(t)}{\sum\limits_{j'} |u_{j'}|} - \frac{\sum\limits_{j"} |u_{j"}|x_{j"}(t)}{\sum\limits_{j"} |u_j"|}\Bigg)
\end{equation*}
\begin{equation*}
\leq \theta \big(\max_{i\in V \setminus F}x_i(t) - \min_{i\in V \setminus F}x_i(t)\big) \leq \gamma'(C)e(t).
\end{equation*}
Now, suppose Byzantine nodes send different values to different nodes at the same time and non-faulty nodes might accept these values. As result,
\begin{equation*}
x_l(t+\tau_e)-x_{l'}(t+\tau_e) \leq \sum\limits_{j} c_{lj}x_{lj}(t)- \sum\limits_{j} c_{lj'}x_{lj'}(t).
\end{equation*}
Moreover,
\begin{equation*}
\min_{i,j \in V \setminus F} \sum\limits_{k\in V \setminus F} \min\{c_{ik},c_{jk}\} \geq \alpha.
\end{equation*}

 Theorem 4.1 states that after $\tau_e$, $e(t)$ decreases. Due to above equation, the amount of decrease has direct relation with $c_{ij}$ weights. Therefore by applying (4.13),
 \begin{equation*}
 e(t+\tau_e) \leq (1-\alpha) e(t) 
 \end{equation*}
which completes the sufficiency part of the proof.


\textit{(Necessity)} Suppose the structure of the network of non-faulty nodes is not at least $(f_a+1)$-robust. From the definition of robustness, there exist two disjoint subsets $S_1$ and $S_2$ with reachability less than or equal to $f_a$. Now, suppose that nodes of $S_1$ and $S_2$ have initial state values $a$ and $b$ respectively. Also, assume the Byzantine nodes do not send any value to their neighbors. Due to the definition of the MSR algorithm with parameter $f_a$, nodes of $S_1$ and $S_2$ eliminate all the received values. Therefore,
\begin{equation*}
\max_{i\in V \setminus F} x_i(t+\tau_e) -\min_{i\in V \setminus F}x_i(t+\tau_e) = \max_{i\in V \setminus F}x_i(t) - \min_{i\in V \setminus F}x_i(t)
\end{equation*}
and as result,
\begin{equation*}
\gamma'(C)=1
\end{equation*}
which completes the necessity part of the proof.
\end{proof}

For a faulty network, we refer to $C$ as \textit{semi transition matrix} over $\tau_e$ period. We use the word \textit{semi} since, in faulty networks that nodes adopt the MSR algorithm to update their states, the following equation does not necessarily hold because of the behavior of Byzantine nodes.
\begin{equation*}
x(t+\tau_e)=C(t)x(t)
\end{equation*}
On the other hand, $C$ can represent many features of the network. 

 Using the above properties found in Theorems 4.1 and 4.3, \begin{equation}
e(k)\leq\big(1-\alpha\big)^k e(0)
\end{equation}
if and only if  the network of non-faulty nodes is ($f_a+1$)-robust. Where $\alpha$ is the lower bound on $\omega_{ij}$ coefficients defined in (3.1) and $k=\lfloor \frac{t}{\tau_e} \rfloor $. Note that, $y=f(x)=\lfloor x \rfloor$ is the greatest integer function.

 (4.14) suggest a better bound for the convergence rate of the MSR algorithm compared to (4.4). In the following, we show that this bound is applicable to non-faulty networks as well.

\begin{theorem}
In a network with no faulty node and connected underlying graph, in which, each node updates its state value using linear consensus algorithm proposed in Section 2.5,
\begin{equation}
e(k)\leq\big(1-\alpha\big)^k e(0).
\end{equation}
where $\alpha$ is the lower bound on $\omega_{ij}$ coefficients defined in (3.1) and $k=\lfloor \frac{t}{\tau_e} \rfloor $. Note that, $y=f(x)=\lfloor x \rfloor$ is the greatest integer function.
\end{theorem}
\begin{proof}
Due to the definition of robustness, a network with connected underlying graph is at least $1$-robust. Therefore, $\tau_e=(n-1)\Delta t_M$. The remainder of the proof is the same as the method that we used to derive (4.14).
\end{proof}
 
Using (4.12), an upper bound for the convergence time can be found as:
\begin{equation}
t \leq \tau_e \big( \log^{\frac{\epsilon}{e(0)}}_{(1-\alpha)}+1 \big).
\end{equation}

The presented bounds for the convergence time and rate are applicable to both synchronous and asynchronous networks with or without time delay on communication paths. 

\section{Convergence Analysis of Time-Varying Networks}
 
 In this section, we extend our previous results to the case of networks with time-varying underlying graph topology.
 
\begin{theorem}
In an asynchronous network with time-varying underlying graph topology, bounded delay on communication links and maximum $f_t$ number of Byzantine nodes, in which, each non-faulty node updates its state value using the proposed MSR algorithm with parameter $f_a$ ($f_a \geq f_t$),
\begin{equation}
e \Bigg( t+(n-f_a-1)\Delta t_M \Bigg) < e(t)
\end{equation}
 if $|\{t_l\} \cap \{t_r^i\}| \rightarrow \infty$ as $t \rightarrow \infty$, for all $i \in V \setminus F$, where $\{t_l\}$ with $l=1, 2 , ...$ represents the set of time instances that the topology of the network of non-faulty nodes is at least $(f_a+1)$-robust with bounded $\Delta t_l$ and $\{t_r^i \}$ is the set of update time steps of node $i$.
\end{theorem}
\begin{proof}
Assume each sequence of the set $\big\{ \{t_l\} \cap \{t_r^i\}\big\}$ is bounded by $\alpha_l$. Then,
\begin{equation}
 \Delta t_{M} = \alpha_t + \alpha_\tau+\alpha_l.
\end{equation}
 The remainder of the proof is the same as the sufficiency part for the proof of Theorem 4.1.
\end{proof}

The above theorem is the extension of Theorem 4.1 for networks with time-varying underlying graph topology. The result of the theorem is applicable to synchronous systems as well. This fact can be concluded by taking $\{t_r^i \}=\{t_r^j \}$ for all $i,j \in V \setminus F$. Moreover, it is valid for networks without delay on communication paths where $\alpha_\tau=0$. 

\begin{remark}
Consider a faulty time-varying asynchronous network $G(t)$ with $f_t$ number of faulty nodes in which nodes use the proposed MSR algorithm to update their state values with parameter $f_a$. Let $\Phi = \{G_i\}$ be the set of underlying graphs of the time-varying network i.e. $G(t) \in \Phi$. Let $\xi = \{C_i\}$ be the set of semi transition matrices of a time-varying network throughout $\tau_e$ i.e. 
\begin{gather*}
C_i=W(t_i)W(t_i+\Delta t_M) ... W\big(t_i+\tau_e \big)
\end{gather*}
where $W(t_i)$ is constructed by applying the MSR algorithm to $G(t_i)$ at any time $t_i\geq 0$ as explained in Section 3 and $\tau_e=(n-f_a-1)\Delta t_M$. Let $\Phi'$ be a subset of $\Phi$ in which members have at least $(f_a+1)-robust$ structure for the network of non-faulty nodes. Then, $v\big(x(k)\big) = e(k)$ is a common Lyapunov function for members of $\xi$ if and only if $|\Phi'| \geq 1$ and $|\{t_l\} \cap \{t_r^i\}| \rightarrow \infty$ as $t \rightarrow \infty$, for all $i \in V \setminus F$, where $\{t_l\}$ with $l=1, 2 , ...$ represents the set of time instances that $G(t) \in \Phi'$ and $k=\lfloor \frac{t}{\tau_e} \rfloor $ in which $y=f(x)=\lfloor x \rfloor$ is the greatest integer function.
\end{remark}

Considering (4.16), Theorem 4.3 is applicable to the case of time-varying networks.

\begin{theorem}
In an asynchronous network with time-varying underlying graph topology, bounded delay on communication links and maximum $f_t$ number of Byzantine nodes, in which, nodes update their state values using the MSR algorithm with parameter $f_a$ ($ f_a\geq f_t$),
\begin{equation}
e(t+\tau_e) \leq (1-\alpha) e(t) 
\end{equation}
if $|\{t_l\} \cap \{t_r^i\}| \rightarrow \infty$ as $t \rightarrow \infty$, for all $i \in V \setminus F$, where $\{t_l\}$ with $l=1, 2 , ...$ represents the set of time instances that the topology of the network of non-faulty nodes is at least $(f_a+1)$-robust with bounded $\Delta t_l$, $\{t_r^i \}$ is the set of update time steps of node $i$, $\alpha$ is the minimum of the averaging coefficients $\omega_{ij}(t_{r}^i)$ in (4) and $\tau_e=(n-f_a-1)\Delta t_M $.
\end{theorem}
\begin{proof}
The proof is the same as the sufficiency part of the proof of Theorem 4.3 using (4.16).
\end{proof}

Using Theorem 4.7, (4.16) and by applying the same method that has been adopted for deriving a bound for the convergence rate of time-invariant networks, the maximum bound for the convergence rate for time-varying networks would be:
\begin{equation}
e(k)\leq\big(1-\alpha\big)^k e(0)
\end{equation} 
where $k=\lfloor \frac{t}{\tau_e} \rfloor $ in which $y=f(x)=\lfloor x \rfloor$ is the greatest integer function. Therefore, convergence time can be found using 
\begin{equation}
t \leq \tau_e \big( \log^{\frac{\epsilon}{e(0)}}_{(1-\alpha)}+1 \big).
\end{equation}
 if $|\{t_l\} \cap \{t_r^i\}| \rightarrow \infty$ as $t \rightarrow \infty$, for all $i \in V \setminus F$.
 
 The results are applicable to synchronous networks as well where $\{t_r^i\} = \{t_r^j\}$ for all $i, j \in V \setminus F$.

%\section{Existence of Common Lyapunov Functions for Time-Varying Faulty Networks}

%In this section, we analyze the existence of a \textit{common Lyapunov function} for the set of underlying graphs of time-varying networks. The results in \cite{4459784} has motivated us to assess the existence of such a property in faulty networks in which nodes update their state values using the proposed MSR algorithm. 

%Consider a faulty time-varying asynchronous network $G(t)$ with $f_t$ number of faulty nodes in which nodes use the proposed MSR algorithm to update their state values with parameter $f_a$. Let $\Phi = \{G_i\}$ be the set of underlying graphs of the time-varying network i.e. $G(t) \in \Phi$. Let $\xi = \{C_i\}$ be the set of semi transition matrices of a time-varying network built using (4.19) throughout the time i.e. 
%\begin{gather*}
%C_i=W(t_i)W(t_i+\Delta t_M) ... W\big(t_i+\tau_e \big)
%\end{gather*}
%C_2=W\big((n-f_a-1)\Delta t_M\big)W\big(\Delta t_M+(n-f_a-1)\Delta t_M\big) ... W\big(2(n-f_a-1)\Delta t_M\big) \\ . \\ . \\ .

%where $W(t_i)$ is constructed by applying the MSR algorithm to $G(t_i)$ at any time $t_i\geq 0$ as explained in Section 3.1 and $\tau_e=(n-f_a-1)\Delta t_M$.

%Let $\Phi'$ be a subset of $\Phi$ in which members have at least $(f_a+1)-robust$ structure for the network of non-faulty nodes. In the following, we show $v\big(x(k)\big) = e(k)$ is a common Lyapunov function for members of $\xi$ if and only if $|\Phi'| \geq 1$ and $|\{t_l\} \cap \{t_r^i\}| \rightarrow \infty$ as $t \rightarrow \infty$, for all $i \in V \setminus F$, where $\{t_l\}$ with $l=1, 2 , ...$ represents the set of time instances that $G(t) \in \Phi'$ and $k=\lfloor \frac{t}{\tau_e} \rfloor $ in which $y=f(x)=\lfloor x \rfloor$ is the greatest integer function.

%\begin{theorem}
%In an asynchronous network with time-varying underlying graph topology, bounded delay on communication links and maximum $f_t$ number of Byzantine nodes, in which, nodes update their state values using the proposed MSR algorithm with parameter $f_a$ ($ f_a\geq f_t$), the two following statements are equal if and only if $|\Phi'| \geq 1$ and $|\{t_l\} \cap \{t_r^i\}| \rightarrow \infty$ as $t \rightarrow \infty$, for all $i \in V \setminus F$.
%\begin{itemize}
%\item[(i)] Achieving approximate Byzantine consensus in the network is guaranteed.
%\item[(ii)] $v\big(x(k)\big) = e(k)$ is a common Lyapunov function for members of the set $\xi$.
%\end{itemize}
%\end{theorem}

%\begin{proof}
%\textit{(Sufficiency)}(i) can be concluded for Theorem 3.3. In Theorem 4.7, it is proved that $e(t+\tau)<e(t)$. As result, $\Delta V(k) = e(k+1)-e(k)<0$. Therefore, $v\big(x(k)\big) = e(k)$ is a common Lyapunov function for the set $\xi$ which results to (ii).

%\textit{(Necessity)} Assume $|\Phi'| = 0$. Then, due to Theorem 3.3, approximate Byzantine consensus can not be achieved. Moreover, if $|\{t_l\} \cap \{t_r^i\}| \not\to \infty$, there exists a $C_i \in \xi$ for which $\gamma'=1$. Hence, there exists a non-negative integer $k'$ that $V(k') = e(k'+1)-e(k')=0$.
%\end{proof}

%The above theorem relates approximate Byzantine consensus in time-varying networks to the existence of a common Lyapunov function for a set of semi transition matrices which are built by applying the MSR algorithm to $G(t) \in \Phi$. It might be worthy to mention that Theorem 4.8 is applicable to synchronous networks with or without delay on communication paths.

\section{Numerical Analysis}

In this section, we present some examples to evaluate our results in this chapter. 
\begin{example} \normalfont
Consider Example 3.1 where a complete graph with $4$ nodes is the underlying graph of the network. Node 4 is Byzantine and the network of non-faulty nodes is $2$-robust. $\Delta t_M=10$ and as result, $\tau_e=20$. It is assumed that each non-faulty node $i$ assigns equal weights to state values of its neighbors and then applies (3.1). Hence, $\alpha=\frac{1}{4}$. $e(0)=4$ and $\epsilon$ is supposed to be $0.1$. Using (4.4), we have:
\begin{equation*}
e(k)\leq (0.99375)^k e(0)
\end{equation*}
where $k=\lfloor \frac{t}{20} \rfloor $. By applying the second set of higher bounds for the convergence rate and time that are proposed in Section 4.3, we have:
 \begin{equation*}
e(k)\leq (0.75)^k e(0)
\end{equation*}
which is compromised using (4.18). Moreover, convergence time can be calculated using (4.19) which is $t\approx 275$.
\end{example}

\begin{example} \normalfont
Consider the set of graphs depicted in Figure 4.1. Assume a time varying-network $G(t)$ which uses these graphs for its underlying graph topology. The network changes its topology every second. It starts from topology (a) in Figure 4.1. In the next second, it changes to topology (b). Afterwards, to (c). Then, to (a) and continues this loop. It is assumed that Node 1 is Byzantine which sends different values to its neighbor nodes. The values of the Byzantine node are generated by \textsf{5*rand} (we use Matlab notations). The initial state values of non-faulty Nodes 2, 3 and 4 are $x_N(0)=[3, 5, 1]^T$. These nodes update their state value every 2, 4 and 5 seconds. Furthermore, the maximum communication delay between every two neighbor nodes is 5 seconds. As result, $\Delta t_M=14$ which implies $\tau_e=28$. If the nodes adopt equal weighting in (3.1) to update their states, $\alpha=\frac{1}{4}$. Let $\epsilon=0.1$. Therefore, using (4.19) the maximum convergence time would be around 380 seconds. However, Figure 4.2 shows that non-faulty nodes converge to a common value and approximate Byzantine consensus is achieved much faster.



\begin{figure}
\begin{center}
\begin{tabular}{ccc}
\includegraphics[scale=0.6]{Fig413.jpg} & \includegraphics[scale=0.6]{Fig411.jpg} &  \includegraphics[scale=0.6]{Fig412.jpg} \\(a) & (b)  & (c)  \\
\end{tabular}
\caption{(a) is a disconnected graph. (b) is a complete graph in which the network of non-faulty nodes is $2$-robust and (c) is an incomplete graph with ring topology. }
\end{center}
\end{figure}


\begin{figure}
\begin{center}
\includegraphics[scale=0.3]{Fig42.jpg}
\caption{Simulation result of the network explained in Example 2. }
\end{center}
\end{figure}

\end{example}

\section{Summary of the Chapter and Concluding Remarks}

In this chapter, we have analyzed convergence properties of the proposed MSR algorithm. We started by introducing maximum bounds for the convergence rate and time of the algorithm, considering the network as a non-linear non-autonomous system. Then, using matrix representation, we have derived better bounds for the convergence rate and time. In Section 4.3, we extended our results to time-varying networks and bounds for the convergence rate and time of such networks are introduced. Moreover, the existence of a common Lyapunov function for time-varying networks is shown. Finally, numerical analysis is included to evaluate our results.

Throughout the chapter, it is shown that the results are applicable to both asynchronous and synchronous networks. Moreover, the effect of delay on communication paths of networks is considered in our results. 


\chapter{USE OF CONVEX HULLS IN DESIGNING FAULT-TOLERANT DISTRIBUTED ALGORITHMS}


In most of the fault-tolerant algorithms that have been introduced
for Byzantine networks, it is assumed that each node has knowledge of the maximum number of faulty nodes, $f_t$, in the network. In this chapter, we propose a new family of algorithms which do not require this a priori information and evaluate its performance in complete networks facing Byzantine failures. We propose a more restrictive but widespread model of Byzantine fault known as Malicious (one-sided Byzantine) fault and propose a fault-tolerant algorithm for it. In the construction of our algorithms which we refer to as Shrinking Convex Hulls (SCH), we employ an  interesting feature of non-faulty nodes in Byzantine networks in order to maintain each node's state value in a convex hull. We analytically examine the convergence properties of the proposed algorithm and compare its performance in simulations with respect to the existing literature. Note that, throughout this chapter, we refer to a network which contains at least one Byzantine node as \textit{Byzantine network} and a network which contains Malicious nodes, \textit{Malicious network}. Also, throughout the chapter, we refer to a synchronous network without time delay on communication paths, as simply, \textit{network}. Therefore, in this chapter, $t$ is a positive integer.

\section{Malicious Fault}

In this section, the notion of Malicious fault is defined.

\begin{definition} A node $i \in V$ is said to be Malicious (one-sided Byzantine) if it sends the same value to all of its neighbors at a time step but it applies some other arbitrary functions to update its state.
\end{definition}

This type of fault is prevalent in distributed systems where each agent acquires the state of its neighbors by observing. In other words, agents do not send their state values to each other. In this type of networks, Byzantine nodes can not send different values to different agents at the same time and as result, Byzantine fault is reduced to Malicious fault. For instance, consider a flock of birds. Each agent (bird) obtains information about the position of its neighbors by observation. As result, there exists no two non-faulty agents which obtain different information about an agent at the same time.  

\section{The Shrinking Convex Hull Algorithm for Complete Malicious Networks}

In this section, we first investigate one of the significant features in consensus networks that can be adopted to develop a new family of fault-tolerant algorithms which do not require any initial knowledge on the maximum number of faulty nodes in the network. By use of the proposed algorithm, nodes do not throw away useful state values of their neighbors in each iteration. In other words, they can determine their suspected neighbors with more accuracy than the other algorithms. An additional advantage of this algorithm is that information loss is less due to the above mentioned reasons and as result, the final consensus value is nearer to mean of the initial values of non-faulty nodes in complete networks.

In the following, we first introduce our algorithm which is designed to resist against Malicious failures in Byzantine complete networks and then prove its success.

 Suppose that, each node $i$ maintains a convex hull $\chi_i$ at time $t$ that is defined as
\begin{equation}
\chi_i(t)=[\min_{j \in N'_i(t-1)}x_j(t-1),\max_{j \in N'_i(t-1)}x_j(t-1)]
\end{equation}
where $N'_i(t)$ is a set that consists of state values of node $i$'s neighbors which are in $\chi_i(t)$ (including node $i$'s value too). Also, $\chi_i(0)=[-\infty, \infty]$.

For each time step the algorithm repeats the following.

\textbf{SCH-CMN algorithm:}
\begin{itemize}
\item[(S1)] Each node $i$ receives its neighbor values at time $t$.
\item[(S2)] If $x_j(t) \notin \chi_i(t)$ then node $i$ throws it away.
\item[(S3)] Each normal node $i$ applies the update rule
\begin{equation}
x_i(t+1)= \sum_{j \in N'_i(t)} \omega_{ij}(t)x_j(t)
\end{equation}
where the weights $\omega_{ij}(t)$ satisfy the conditions discussed in (3.1).
\item[(S4)] If $|N'_i(t)|=1$ (which is $i$'s value) at time $t$, then node $i$ picks the latest previous convex hull that $|N'_i|>1$. Else, it updates the convex hull using the below protocol.

\begin{enumerate}
\item[(I)] After the transmitting sequence, each node $i$ chooses $\min_{j \in N'_i(t)}x_j(t)$ and $\max_{j \in N'_i(t)}x_j(t)$.
\item[(II)] If $\min_{j \in N'_i(t)}x_j(t) > \min_{j \in N'_i(t-1)}x_j(t-1)$, it chooses the $\min_{j \in N'_i(t)}x_j(t)$ as the lower bound of $\chi_i(t+1)$, else, it chooses the second minimum value that fulfills the stated condition.
\item[(III)] If $\max_{j \in N'_i(t)}x_j(t) < \max_{j \in N'_i(t-1)}x_j(t-1)$, it chooses the $\max_{j \in N'_i(t)}x_j(t)$ as the higher bound of $\chi_i(t+1)$, else, it chooses the second maximum value that fulfills the stated condition.
\end{enumerate}
\end{itemize}

The above algorithm is designed to overcome Malicious failures in a Complete Malicious Network (CMN); therefore we call it the SCH-CMN algorithm. Recall that, designing fault-tolerant algorithms for complete Byzantine networks is a challenging field which has been studied extensively in the literature. SCH-CMN algorithm is light-weight and guarantees Approximate Byzantine Consensus regardless of the number of faulty nodes in the network. As result, in the worst situation, two non-faulty nodes can resist against adverse behavior of as many as possible Malicious nodes in any complete network.

\subsection{Proof of Success}

In this part, we prove the success of the algorithm in the presence of Malicious failures in complete networks. First, we present two lemmata, which are utilized subsequently in proving the success of the SCH-CMN algorithm.

\begin{lemma}
In a complete network in which nodes update their state value using the SCH-CMN algorithm, we have $\chi_i(t)=\chi_j(t)\subset [m(0), M(0)]$, for all $i, j \in V\setminus F$ and $\ t>0$, if for all $ k \in F, m(0)\leq x_k(0) \leq M(0)$.
\end{lemma}
\begin{proof}
In order to prove this lemma, we proceed by induction.
Note that we have $\chi_i(0)=\chi_j(0)=[-\infty,\infty]$ and $\chi_i(1)=\chi_j(1)=[m(0),M(0)]$, for all $ i, j \in V\setminus F $.
Suppose $\chi_i(t)=\chi_j(t)$  holds for all $ i, j \in V\setminus F $.
Since all non-faulty nodes receive the same information at time $t$, we have $N'_i(t)=N'_j(t)$ which results in $\min_{k \in N'_i(t)}x_k(t)=\min_{k \in N'_j(t)}x_k(t)$ and $\max_{k \in N'_i(t)}x_k(t) = \max_{k \in N'_j(t)}x_k(t)$.
Utilize (5.1) to obtain $\chi_i(t+1)=\chi_j(t+1)$, for all $ i, j \in V\setminus F $.
\end{proof}

\begin{lemma}
In  a complete network, in which nodes update their state value using the SCH-CMN algorithm, we have $|N'_i(t)|\geq |V\setminus F|$, for all $i \in V \setminus F$, if for all $ k \in F, m(0)\leq x_k(0) \leq M(0)$.
\end{lemma}
\begin{proof}
In order to prove this lemma, we proceed by contradiction. Suppose that we have $|N'_i(t)|<|V\setminus F|$, there exist a $t_1 \geq 0$ and an $i \in V \setminus F$. Consequently, there exists a $ j \in V\setminus F$ that $x_j(t_1) \notin N'_i(t_1)$. Hence, we obtain $\chi_i(t_1) \neq \chi_j(t_1)$ which contradicts with Lemma 5.1.
\end{proof}

\begin{theorem}
In  a complete network in which nodes update their state value using the SCH-CMN algorithm, if for all $ k \in F, m(0)\leq x_k(0) \leq M(0)$, approximate Byzantine consensus is guaranteed, i.e. $\forall i \in V\setminus F$, $lim_{t \rightarrow \infty} x_i(t)=L$, $m(0)\leq L \leq M(0)$.
\end{theorem}
\begin{proof}
From Lemmata 1 and 2, we have for all $ t \geq 0$, for all $ i, j \in V \setminus F $, $\chi_i(t)=\chi_j(t)$ and $|N'_i(t)| \geq |V \setminus F| \geq 2$.
Also, from the algorithm $\chi_i(t+1) \subset \chi_i(t)\subset [m(0), M(0)]$. As result, $\min_{j \in N'_i(t+1)}x_j(t+1) > \min_{j \in N'_i(t)}x_j(t)$ and $\max_{j \in N'_i(t+1)}x_j(t+1) < \max_{j \in N'_i(t)}x_j(t)$. Subsequently, we conclude for all $ t {\geq 0}$, there exists an $ \epsilon \in {\geq 0}$ that $ |\max_{j \in N'_i(t)}x_j(t)-\min_{j \in N'_i(t)}x_j(t)| \leq \epsilon$. It means $lim_{t \rightarrow \infty} \max_{j \in N'_i(t)}x_j(t)=lim_{t \rightarrow \infty}\min_{j \in N'_i(t)}x_j(t)=L$ and since, node $i$'s convex hull always maintains its own value $lim_{t \rightarrow \infty} x_i(t)=L$. Thus, approximate Byzantine consensus is guaranteed.
\end{proof}

The proof verifies that in any complete network approximate Byzantine consensus is guaranteed, in the presence of any number and type of Malicious nodes. In other words, each non-faulty node can recognize its faulty neighbors precisely. This is an advantage comparing to other types of fault-tolerant algorithms.

\subsection{Numerical Analysis}

In this part, we will analyze performance of SCH-CMN algorithm in the presence of different Malicious behaviors of faulty nodes.
The results confirm superior performance of the algorithm in various Malicious complete networks.

\begin{example}
\normalfont Figure 5.1 shows the simulation results of a complete network with $5$ nodes where $3$ of them are Malicious.
Two of the faulty nodes behave unstably and increase their values arbitrarily over time and the other one uses a White Gaussian Noise sequence to update its value.
As depicted in Figures 5.1, the linear consensus algorithm and the proposed MSR algorithm are unable to achieve approximate Byzantine consensus to the network while approximate Byzantine consensus is guaranteed by adopting SCH-CMN.
\end{example}

\begin{example} \normalfont
Another case is analyzed in Figure 5.2 which illustrates the simulation results for a complete network with $8$ nodes.
In this example, $4$ nodes are representing Malicious behavior such that $3$ of them are unable to update their state values
and  just  send constant values while another updates its value arbitrarily.
The convergence of convex hulls of non-faulty nodes in the same network is demonstrated in Figure 5.3.
\end{example}


\begin{figure}
\begin{center}
\begin{tabular}{c}
\includegraphics[scale=0.2]{LCA1.jpg} \\(a) Linear consensus algorithm \\
\includegraphics[scale=0.2]{wmsr1.jpg} \\ (b) MSR \\ 
\includegraphics[scale=0.2]{SCH1.jpg} \\ (c) SCH-CMN \\
\end{tabular}
\caption{(a) and (b) show failure of linear consensus algorithm and the MSR respectively in the presence of $3$ Malicious nodes while SCH-CMN succeeds in the same situation. }
\end{center}
\end{figure}



\begin{figure}
\begin{center}
\begin{tabular}{c}
\includegraphics[scale=0.2]{LCA2.jpg} \\(a) Linear consensus algorithm \\
\includegraphics[scale=0.2]{wmsr2.jpg} \\ (b) MSR \\
\includegraphics[scale=0.2]{SCH2.jpg} \\ (c) SCH-CMN \\
\end{tabular}
\caption{(a) and (b) show failure of linear consensus algorithm and the MSR respectively in the presence of $4$ Malicious nodes, where $3$ of them are just sending constant values, (c) shows SCH-CMN succeeds in the same situation. }
\end{center}
\end{figure}


\begin{figure}
\begin{center}
\includegraphics[scale=0.3]{SCH4.jpg}
\caption{Simulation results for a complete network. The figure shows that convex hulls of non-faulty nodes converge as their states converge.}
\end{center}
\end{figure}

\section{The Shrinking Convex Hull Algorithm for Complete Byzantine Networks}

In this section, we introduce a new algorithm which can tolerate against Byzantine failures in complete networks. We use shrinking convex hull feature to facilitate our algorithm. It is shown that the algorithm has feasible performance in determining adverse behavior of nodes and it detects suspicious nodes accurately. In other words, there exists no $t$ such that a non-faulty node disregards state value of another non-faulty node due to bad recognition.

In the following, we first introduce our algorithm which is designed to resist against Byzantine failures in Byzantine complete networks and then prove its success.

 Suppose that, each node $i$ maintains a convex hull $\chi_i$ at time $t$ that is defined as
\begin{equation}
\chi_i(t)=[L\chi_i(t),H\chi_i(t)]
\end{equation}
where $L\chi_i(t)$ and $H\chi_i(t)$ are lower and higher bound of node $i$'s convex hull respectively. These values can be calculated using below equations.
\begin{equation}
L\chi_i(t)=\frac{1}{n}\Big(x_i(t-1)+(n-1)[\min_{k \in N_{\chi_i}(t)}L\chi_k(t-1)]\Big)
\end{equation}
\begin{equation}
H\chi_i(t)=\frac{1}{n}\Big(x_i(t-1)+(n-1)[\max_{k \in N_{\chi_i}(t)}H\chi_k(t-1)]\Big)
\end{equation}
 $N_{\chi_i}(t)$ is a set that consists of acceptable convex hulls which are belong to node $i$'s neighbors (including node $i$ too) and $N_{\chi_i}(t) \subset N'_i(t)$ where $N'_i(t)$ is the set of state values that $i$ uses them to update its own state. Also, note that $\chi_i(0)=[-\infty, \infty]$ and $m(0)$ and $M(0)$ are the minimum and maximum initial values of the non-faulty nodes. % then $\chi_i(1)=[m(0),M(0)]$. Moreover, $n$ represents the number of nodes in the network.

For each time step the algorithm repeats the following.

\textbf{SCH-CBN algorithm:}
\begin{itemize}
\item[(S1)] Each node $i$ receives its neighbor values at time $t$.
\item[(S2)] If $x_j(t) \notin \chi_i(t)$ then node $i$ throws it away and will not accept state value of node $j$ for all future iterations. 
\item[(S3)] Each normal node $i$ applies the update rule
\begin{equation}
x_i(t+1)= \sum_{j \in N'_i(t)} \omega_{ij}(t)x_(t)
\end{equation}
where $\omega_{ij}(t)=\frac{1}{|N'_i(t)|}$.
\item[(S4)] If $t=1$, non-faulty node $i$ chooses the minimum and maximum received state value as lower and higher bound of its convex hull respectively. Else, it updates its convex hull using the below protocol.

\begin{enumerate}


\item[(I)] All nodes send their convex hulls to their neighbor nodes.
\item[(II)] For $j \in N'_i(t)$, if $\chi_j(t) \subset \chi_j(t-1)$ (but $\chi_j(t) \neq \chi_j(t-1)$) and $x_i(t) \in \chi_i(t)$ then node $i$ keeps the $\chi_j(t)$, else, it throws it away and will not accept any value from node $j$ for all future iterations. Using the accepted convex hulls node $i$ calculates $L\chi_i(t+1)$ and $H\chi_i(t+1)$ by adopting (5.4) and (5.5).
\item[(III)] If $L\chi_i(t+1)<L\chi_i(t)$ then node $i$ does not update $L\chi_i$ which means $L\chi_i(t+1)=L\chi_i(t)$. Similarly, if $H\chi_i(t+1)>H\chi_i(t)$ then node $i$ does not update $L\chi_i$ which means $H\chi_i(t+1)=H\chi_i(t)$.
\item[(IV)] Node $i$ computes $\chi_i(t+1)$ by employing (5.3).
\end{enumerate}
\end{itemize}

The above algorithm is designed to overcome Byzantine failures in a Complete Byzantine Networks (CBN); therefore we call it the SCH-CBN algorithm. Note that, designing fault-tolerant algorithms for complete Byzantine networks is a challenging task which was examined in many other articles. SCH-CBN algorithm guarantees approximate Byzantine consensus regardless of the number of faulty nodes in a network. As result, in the worst situation, two non-faulty nodes can resist against adverse behavior of as many as possible Byzantine nodes in any complete network. Compared to the previous algorithm (SCH-CMN), in this algorithm, each node uses decision rule of its trusted neighbors. It means, nodes decide not only on basis of their opinions but also, they inquire opinion of their trusted neighbor nodes to judge about states of their neighbors. Hence, decision making is distributed and decision rules are made not solely but locally. Indeed, this feature emphasizes on the notion of distributed decision making in determining decision rules.

\subsection{Proof of Success}

In this part, we prove the success of the algorithm with any number of Byzantine nodes. In this way, assume $F$ is the set of faulty nodes and $x_{ij}(t)$ is the state value which is sent by node $j$ to node $i$.

\begin{lemma}
In a complete Byzantine network where nodes update their state values using SCH-CBN algorithm, $x_i(t) \in \chi_i(t)$, for all $ i \in V\setminus F $ and for all $ t{ \geq 0}$, if $ m(0)\leq x_{kj}(0) \leq M(0)$, for all $ k \in F$ and $ j \in V$.
\end{lemma}
\begin{proof}
In order to prove this Lemma we proceed by induction. We know $x_i(0) \in \chi_i(0)=[-\infty, \infty]$ and $x_i(1) \in \chi_i(1)= [m(0), M(0)]$, for all $ i \in V\setminus F $. Suppose $x_i(t) \in \chi_i(t)$ holds for $ t \in \mathbb{Z}_{> 1}$. A non-faulty node always accepts convex hull of its non-faulty neighbors because convex hull range of a non-faulty node is decreasing as time passes. Therefore, 
\begin{gather*}
x_i(t+1) > L\chi_i(t) \geq \min_{j \in N'_i(t)}L\chi_j(t)
\end{gather*} 
and
\begin{equation*}
x_i(t+1) < H\chi_i(t) \leq \max_{j \in N'_i(t)}\chi_j(t).
\end{equation*}
Hence, by adopting (5.3), we conclude $x_i(t+1) \in \chi_i(t+1)$.
\end{proof}

\begin{lemma}
In a complete Byzantine network where nodes update their state values using SCH-CBN algorithm, $x_i(t) \in \chi_j(t)$, for all $i, j \in V\setminus F $ and for all $ t { \geq 0}$, if $ m(0)\leq x_{kl}(0) \leq M(0)$, for all $k \in F$ and $ l \in V$.
\end{lemma}
\begin{proof}
In order to prove this Lemma we proceed by induction. From the algorithm, $x_i(0) \in \chi_j(0)=[-\infty, \infty]$ and $x_i(1) \in \chi_j(1)=[m(0), M(0)]$, for all $ i, j \in V\setminus F $. Suppose $x_i(t) \in \chi_j(t)$ holds for all $ t {> 1}$. As we mentioned in the proof of Lemma 5.4, all non-faulty nodes accept convex hull of their non-faulty neighbors, therefore $ i \in N_{\chi_j}(t+1)$, for all $ i, j \in V\setminus F $. Moreover, $V\setminus F \in N'_i(t)$, for all $  i \in V\setminus F$ and as result,
\begin{equation*}
 x_i(t+1)=\frac{x_j(t)+\sum_{k \in N'_i(t),k\neq j} x_k[t]}{|N'_i(t)|} 
\end{equation*}
 From the algorithm, we have:
 \begin{equation*}
 \max_{k \in N'_j(t)}H\chi_k(t)\geq H\chi_i(t) >\frac{\sum_{k \in N'_i(t),k\neq j} x_k[t]}{|N'_i(t)|-1} > L\chi_i(t) \geq \min_{k \in N'_j(t)}L\chi_k(t).
\end{equation*}  
Hence,
\begin{equation*}
\frac{x_j(t)+(n-1)\max_{k \in N'_j(t)}H\chi_k(t)}{n} > x_i(t+1) > \frac{x_j(t)+(n-1)\min_{k \in N'_j(t)}L\chi_k(t)}{n} 
\end{equation*}
 and by adopting (5.3), we conclude $x_i(t+1) \in \chi_j(t+1)$.
\end{proof}

\begin{theorem}
In a complete Byzantine network where nodes update their state values using SCH-CBN algorithm, approximate Byzantine consensus is guaranteed if $ m(0)\leq x_{kl}(0) \leq M(0)$, for all $ k \in F$ and $ l \in V$.
\end{theorem}
\begin{proof}
Assume $\mathcal{R}_i(t)=|H\chi_i(t)-L\chi_i(t)|$, for all $ i \in V\setminus F$ is the range of node $i$'s convex hull. Due to the algorithm, $\mathcal{R}_i(t)$ is a decreasing function. Therefore,
\begin{equation*}
 \lim_{t \rightarrow \infty}H\chi_i(t)=\lim_{t \rightarrow \infty}L\chi_i(t)=\Lambda
  \end{equation*}
  and $\Lambda \in [ m(0),M(0)] \in \mathbb{R}$.
  As result, using Lemmata 1 and 2 we conclude $\lim_{t \rightarrow \infty}x_j(t)=\Lambda$, for all $ j \in V \setminus F$.
\end{proof}

 Theorem 5.2 demonstrates that SCH-CBN algorithm can guarantee approximate Byzantine consensus in a Byzantine complete network regardless of the number of faulty nodes.

 \subsection{Numerical Analysis}

In this section, we analyze the performance of the algorithm by assessing an example. 
\begin{example} \normalfont
Consider a network of 5 nodes with complete underlying graph. Suppose 3 nodes are Byzantine and Nodes 4 and 5 are non-faulty. Nodes 1, 2 and 3 send different values to different nodes at the same time. These values are produced using a white Gaussian noise function of Matlab. Figure 5.4 shows the result of the simulation. It is shown that the non-faulty nodes converge to a common value. Moreover, convergence of the convex hulls are illustrated. 
\end{example}

\begin{figure}
\begin{center}
\includegraphics[scale=0.3]{ByzCH.jpg}
\caption{Simulation results for a complete network with 5 nodes where 3 of them are Byzantine.}
\end{center}
\end{figure}

\section{Comparison with the MSR Algorithm}

In this section, we compare Shrinking Convex Hulls algorithms with MSR algorithms. We specifically compare SCH-CMN and SCH-CBN with the MSR algorithm that is proposed in Chapter 3. 

First, we derive the condition that the proposed MSR algorithm succeeds in complete networks. 

\begin{theorem}
In a complete Byzantine network where nodes update their state values using the MSR algorithm proposed in Chapter 3, approximate Byzantine consensus is guaranteed if and only if $f_t\leq \frac{n}{2}-1$, where $f_t$ and $n$ are maximum number of faulty nodes and total number of nodes, respectively.
\end{theorem}

Using the outcome of Theorem 5.3, we enumerate the advantages and disadvantages of SCH algorithms comparing to the MSR algorithm.

\begin{itemize}
\item SCH algorithms can guarantee approximate Byzantine consensus in presence of $n-2$ faulty nodes (which is the worst probable case) while the MSR algorithm can tolerate against $\frac{n}{2}-1$ number of faulty nodes in a complete network. Note that, the term faulty here deputes both Malicious and Byzantine faults.
\item SCH algorithms do not require any a priori knowledge on maximum number of faulty nodes while by adopting the MSR algorithm, each individual node needs this knowledge. Note that, this value should be chosen accurately due to different possible failure scenarios.
\item Using SCH algorithms, $ m(0)\leq x_{kl}(0) \leq M(0)$, for all $ k \in F$ and for all $l \in V$ while this assumption is not necessary the MSR algorithm is applied.
\item By using SCH algorithms, information loss never happens which indicates there exist no iteration that state value of a non-faulty node gets rejected by another non-faulty node. On the other hand, this may happen several times by adopting the MSR algorithm.
\item The MSR algorithm is more light-weight than the SCH algorithms.
\item The MSR algorithm can be applied to partially connected graphs.
\end{itemize}

\section{Summary of the Chapter and Concluding Remarks}

In this chapter, we have introduced a new family of algorithms, called Shrinking Convex Hulls based on the interesting property of non-faulty nodes. We have proposed two algorithms SCH-CMN and SCH-CBN for Malicious and Byzantine complete networks, respectively. We have derived the required condition for success of the algorithms. The numerical examples have been proposed to evaluate the performance of the algorithm as well.

 While several other numerical examples can be examined,
we believe that the results presented above verify the feasibility
and superior performance of the SCH algorithms in complete networks in the presence of any number of Malicious and Byzantine nodes.
Hence, the proposed algorithms are deemed to be robust enough to be applied in critical fields where the probability of nodes failure is high or security is a concern.


\chapter{CONCLUSIONS}

In this thesis, the problem of achieving approximate Byzantine consensus in faulty synchronous and asynchronous networks is examined. We have proposed a novel MSR algorithm and shown that the topological condition required for the success of the algorithm is more relaxed in asynchronous networks with delay on communication paths compared to the previous results. Furthermore, it is proved that the synchronicity of the network and presence of delay on communication paths do not affect this condition. This result is in contrary to the results appeared in the literature. We have also extended our results to the case of time-varying synchronous and asynchronous networks and proved the success of the algorithm there. 

In Chapter 4, using matrix representation, we have determined the convergence rate and time of the proposed MSR algorithm and extended the results to time-varying networks. Moreover, the existence of a common Lyapunov function has been assessed for time-varying networks. Finally, a new family of algorithms, referred to as Shrinking Convex Hulls algorithms for Byzantine failure and a more restrictive but commonplace type of Byzantine failure known as Malicious failure has been presented in Chapter 5.

Our results not only extend the previous results in the literature but some of them can be considered as novel solutions to the problem of achieving approximate Byzantine consensus in faulty networks. 

Future potential researches related to this thesis can be itemized as follows:
\begin{itemize}
\item Designing fast MSR algorithms by selecting the averaging weights appropriately.
\item Designing SCH algorithms that can be applied to partially connected networks. 
\item Analysis of SCH algorithms in asynchronous networks and the presence of delay on communication paths.
\item Examining the behavior of Byzantine nodes and their impact on the overall dynamics of networks, so that designing new fault-tolerant algorithms without a priori knowledge on the maximum number of faulty nodes reduces to an easier problem.
\item Applying current results to real life applications such as multi-agent coordination, flocking and distributed estimation.
\item In all of the relevant results that appeared in the literature, node dynamics are considered to be first order. The analysis of the proposed algorithms in networks where each agent has non-linear uncertain dynamics in the presence of disturbances and communication delay can be considered as an another interesting potential future work.
\end{itemize}

%\appendix      % Starts appendices
%\chapter{TITLE OF THE FIRST APPENDIX}
%The appendices start here.

\bibliography{prref}{}
\bibliographystyle{unsrt}
%\begin{thebibliography}{9}
%\bibitem{label} References in the order they are mentioned in the text.
%\end{thebibliography}
%
% You can also try harvardbibliography, bibnotcited and
% harvardbibnotcited environments for other types of bibliographical
% lists.
%
\end{document}
