\section{Introduction}

	\subsection{Theoretical Background}

		Deterministic synchronous consensus has conceptual significance for the purposes of atomicity of committed distributed database transactions \cite{MohanStrongFink1985}
		\cite{HectorGM_EtAl1986}.
		It is impossible with a large fraction of all communication links being faulty \cite{JimGray78}.
		With all links being correct and process faults up to a fraction of all processes, it was solved with an algorithm where the decision making takes as input a vector, having an element for each process, loaded with values received from all processes
		\cite{PeaseShostakLamport80}
		\cite{LamportShostakPease82}. Under the same limit of tolerated faulty processes, it was also solved with a small fraction of all one-way links being faulty \cite{Dolev1981}. Aspects of synchronous consensus under simultaneous process and link failures were studied and solved in various contexts and scenarios
		\cite{MeyerPradhan1991}
		\cite{Hin-SingSiuEtAl1998}
		\cite{Schmid2001}
		\cite{SchmidEtAl2002}
		\cite{SantoroEtAl2007}
		\cite{SchmidEtAl2009}
		\cite{BielyEtAl2011}.
		Yet none of these works considers possible communication asynchrony.

		Consensus cannot be solved with a single unannounced failure of a process under \textit{full asynchrony} of processes, communication, and message ordering \cite{FLP_result} and also under full asynchrony of either processes or communication \cite{DolevDworkStockm1987}. Yet the needs of practice compel more attention to communication that is neither fully asynchronous nor fully synchronous. Its name \textit{partial synchrony} \cite{DworkLynchStockm1988} reflects the reality where intervals of full synchrony with unknown duration are followed by intervals of infringed full synchrony. First dealing with it was under the model of \textit{eventual synchrony} \cite{DworkLynchStockm1988}, meaning eventual \textit{in time} synchrony. This model stoically accepts the inevitability of intervals with asynchrony and allows termination only during large enough intervals of full synchrony.
		\cite{DuttaGuerraoui_2002}
		\cite{Alistarh_2008}.

		Handling asynchrony in a proactive manner makes more sense. One, and so far the most popular, way of doing that is to give up the reliance on ability of correct processes to obtain coherent view of the system state for computation of consensus value and replace it with reliance on a leader to propose the value \cite{CastroLiskov2002PBFT}. This approach is a tradeoff where vulnerability to stop-fail or Byzantine faults \cite{LamportShostakPease82} of the leader replaces the vulnerability to communication asynchrony. A Byzantine-faulty leader can delay consensus without revealing itself. Hence, with this way of proactive handling of asynchrony, as well as with the passive waiting for its disappearance, consensus is time vulnerable. These outcomes led to conjecture of impossibility to ensure simultaneous safety and liveness of consensus systems under partial synchrony \cite{GilbertLynch_2012}. Leaderless consensus under partial synchrony is considered theoretically possible \cite{BoranSchiper_2010}. Yet at present all deterministic algorithms that solve Byzantine consensus over communication medium susceptible to asynchrony are leader-based
		\cite{Abraham_EtAl_2020}
		\cite{Buchman_EtAl_2018}
		\cite{Baudet_EtAl_2020}
		\cite{Naor_EtAl_2019}
		\cite{Naor_Keidar_2020}
		\cite{Bravo_EtAl_2020}
		\cite{Stathakopoulou_EtAl_2019},
		hence time-vulnerable.

		\textbf{Definition 1} (\textit{Leaderless Consensus Algorithm}): Every process, from a quorum of correct processes with atomically consistent \cite{Herlihy_Wing_1990} views of system's state, proposes the same value for consensus.

		Consensus is key for ensured atomic operations across database management systems \cite{Gray_lamport}. These systems implement and use local transactions for consistency of operations and integrity of local data. Distributed transactions across these systems aim the same outcome and also by using local transactions, yet executed under external coordination. It involves use of a protocol from a family of distributed commit protocols
		\cite{JimGray78}
		\cite{BruceLindsay79}
		\cite{LampsonSturgis76},
		known for susceptibility to blocking
		\cite{BernsteinHadzilacosGoodman}
		\cite{WeikumVossen}
		and/or possibility to leave a database system participating in a distributed transaction in inconsistent state.

		\textbf{Definition 2} (\textit{Decentralized Database System}): Data replicated on multiple database management system peers in different trust domains and modified with decisions made by quorum of peers.

		Decentralized database systems solve half of the problem
		solved with distributed transactions – the stretch over distance – with global replication of locally executed transactions. These solutions ensure atomic (linearizable)
		\cite{Herlihy_Wing_1990} consistency across local systems' data with state machine replication
		\cite{Lamport_StateMachine}
		\cite{Schneider_1990}
		\cite{Lampson_1996}.
		Users can safely transact across continents, but only within a decentralized database silos. Solving the second half requires non-blocking transactions across the boundaries of decentralized database systems.

		For the duration of a distributed transaction, all participants performing a role in it (the transacting parties and the coordinator) operate as a single system. Its partitioning, or spoiled liveness of a participant, normally spoils its liveness and may compromise its safety, regardless of non-compromised safety of all participants, and the transaction cannot fulfill its purpose to ensure consistent outcome. Hence, distributed transaction system's prerequisites for safety are: 1) non-partitioning; and 2) liveness and safety of all participants. Further on in the paper we elaborate on and present a way to tame the root cause for partitioning and spoiled liveness.

	\subsection{Problem Formulation}

		Root cause for the present inability of deterministic Byzantine consensus systems to operate with ensured safety and bounded liveness under partial synchrony \textbf{is} the perceived impossibility for bounded delivery during incomplete communication synchrony.

	\subsection{Motivation}

		Possibility for deterministic Byzantine consensus systems with ensured safety and bounded liveness in partial synchrony would make feasible distributed transactions between decentralized database systems to operate with consistency resilient to:

		- Partitioning of the distributed transaction system; or

		- Fraudulently 'lost' liveness by one participant.

		\subsection{Solution Brief}
		A digitally signed \cite{RivestShamirAdleman78} message proves its authenticity to anyone with access to signing party’s public key. So, it might be relayed multiple times before reaching its final destination, in effect as if received directly from the sender. The key idea is to circumvent faulty and/or asynchronous links with epidemic dissemination \cite{BirmanEtAl1999} of messages and attain performance of a system with fault-free and asynchrony-free links. The goal is all correct processes to obtain a coherent view of the system state within a bounded time and establish consensus with no need of leader. From engineering perspective the solution is a trade-off: giving up the max throughput and efficient scalability in exchange for ensured bounded liveness.

	\subsection{Similar Works}

		This solution exhibits a major distinction from all previous works. It circumvents asynchronous links with bounded delivery over the links that operate synchronously. No known concept for delivery over a fraction of links considers links asynchrony or tolerates a non-negligible amount of it. Similarly, no known gossip-based concept or algorithm is concerned with bounded delivery.

		\textbf{Synchronous Consensus Over a Fraction of Links}

		Siu \textit{et al} \cite{Hin-SingSiuEtAl1998} presents a concept for fault-tolerant virtual channels in a synchronous deterministic Byzantine consensus system, where processes and links can fail independently and simultaneously. It ensures reliable delivery for the purposes of synchronous consensus over a fraction of links via circumvention of faulty link.
		This concept does not consider asynchrony of links.

		Aguilera \textit{et al} \cite{AguileraEtAl2003} \cite{AguileraEtAl2004} demonstrates a case of solved synchronous deterministic Byzantine consensus with a small fraction of all links operating synchronously. It is rather an exception from the normal distribution of asynchrony – one correct process having all inbound and outbound links synchronous. The number of permutations with such outcome shows this case's negligibly small probability.

		\textbf{Consensus via Gossip-based Reliable Multicast}

		In a distributed system where every process knows every other, the algorithm of Birman \textit{et al} \cite{BirmanEtAl1999} uses gossips, a.k.a. epidemic dissemination of messages, to deliver to all recipients, even if the sender fails before sending to all. The algorithm tolerates process crash failures and a bounded number of soft failures of links, such as buffer overflown. The algorithm does not consider Byzantine failures, asynchrony of links, or bounded delivery.

		In a distributed system where it is impractical every process to know every other, Eugster \textit{et al} \cite{EugsterEtAl2004} ensures probabilistic message delivery by gossiping with randomly selected partners. This work does not consider Byzantine-faulty processes or bounded delivery during asynchrony of some links. With the same type of distributed system, Guerraoui \textit{et al} \cite{GuerraouiEtAl2019} goes further to ensure the same as \cite{EugsterEtAl2004} under presence of Byzantine-faulty processes. Yet this work also does not consider possible asynchrony of links or bounded delivery under Byzantine omissions / delays.

	\subsection{Contribution}

		This paper contributes on the subject matter of consensus in partial synchrony:

		1. The algorithm for synchronous deterministic consensus with highest known tolerance to communication asynchrony;

		2. The first leaderless consensus algorithm over a communication medium susceptible to asynchrony and faults;

		3. Proof of possibility for deterministic Byzantine consensus systems to operate with ensured safety and bounded liveness.

	\subsection{Content}
		The rest of the paper is structured as follows: Section 2 contains thorough formal presentation of the concept. Section 3 presents the system model of distributed computing. Section 4 presents the algorithm. Section 5 proves the claims of this paper. Section 6 summarizes the results. Section 7 concludes the paper. Appendix shows assessment of tolerance with simulation and regression analysis.

	\section{The Concept}

		A digitally signed \cite{RivestShamirAdleman78} message might be relayed multiple times before reaching its final destination, in effect as if received directly from the sender. Thus, in spite of faults and/or asynchrony of some links, a message might reach all recipients via \textit{indirect channels} – virtual aggregations of multi-hop indirect delivery paths.

		\subsection{Direct Channels}

		Distributed consensus system $S$ of $N$ processes $(N \geq 3)$ has a full set $C$ of $N*(N-1)$ direct channels $c_{pq}$ $(1 \leq p \leq N, 1 \leq q \leq N, p \neq q)$. Channel $c_{pq}$ represents a one-way link for delivery from process $p$ to process $q$. Channel value 1 denotes \textit{correct and synchronous} link. Value 0 denotes \textit{\textit{faulty or asynchronous}}. Matrix $C$ represents the full set $C$ and also $N$ values representing $c_{pq}$ $(1 \leq p \leq N, 1 \leq q \leq N, p = q)$, i.e. a link of every process to itself, always with value 1:

		\begin{equation}
			\label{eq:1}
			C = \begin{Bmatrix}
				c_{11} & c_{12} & \dots & c_{1N} \\
				c_{21} & c_{22} & \dots & c_{2N} \\
				\vdots & \\
				c_{N1} & c_{N2} & \dots & c_{NN}
			\end{Bmatrix}
			\tag{1}
		\end{equation}

		\subsection{Two-hop Indirect Delivery Paths}

		System $S$ has also a full set $C'$ of \textit{two-hop indirect} delivery paths comprising $N*(N-1)*(N-2)$   individual paths, as every direct path has $(N-2)$ two-hop alternatives. A message from process $p$ to process $q$ can be delivered with two hops, the first hop from $p$ to process $r$ and the second hop from process $r$ to $q$. Indirect delivery over two links with bounded delivery is longer but still bounded. A \textit{two-hop indirect} delivery path is denoted in two ways:

		- $c'_{pqr} (1 \leq p \leq N, 1 \leq q \leq N, 1 \leq r \leq N, p \neq q,  r \neq p,  r \neq q )$, indicating delivery from process $p$ to process $q$ via process $r$; or

		- $c'_{pq}$, indicating delivery over any of the \textit{two-hop indirect} delivery paths from process $p$ to process $q$ represented by a vector of $(N-2$) elements, each representing a vector of 2 elements: $c_{pr}$ and $c_{rq}$.

		Value of $c'_{pqr}$ is 1 if both $c_{pr}$ and $c_{rq}$ have value 1. Value of $c'_{pq}$ is 1 if among the existing $(N-2)$ indirect delivery paths there exists a path where both $c_{pr}$ and $c_{rq}$ have value 1.

		\textbf{Formal}

		Matrix $C'$ represents a full set of two-hop indirect delivery paths:
		\begin{subequations}
			\begin{equation}
				\label{eq:2}
				C' = \begin{Bmatrix}
					c'_{11} & c'_{12} & \dots & c'_{1N} \\
					c'_{21} & c'_{22} & \dots & c'_{2N} \\
					\vdots & \\
					c'_{N1} & c'_{N2} & \dots & c'_{NN}
				\end{Bmatrix}
				\tag{2}
			\end{equation}
			where value of $c'_{pq} (p = q)$ is always 0 as it has no meaning and where value of $c'_{pq} (p \neq q)$ is defined by vector $C'_{pq}$:
			\begin{equation}
				\label{eq:2.1}
				C'_{pq} =
				\begin{Bmatrix}
					k'_{1} & k'_{2} & \dots & k'_{N-2}
				\end{Bmatrix}
				\tag{2.1}
			\end{equation}
			comprising all two-hop paths from $p$ to $q$, and computed as:
			\begin{equation}
				\label{eq:2.2}
				c'_{pq}=k'_{1} \lor k'_{2}\lor \dots \lor k'_{N-2}
				\tag{2.2}
			\end{equation}

			where $k'_{i} = c'_{pqr}$, and value of $c'_{pqr}$ is defined by vector $C'_{pqr}$:
			\begin{equation}
				\label{eq:2.3}
				C'_{pqr} =
				\begin{Bmatrix}
					k_{1} & k_{2}
				\end{Bmatrix}
				\tag{2.3}
			\end{equation}
			specifying the links participating in the path, and computed as:
			\begin{equation}
				\label{eq:2.4}
				c'_{pqr} = k_{1} \land k_{2}
				\tag{2.4}
			\end{equation}

		\end{subequations}

		\subsection{Three-hop Indirect Delivery Paths}

		System $S$ has as well a full set $C''$ of \textit{three-hop indirect} delivery paths comprising $N*(N-1)*(N-2)*(N-3)$ paths as every \textit{two-hop indirect} path has $(N-3)$ three-hop alternatives. A message from process $p$ to process $q$ can be delivered with three hops: the first from $p$ to process $r$, the second from $r$ to process $s$, and the third from process $s$ to $q$. A \textit{three-hop indirect} delivery path is denoted also in two different ways:

		- $c''_{pqrs} (1 \leq p \leq N, 1 \leq q \leq N, 1 \leq r \leq N, 1 \leq s \leq N, p \neq q,  r \neq p,  r \neq q, s \neq p, s \neq q, s \neq r )$, indicating delivery from $p$ to $q$ via processes $r$ and $s$; or

		- $c''_{pq}$, indicating any of the \textit{three-hop indirect} delivery paths from $p$ to $q$, represented by a matrix of $(N-2)*(N-2)$ elements, each representing a vector of 3 elements: $c_{pr}$, $c_{rs}$, and $c_{sq}$.

		Value of $c''_{pqrs}$ is 1 if each of its constituent elements $c_{pr}$, $c_{rs}$, and $c_{sq}$ has value 1. Value of $c''_{pq}$ is 1 if among the existing $(N-2)*(N-2)$ indirect delivery paths there exists a path where each of its constituent elements $c_{pr}$, $c_{rs}$, and $c_{sq}$ has value 1.

		\textbf{Formal}

		Matrix $C''$ represents full set of three-hop indirect delivery paths:
		\begin{subequations}
			\begin{equation}
				\label{eq:3}
				C'' =
				\begin{Bmatrix}
					c''_{11} & c''_{12} & \dots & c''_{1N} \\
					c''_{21} & c''_{22} & \dots & c''_{2N} \\
					\vdots & \\
					c''_{N1} & c''_{N2} & \dots & c''_{NN}
				\end{Bmatrix}
				\tag{3}
			\end{equation}

			where the value of $c''_{pq} (p = q)$ is always 0 as it has no meaning and the value of $c''_{pq} (p \neq q)$ is defined by matrix $C''_{pq}$, where $M=N-2$:

			\begin{equation}
				\label{eq:3.1}
				C''_{pq} =
				\begin{Bmatrix}
					k''_{11} & k''_{22} & \dots & k''_{1M} \\
					k''_{12} & k''_{22} & \dots & k''_{2M} \\
					\vdots & \\
					k''_{M1} & k''_{M2} & \dots & k''_{MM} \\
				\end{Bmatrix}
				\tag{3.1}
			\end{equation}

			comprising all $M*M$ 3-hop paths from $p$ to $q$, and computed as:
			\begin{align}
				\label{eq:3.2}
				\tag{3.2}
				c''_{pq} =	&k''_{11} \lor k''_{12} \lor \dots \lor k''_{1M} \lor \nonumber \\
				&k''_{21} \lor k''_{22} \lor \dots \lor k''_{2M} \lor \nonumber \\
				&\vdots \nonumber \\
				&k''_{M1} \lor k''_{M2} \lor \dots \lor k''_{MM} \nonumber
			\end{align}

			where value of $k''_{ij} = c''_{pqrs}(r=s)$ is 0 as it has no meaning and where value of $k''_{ij} = c''_{pqrs}(r\neq s)$ is defined by vector $C''_{pqrs}$:
			\begin{equation}
				\label{eq:3.3}
				\tag{3.3}
				C''_{pqrs} =
				\begin{Bmatrix}
					k_{1} & k_{2} & k_{3}
				\end{Bmatrix}
			\end{equation}
			specifying the links participating in the path, and computed as:
			\begin{equation}
				\label{eq:3.4}
				\tag{3.4}
				c''_{pqrs} = k_{1} \land k_{2} \land k_{3}
			\end{equation}
		\end{subequations}
		For instance, value of $c''_{1234} = c_{13} \land c_{34} \land c_{42}$.

		\subsection{Subsets of Channels}

		At any point of time, only a fraction of links in $S$ may be correct and operate synchronously. Yet, $S$ may have $D$ \textit{delivery} subsets $Cd_{i} (1 \leq i \leq D)$, where the channels of every subset $Cd_{i}$ can deliver all messages, directly or indirectly, within the synchrony bound. Given that all $N$ processes in  $S$ are correct, a subset of $C$ \eqref{eq:1} is a \textit{delivery} one if it can deliver a message from a process $p$ to any other process $q$ over $c_{pq}$ $(1 \leq p \leq N, 1 \leq q \leq N, p \neq q)$ \eqref{eq:1} or over $c'_{pq}$ \eqref{eq:2} or over $c''_{pq}$ \eqref{eq:3} of the subset. A \textit{non-delivery} subset is one where no $c_{pq}$ and no $c'_{pq}$ and no $c''_{pq}$ can deliver the message. Existence of at least one \textit{delivery} subset $Cd_{i}$ is the necessary and sufficient condition for delivery of all messages. Hence, the delivery of all messages can be prevented only by a number of faulty direct channels that renders all subsets \textit{non-delivery}.

		\subsection{Effect of Faulty Processes}

		In a consensus system where any third party can verify authenticity of messages, a Byzantine-faulty process may deceive about its value, but may not tamper any message from other process and send it as authentic \cite{PeaseShostakLamport80}. Its options are limited to failure to send a protocol message to some or all processes, or to deliberately delay its sending \cite{DolevStrong1983}. Hence in a system that relies on indirect delivery, a Byzantine-faulty process can do no more harm than a stop-failed process and consensus safety requires $N=2F+1$ processes, where $F$ is the number of tolerated stop-failed and/or Byzantine-faulty processes.
		The indirect delivery depends on strict execution of an algorithm. A process can spoil an indirect path that relies on its participation. Thus, a faulty process may convert some of the $D$ \textit{delivery} subsets into \textit{non-delivery} subsets. Consequently, system $S$ may have $A$ subsets of channels $Ca_{i} (1 \leq i \leq A)$ called \textit{agreement} subsets, where the channels in every subset $Ca_{i}$ can deliver all messages necessary for reaching an agreement, directly or indirectly. \textit{Agreement} subset of $C$ \eqref{eq:1} is a subset that can synchronously deliver a message from any process $p$ of a group of at least $F+1$ correct processes to any other process $q$ of the same group over $c_{pq}$ $(1 \leq p \leq N, 1 \leq q \leq N, p \neq q)$ \eqref{eq:1} or over $c'_{pq}$ \eqref{eq:2} or over $c''_{pq}$ \eqref{eq:3} of the subset. A \textit{non-agreement} subset is one where neither $c_{pq}$, $c'_{pq}$, or $c''_{pq}$ of the subset can deliver the message synchronously.

		\subsection{Virtual Channels for Indirect Delivery}

		A set of \textit{Virtual indirect channels} is a construction of links and processes interacting according to a deterministic protocol. Purpose of an indirect channel is to circumvent a faulty or asynchronous link via indirect synchronous delivery. A set of \textit{2-hop indirect channels} operates with one process that helps deliver with two hops. The helper multicasts a message received from sender to $(N-2)$ recipients, thus enacting $(N-2)$ channels; A set of \textit{3-hop indirect channels} operates with $1 +(N-2)$ helper processes. The first helper enacts $(N-2)$ \textit{2-hop indirect channels}. The group of $(N-2)$ second helpers enacts the third hop where each of the second helpers multicasts the received message to $(N-3)$ recipients, on its first receiving.

		\section{System Model}
		Critical for the concept is to minimize the chance that all inbound links to a process can together fail or became asynchronous. Failure of a link is typically due to network card's overflown receive buffer. Avoiding it requires hardware with capacity for overlapped receiving of messages with max size from all peers. So, an avalanche of faulty links triggered by a single link fault can be ruled out.

		Asynchrony of links is beyond Internet users' ability to tame it. Multiple inbound links to a process inevitably share a router that may become overloaded. Fortunately, TCP congestion avoidance
		\cite{Jacobson_Karels_1988} algorithms use
		\textit{random early detection}
		\cite{Jacobson1988}
		\cite{FloydJacobson1993}
		\cite{JacobsonEtAl1999} to halve the TCP window of individual flows one-by-one when needed, thereby ruling out simultaneous switch to unbounded delivery.

	\subsection{Model Assumptions}

		\textbf{Computation}:

		- \textit{Deterministic processes}. Processes are implemented as computer code with state-defined deterministic execution on pre-selected CPU cores to run process threads.

		- \textit{Deterministic protocol}. Processes communicate with exchange of messages, which follows a deterministic protocol.

		\textbf{Communication} and \textbf{messages}:

		- \textit{Synchronous with limited exceptions}. Messages are normally delivered within a known bounded amount of time.

		- \textit{Signed}. Messages are signed with third party verifiable digital signatures, i.e. able to prove its authenticity to every process.

		\textbf{Processors} and \textbf{processes}:

		- \textit{Synchronous}. Processes execute on CPUs with a fixed upper bound on how faster one complete a processing cycle than another and on the difference in cache size and cache latencies.

		- \textit{Synchronized}. Processes start a consensus round with a max lag bound to less than $RTTB/2$ (round trip transmission bound), which is $MDTB$ (message delivery time bound).

		- \textit{No clocks drift}. Synchronized processes stay synchronized via periodic re-synchronization of clocks.

		- \textit{Known public keys}. Every process knows the public key of every other process' private key for signature.

		\textbf{Communication failures and asynchrony}:

		- \textit{Uncorrelated failures}. A fault in one link is independent from a fault in another link, i.e. a failure in an inbound link cannot trigger an avalanche of inbound link failures.

		- \textit{Uncorrelated asynchrony}. Asynchronous operation of one link is independent from asynchronous operation of another link, i.e. an asynchronous inbound link cannot trigger an avalanche of asynchronous inbound links.

		\textbf{ Process failures}:

		-\textit{ Stop-Fail}. Processes execute correctly, but can stop at any time and once stopped, cannot restart.

		- \textit{Bizantine}. Arbitrary behavior expressed as:

		- (1) \textit{Omission} to send to all recipients.

		- (2) \textit{Delay} before sending to one or more recipients.

		- (2) \textit{Deceit} in regard to message content.

	\subsection{The System}
		The model considers a consensus system $S$ comprising $N$ deterministic \textit{processes} $(N \geq 3, N \geq 2F+1)$, where $F$ is the tolerated number of faulty processes. Each process $P$ is uniquely identified within $S$ with a system index $I (1 \leq I \leq N)$. The processes are connected by point-to-point one-way \textit{links}. Every pair of processes is connected with a pair of links $c_{IsIr}$, where $Is$ identifies the sender process and $Ir$ identifies the receiver process. Existence of links where $Is=Ir$, i.e. from every process to itself, is assumed for simpler presentation.

		Every process $P$ has special memory locations: \textit{input register} $R^{In}$ and \textit{output register} $R^{Out}$. Register $R^{In}$ can contain up to $x$ bytes in size. Register $R^{Out}$ is a vector of $N$ elements $R^{In}$:
		\begin{subequations}
		\begin{equation}
		\label{eq:4}
		\tag{4}
		R^{Out} =
		\begin{Bmatrix}
			R^{In}_{1} & R^{In}_{2} & \dots & R^{In}_{N}
		\end{Bmatrix}
		\end{equation}

		Every process $P$ also has an unbound amount of internal storage and an allocated in it vector $E$ of $N$ \textit{extended} digital signatures:
		\begin{equation}
		\label{eq:4.1}
		\tag{4.1}
		E =
		\begin{Bmatrix}
			e_{1} & e_{2} & \dots & e_{N}
		\end{Bmatrix}
		\end{equation}
		\end{subequations}
		where $e_{i}$ is extended digital signature over $ R^{In}_{i} $ in form of a tuple of 2 elements: 1) $ h_{i} $ is output of execution of the $ Hash $ function used in $S$ over $ R^{In}_{i} $; and 2) $ s_{i} $ is the signature of process $ P_{i} $ over $ h_{i} $.

		The values in $R^{In}$, $R^{Out}$, and the internal storage of the processes of $S$ define the internal state of $S$. Initial states prescribe fixed starting value for all; in particular $R^{In}$ and $R^{Out}$ start with value 0 of every byte. States in which $R^{Out}$ contains $\geq ( F + 1 )$ elements with values $\neq 0$ are distinguished as decision states.

		Each process $P$ acts deterministically according to a transition function $\Phi$, which cannot change the value of $R^{Out}$ once the process has reached a decision state; i.e., $R^{Out}$ is 'write-once'. System $S$ is specified by the function $\Phi$ and the values in $R^{In}$ of every process.

		Processes communicate with signed messages. A \textit{message} is tuple $(T, Is, Id, Io, m, Do)$, where $ T $ is a constant specifying message type, $ Is $ is index of the source process, $ Id $ is index of the destination process, $ Io $ is index of the originator process, $ m $ is 'message value' from a fixed universe $ M $, and $ Do $ is digital signature of the originator process over $ m $. Where $Io \neq Is$, this indicates that the message $ m $ sent by process $ P_{Is} $ contains the message and the digital signature that $ P_{Is} $ has received from $ P_{Io} $.

		Communication within a consensus round happens in two phases. During Phase One each process $ P_{Is} $ transmits to every process $ P_{Id} (1 \leq Id \leq N, Id \neq Is)$, the value in its input register $ R^{In}_{Is}$ and its signature over the value in $ R^{In}_{Is} $. During Phase Two each process $ P_{Is} $ transmits the content of its $E_{Is}$ \eqref{eq:4.1} and its signature over $E_{Is}$ to every process $ P_{Id} (1 \leq Id \leq N, Id \neq Ips)$.

		At the Phase One beginning, state of $S$ is defined by vector V1:
		\begin{subequations}
		\begin{equation}
		\label{eq:5}
		\tag{5}
		V1 =
		\begin{Bmatrix}
			v1_{1} & v1_{2} & \dots & v1_{N}
		\end{Bmatrix}
		\end{equation}

		An element $v1_{i} (1 \leq i \leq N)$ contains the value $R^{In}_{i}$ of process $P_{i}$ and its signature $s_{i}$ over $R^{In}_{i}$. During Phase One each process $P_{i}$ sends $v1_{i}$ to every process $P_{j}(1 \leq j \leq N, j \neq i)$ over $c_{ij}$ \eqref{eq:1}.

		Matrix $D1$ presents what was delivered by $S$ during Phase One. An element $d1_{ij}$ is the value of $v1_{i}$ as delivered over $c_{ij}$, i.e. where value of  $c_{ij}$ is $0$, indicating a faulty direct channel, the delivered value $d1_{ij}$ is $0$; otherwise $d1_{ij} = v1_{i}$:
		\begin{equation}
			\label{eq:5.1}
			\tag{5.1}
		D1 = \begin{Bmatrix}
			d1_{11} & d1_{12} & \dots & d1_{1N} \\
			d1_{21} & d1_{22} & \dots & d1_{2N} \\
			\vdots & \\
			d1_{N1} & d1_{N2} & \dots & d1_{NN} \\
		\end{Bmatrix}
		\end{equation}

 		On receiving $d1_{ij} \neq 0$ from process $P_{i}$, process $P_{j}$ executes the system's \textit{ Hash} function over $R^{In}_{i}$ component of $d1_{ij}$, writes the outcome as $h_{i}$ component of element $e_{i}$ of its vector $E_{j}$, uses the signature $s_{i}$ component of $d1_{ij}$ to verify the signature, writes $s_{i}$ as the $s_{i}$ component of element $e_{i}$ of its vector $E_{j}$, and in case of correctly verified signature writes $R^{In}_{i}$ in its vector $R^{Out}{j}$ \eqref{eq:4}.

		On completion of Phase One, every process $P_{j}$ has formed a vector of extended digital signatures $E_{j}$:
		\begin{equation}
			\label{eq:5.2}
			\tag{5.2}
		E_{j} =
		\begin{Bmatrix}
			e_{1j} & e_{2j} & \dots & e_{Nj}
		\end{Bmatrix}
		\end{equation}
		from  vector $D1_{j}$:
		\begin{equation}
			\label{eq:5.3}
			\tag{5.3}
		D1_{j} =
		\begin{Bmatrix}
			d1_{1j} \\
			d1_{2j} \\
			\vdots  \\
			d1_{Nj} \\
		\end{Bmatrix}
		\end{equation}
		\end{subequations}
		Next, $P_{j}$ forms $v2_{j}$ containing the vector of extended digital signatures $E_{j}$ and a digital signature of $P_{j}$ over the content of vector $E_{j}$.

		At the Phase Two beginning, state of $S$ is defined by vector V2:
		\begin{subequations}
		\begin{equation}
			\label{eq:6}
			\tag{6}
		V2 =
		\begin{Bmatrix}
			v2_{1} & v2_{2} & \dots & v2_{N}
		\end{Bmatrix}
		\end{equation}

		During Phase Two each process $P_{i}$ sends $v2_{i}$ to every other process $P_{j}(1 \leq j \leq N, j \neq i)$ over $c_{ij}$. Matrix $D2$ presents the outcome of Phase Two. An element $d2_{ij}$ is $v2_{i}$ as delivered over $c_{ij}$:
		\begin{equation}
		\label{eq:6.1}
		\tag{6.1}
		D2 = \begin{Bmatrix}
			d2_{11} & d2_{12} & \dots & d2_{1N} \\
			d2_{21} & d2_{22} & \dots & d2_{2N} \\
			\vdots & \\
			d2_{N1} & d2_{N2} & \dots & d2_{NN} \\
		\end{Bmatrix}
		\end{equation}
		\end{subequations}

		In case of no process or link failures, all $d2_{ij}$ contain the same value. Process $P_{j}$
		having received $(N-1)$ vectors $d2_{ij}$ that have the same value as the value $d2_{jj}$ that $P_{j}$ received from itself, knows that every other process $P_{i}$ has received exactly the same values. So $P_{j}$ obtains the value upon which an agreement has been reached with execution of a pre-defined deterministic function that takes as input the content of vector $R^{Out}_{j}$.

	\subsection{Handling Faults and Asynchrony}

		The model assumes signed messages able to prove its authenticity to any process of the system. So, a Byzantine process may deceive about its value, but may not alter values received from other processes and send the altered values without revealing itself as malicious \cite{PeaseShostakLamport80}. Thus the model limits the undetected behavior of Byzantine processes to just failure to send a protocol message to some or all processes or deliberately delay the sending \cite{DolevStrong1983}.

		\textbf{Handling Byzantine Deceit}

		During Phase Two the consensus algorithm exchanges extended signatures only. The model has to ensure that Byzantine consensus can still be solved with $N=2F+1$ processes. A Byzantine-faulty process $P_{i}$  may send different versions of $v1_{i}$ to $P_{j}$ and  $P_{k}$ $(1 \leq j \leq N, 1 \leq k \leq N, j \neq i, k \neq i, j \neq k)$, thus deceiving about own value. If $R^{In}_{i}$ and $s_{i}$ do not match, $v1_{i}$ is ignored; otherwise $P_{j}$ includes $e_{i}$ in vector $E_{j}$ and $P_{k}$ includes $e_{i}$ in vector $E_{k}$.

		On completion of Phase Two, if vectors $E_{j}$ and $E_{k}$ distributed to all processes contain different versions of $e_{i}$, then $P_{i}$ reveals itself as Byzantine-faulty and all correct processes drop $R^{In}_{i}$ from the consensus vector $R^{Out}$. Sufficient is to verify that the different $h_{i}$ of each version is correctly signed with the different $s_{i}$ of its version. Hence system $S$ reveals the deceit and terminates consensus rounds with no need of more than $F+1$ correct processes.

		\textit{During Phase One}: A Byzantine-faulty process $P_{i}$ may send more than one value as its $R^{In}_{i}$ value during Phase One. These values may be correctly or incorrectly signed. Process $P_{i}$ is supposed to send value $v1_{i}$ to every process $P_{j} (1 \leq j \leq N, j \neq i)$ over $c_{ij}$. Yet the value $v1_{i}$ that process  $P_{i}$ sends is not the same to every $P_{j}$:
		\begin{subequations}
		\begin{equation}
		\label{eq:7.1}
		\tag{7.1}
		v1_{i} =
		\begin{Bmatrix}
			R^{In}_{i} & s_{i}
		\end{Bmatrix}
		\end{equation}

		Process $P_{i}$  may send different versions of $v1_{i}$ to $P_{j} (1 \leq j \leq N, j \neq i)$ and $P_{k} (1 \leq k \leq N, k \neq i, k \neq j)$. Processes $P_{j}$ and $P_{k}$ execute $ Hash $ function over $R^{In}_{i}$ to produce $h_{i}$ and verify correctness of the received signature $s_{i}$. If $R^{In}_{i}$ and $s_{i}$ do not match, $v1_{i}$ is ignored; otherwise $P_{j}$ includes $h_{i}$ and $s_{i}$ as element $e_{i}$ in vector $E_{j}$ and  $P_{k}$ includes $h_{i}$ and $s_{i}$ as element $e_{i}$ in vector $E_{k}$. During Phase Two, vectors $E_{j}$ and $E_{k}$ containing different versions of $h_{i}$  will be distributed to all processes, thereby revealing $P_{i}$ as Byzantine-faulty. So, all correct processes $P_{j} (1 \leq j \leq N, j \neq i)$ will drop $R^{In}_{i}$ from their vector $R^{Out}_{j}$.

		\textit{During Phase Two}: Process $P_{i}$ may deceive about value $v1_{j}$ it has received from process $P_{j} (1 \leq j \leq N, j \neq i)$ during Phase One. Value $v2_{i}$ process $P_{i}$ sends during Phase One contains $E_{i}$ and signature of $P_{i}$ over $E_{i}$:
		\begin{equation}
		\label{eq:7.2}
		\tag{7.2}
		E_{i} =
		\begin{Bmatrix}
			e_{1i} & e_{2i} & \dots & e_{Ni}
		\end{Bmatrix}
		\end{equation}
		\end{subequations}
		Yet the value $v2_{i}$ sent to at least one process $P_{k} (1 \leq k \leq N, k \neq i)$ contains at least one value $e_{ji}$ that does not reflect correctly the value $v1_{j}$ that $P_{i}$ has received from process $P_{j} (1 \leq j \leq N, j \neq i, j \neq k)$. This deceit cannot be successful: a $h_{j}$ incorrectly reflecting $R^{In}_{j}$ has no chance to match the signature $s_{j}$ of process $P_{j}$.

		Process $P_{i}$ may try to deceive about the value received from process $P_{k} (1 \leq k \leq N, k \neq i)$ by including a false $h_{k}$ in its vector $E_{i}$. However, $P_{i}$ cannot produce a false signature $s_{k}$ that matches with the false $h_{k}$. Matching signature can be produced only by process $P_{k}$. Whatever values $h_{k}$ and $s_{k}$ process $P_{i}$ sends, the non-matching between these values will be easily detected by the recipient processes. So, process $P_{i}$ cannot prevent consensus, but reveals itself as Byzantine-faulty.

		\textbf{Handling Link Failure or Asynchrony}

		Link failure is an arbitrary behavior of a one-way link $c_{ij}$ between two processes $P_{i} (1 \leq i \leq N)$ and $P_{j} (1 \leq j \leq N, j \neq i)$ that prevents correct transmission of messages from the sender process $P_{i}$ to the receiver process $P_{j}$. Asynchrony of the one-way link $c_{ij}$ is arbitrary behavior in regard to delivery time of the communication medium between processes $P_{i}$ and $P_{j}$. Link $c_{ij}$ is represented in matrix $C$ \eqref{eq:1} with value 1 if it operates correctly and synchronously. It has value 0 if it does not deliver within the synchrony bounds.

		The model does not distinguish faulty from asynchronous link and does not need to. It handles both with indirect delivery. It does not need the receiving end of a link to distinguish a faulty/asynchronous link from possible process failure on the sending end.

		The model prescribes that in addition to the protocol rules, a correct process $P_{i}(1 \leq i \leq N)$ must follow one more rule. On first receiving of a signed message $mP_{j}$, directly from the signatory  $P_{j} (1 \leq j \leq N, j \neq i)$ or indirectly, $P_{i}$ multicasts $mP_{j}$ to every $P_{k} (1 \leq k \leq N, k \neq i, k \neq j)$ with the signature of $P_{j}$ over $mP_{j}$.

		This rule ensures (where possible) that faulty or asynchronous links will be circumvented with 2-hop or 3-hop indirect delivery. It enacts attempts to deliver message  $mP_{j}$ via different 2-hop indirect channels \eqref{eq:2} and possible attempts to deliver  $mP_{j}$ via different 3-hop indirect channels \eqref{eq:3}.

 		\vspace{\baselineskip}
		\textbf{Stop-Failed Process}

		A stop-failed process is one that executes correctly but stops at any time and once stopped, cannot restart. A stop-failed process $P_{i} (1 \leq i \leq N)$ cannot send any $v1_{i}$ or $v2_{i}$ messages to any other process $P_{j} (1 \leq j \leq N, j \neq i)$ over $c_{ij}$ and cannot receive any $v1_{j}$ or $v2_{j}$ messages from any other process $P_{j}$ over $c_{ji}$. The effect of a stop-failed process $P_{i}$ on the functioning of system S is the same as:

		- Simultaneous failure/asynchrony of all links where $P_{i}$ is sender, represented by the entire row with index $i$ of matrix $C$ \eqref{eq:1}, i.e. every element $c_{ij} (1 \leq j \leq N)$ in matrix $C$ having value 0; and

		- Simultaneous failure/asynchrony of all links  where $P_{i}$ is receiver, represented by the entire column with index $i$ of matrix $C$ \eqref{eq:1}, i.e. every element  $c_{ji} (1 \leq j \leq N)$ in matrix $C$ having value 0.

		\textit{Note}: Process failure presented as link failures provides a common denominator for assessment of the combined effect of simultaneous process failures and link failures/asynchrony and the effect of processes' possible Byzantine behavior in its variety and scale.

		The model does not distinguish whether a missing message is caused by a process stop-failure or anything else. Yet, it takes into consideration that a stop-failed process spoils all 2-hop and 3-hop indirect channels that depend on its active participation. Stop-failed sender during multicast has the effect of Byzantine omission.

		System $S$ needs just $F+$1 correct processes to be able terminate consensus in spite of $F$ stop-failed processes, as a consequence of the eliminated chance for successful Byzantine deceit \cite{PeaseShostakLamport80}
		\cite{DolevStrong1983}.
		With this model, correctness of the above statement is subject to additional condition: As long as the $F$ stop-failed processes do not invalidate all indirect channels allowing a correct process to have two-way communication with the rest of the $F$ correct processes.

		\textbf{Handling Byzantine Omission}

		Every process $P_{i} (1 \leq i \leq N)$ is required by consensus protocol to send each protocol message to every other process $P_{j} (1 \leq j \leq N, j \neq i)$ over $c_{ij}$. A Byzantine-faulty $P_{i}$ may omit sending to $P_{j}$. Omission by $P_{i}$ to send to  $P_{j}$ over $c_{ij}$ has exactly the same effect on functioning of system $S$ as the event of failure of link $c_{ij}$ and is handled in the same way.

		Process $P_{i}$ can omit sending to any process $P_{j}$ without being detected. Sending to at least one process of a group of $F+1$ correct processes with two-way channels between themselves allows the model to tolerate its omissions. Omitted sending to all of the group of $F+1$ correct processes has the effect of a stop-failed process.

		\textbf{Handling Byzantine Delay}

		Every process $P_{i}(1 \leq i \leq N)$ is required by consensus protocol to send each protocol message to every process $P_{j} (1 \leq j \leq N, j \neq i)$ over $c_{ij}$ with no delay. A delayed sending by $P_{i}$ to a process $P_{j}$ has the same effect on functioning of consensus system $S$ as sending over asynchronous link, handled exactly as a Byzantine omission.

	\subsection{Correctness of Consensus}
		Consensus requires existence of a group $G$, which comprises  $\geq F+1$ correct processes communicating via direct or indirect channels with bounded delivery.

		\textbf{Correctness Conditions}

		\textit{Agreement}: Every two processes $P_{i}$ and $P_{j}$ from $G$ compute the same value for their output registers $R^{Out}_{i}$ and $R^{Out}_{j}$.

		\textit{Termination}: All processes in $G$ decide within 4 RTTB intervals.

	\section{The Algorithm}

	\subsection{Synchronization}
		The system model assumes synchronized processes
		\cite{HalpernEtAl1984}
		\cite{Lamport_EtAl_1984}
		\cite{Dolev_EtAl_1984}
		\cite{Lundelius_Lynch_1984}
		\cite{Schneider_1986},
		with max lag bounded to less than half RTTB (round trip transmission bound). Sufficient condition for ensuring the assumed max lag is every process to have access to a Time server with embedded GPS receiver utilizing atomic-clock synchronization systems
		\cite{DanaPenrod1990}
		\cite{AllanEtAl1997}
		\cite{MichaelLombardi2010}.
		The processes of a system with synchronized clocks need only to fix the start time of the first consensus round and then periodically re-synchronize the clocks. The last process joining the system broadcasts a signed message setting the start time. Every recipient of that message, on first direct or indirect receiving also broadcasts it together with its original signature.

	\subsection{Flexible Time-bound}
		Public networks like the Internet operate with fluctuating hourly workload over some backbone elements, causing large fluctuations of the normal delivery time. Hence, flexible time-bound for delivery is a precondition for efficiency in ensuring synchrony. The issue is not essential for this paper, so we only acknowledge it briefly.

		Backbone routers' congestion control algorithms use \textit{random early detection}
		\cite{Jacobson1988}
		\cite{FloydJacobson1993}
		\cite{JacobsonEtAl1999}
		to prevent buffers overflow by reducing transmission speed of individual flows, possibly multiple times below the maximum. This way, Transmission Control Protocol (TCP) allows routers to handle surges of traffic and avoid channels partitioning. Under partially synchronous communication and the consensus model of \textit{eventual synchrony}, execution might halt as a result of a randomly delayed synchronous flow, seen as asynchrony.

		One way of dealing with such random asynchrony is to switch to a larger time-bound for message delivery. Its outcome would be similar to that of routers operating with a fraction of their maximum throughput, yet being unable to eliminate the possibility for random asynchrony. More efficient is a feature similar to TCP congestion window. The consensus algorithm detects early signs of overloaded channels, capable to halt the consensus after further deterioration, and modifies the time-bound for delivery only when needed.

	\subsection{Handling Faulty/Asynchronous Links}

		The algorithm operates in a deterministic data-driven manner by responding to events from a pair of event categories in the sequence of appearing: expiry of time intervals and receiving peer messages.

		\lstset{language=C++,
				basicstyle=\footnotesize}
		\begin{lstlisting}[caption=Processing Timeout Events in C++]
void OnTimeout( BYTE Event )
{
switch(Event)
	{
case START1 :	// Start Phase One
	BroadcastMssgPhaseOne() ;
	break;
case START2 :	// Start Phase Two
	BroadcastMssgPhaseTwo() ;
	break;
	}
}
		\end{lstlisting}

		\vspace{\baselineskip}
		\vspace{\baselineskip}

		Listing 1 presents the algorithm's part that maintains synchronization between consensus rounds of process $P_{i}(1 \leq i \leq N)$ in system $S (N \geq 3, N \geq 2F+1)$ with the rest of processes $P_{j} (1 \leq j \leq N, j \neq i)$. Function OnTimeout() responds to 2 timeout events:

		- START1 prompts process $P_{i}$ to broadcast its own MSGPHASE1 message to all processes $P_{j} (1 \leq j \leq N, j \neq i)$.

		- START2 prompts process $P_{i}$ to broadcast its own MSGPHASE2 message to all processes $P_{j} (1 \leq j \leq N, j \neq i)$.

		\begin{lstlisting}[caption=Processing Received Messages in C++]
void OnRcvdMSSG( MSSG* pMSSG )
{
switch( pMSSG->m_Mssg_Type )
	{
case MSGPHASE1 : // Rcvd a Direct  Mssg Phase One
case RTRNSMTD1 : // Rcvd a Relayed Mssg Phase One
	if( HasMssgBeenRcvd( pMSSG ) break;
	ProcessMssgPhaseOne( pMSSG ) ;
	RetrnsmMssgPhaseOne( pMSSG ) ;
	break;
case MSGPHASE2 : // Rcvd a Direct  Mssg Phase Two
case RTRNSMTD2 : // Rcvd a Relayed Mssg Phase Two
	if( HasMssgBeenRcvd( pMSSG ) break;
	ProcessMssgPhaseTwo( pMSSG ) ;
	RetrnsmMssgPhaseTwo( pMSSG ) ;
	break;
	}
}
		\end{lstlisting}

		Listing 2 presents the algorithm's part that handles and responds the messages that process $P_{i}(1 \leq i \leq N)$ receives from the rest of processes $P_{j} (1 \leq j \leq N, j \neq i)$. Function OnRcvdMSSG() responds to 4 types of messages:

		- MSGPHASE1 is a message that process $P_{i}(1 \leq i \leq N)$ receives directly from every process $P_{j} (1 \leq j \leq N, j \neq i)$. On first receiving, directly or via RTRNSMTD1, $P_{i}$ verifies the signature, records the message in its internal storage, and multicasts it as RTRNSMTD1 message to every process $P_{k} (1 \leq k \leq N, k \neq i, k \neq j)$.

		- RTRNSMTD1 is a message signed by $P_{j} (1 \leq j \leq N, j \neq i)$ and received by $P_{i}$ sent by $P_{k} (1 \leq k \leq N, k \neq i, k \neq j)$ in response to MSGPHASE1 from  $P_{j}$.

		- MSGPHASE2 is a message that process $P_{i}(1 \leq i \leq N)$ receives directly from every process $P_{j} (1 \leq j \leq N, j \neq i)$. On first receiving, directly or via RTRNSMTD2, $P_{i}$ verifies the signature, records the message in its internal storage, and multicasts it as RTRNSMTD2 message to every process $P_{k} (1 \leq k \leq N, k \neq i, k \neq j)$.

		- RTRNSMTD2 is a message signed by $P_{j} (1 \leq j \leq N, j \neq i)$ and received by $P_{i}$ sent by $P_{k} (1 \leq k \leq N, k \neq i, k \neq j)$ in response to MSGPHASE2 from  $P_{j}$.

	\begin{figure}[h]
		\scalebox{0.22}
		{\includegraphics{Bounded_Communication_Over_Level-2_Channels.JPG}}
		\caption{Communication via 3-hop Indirect Channels}
	\end{figure}
	\subsection{Algorithm Illustration}

		Figure 1 is a diagram that illustrates the algorithm operations in a worst-case scenario. On the diagram, all processes are correct  and all presented links are synchronous. The model assumes that the processes start a round with max time lag bound to less than 1/2 RTTB interval. In the presented worst-case scenario:

		- delivery of messages over the presented links takes the max allowed time of 1/2 RTTB;

		- process $Q$ starts a consensus round after process $P$, lagging with the highest tolerated lag of nearly 1/2 RTTB interval;

		- $P$ and $Q$ deliver messages between themselves only via 3-hop indirect channels with the help of processes $P'$, $P''$, $Q'$, and $Q''$.

		On the diagram:

		- $mP1$ denotes MSGPHASE1 message issued by process $P$;

		- $(mP1)$ denotes relayed delivery of $mP1$ as RETRANSM1;

		- $mQ1$ denotes MSGPHASE1 message issued by process $Q$;

		- $(mQ1)$ denotes relayed delivery of $mQ1$ as RETRANSM1.

   		The execution sequence for delivery of MSGPHASE1 messages:

 		1. At its point of time 0, $P$ broadcasts $mP1$, which reaches $P'$;

 		2. At its point of time 0, $Q$ broadcasts $mQ1$, which reaches $Q'$;

 		3. Receiving $mP1$, $P'$ multicasts $(mP1)$, which reaches $Q''$;

 		4. Receiving $mQ1$, $Q'$ multicasts $(mQ1)$, which reaches $P''$;

 		5. Receiving $(mP1)$, $Q''$ multicasts $(mP1)$, which reaches $Q$;

 		6. Receiving $(mQ1)$, $P''$ multicasts $(mQ1)$, which reaches $P$;

 		7. $Q$ receives $(mP1)$ before its point of time 2 RTTB;

 		8. $P$ receives $(mQ1)$ before its point of time 2 RTTB.

  		The delivery of MSGPHASE2 messages follows exactly the same patterns.

   	\vspace{\baselineskip}

    \section{Proofs}

 		\subsection{Synchronous Consensus}
 		We will show that under the model assumptions the algorithm operates with synchrony, as illustrated on Figure 1 where processes $P$, $P'$, $P''$, $Q$, $Q'$, and $Q''$ complete their individual consensus rounds before expiry of 4 RTTB on their individual clocks.

 	 	\textbf{Theorem 1}: \textit{Synchronous consensus during incomplete synchrony.}

 	 	A system of synchronized (less than 1/2 RTTB lag) synchronous processes operating with a 3-hop delivery algorithm, where in a group $G$ of $F+1$ correct processes every process has a synchronous link (1/2 RTTB delivery bound) or an indirect channel over synchronous links to and from every other process in $G$, terminates within 4 RTTB intervals regardless of possibility all other links to be asynchronous.

 		\textbf{Proof}

 		The trivial case is when $F+1$ correct processes are directly connected to each other via $(F+1)*F$ synchronous links. The proof must show that with a fraction of these links, allowing every pair of processes a direct or indirect bidirectional communication, in any combination of direct and 2-hop and 3-hop indirect channels, each of the $F+1$ correct process terminates within 4 RTTB intervals.

		2-hop indirect channels take up to 1 RTTB interval to deliver a message. 3-hop indirect channels take up to 1.5 RTTB interval to deliver a message. In the worst-case scenario, the first process that starts a round receives a message from every other process before expiry of 2 RTTM on its clock, as 1/2 RTTB lag + 1.5 RTTB delivery = 2 RTTM. All other processes receive a message from every other process within a shorter time on their individual clocks. Hence, everyone of the $F+1$ correct processes in $G$  receives the messages necessary and sufficient for termination within 4 RTTB intervals.

	\subsection{Highest Tolerance to Asynchronous Links}
		Gossiping (epidemic dissemination) is typically used to ensure message delivery under the weakest needs of correct links
		\cite{BirmanEtAl1999}
		\cite{EugsterEtAl2004}
		\cite{GuerraouiEtAl2019}.
		Our algorithm implements gossiping for tolerance to faulty and/or asynchronous links. It does so with up to 3-hop indirect delivery. Any additional hop increases the tolerance but delays termination.

		\textbf{Lemma 1}: \textit{Epidemic dissemination of messages}.

		On existence of a path between sender and recipient of a message, an algorithm for epidemic dissemination will deliver the message.

		\textbf{Proof}: In an epidemic algorithm every process of a system forwards the received messages over its output links. Thus, the algorithm utilizes all existing in the system multi-hop delivery routes.

		\textbf{Lemma 2}: \textit{Consensus with epidemic dissemination of messages}.

		A synchronous  consensus algorithm implementing epidemic dissemination of messages ensures highest tolerance to faulty links.

		\textbf{Proof}: It follows from Lemma 1.

		\textbf{Theorem 2}:	\textit{Synchronous consensus with tolerance to asynchrony.}

		Epidemic dissemination of messages lets synchronous consensus algorithm terminate under highest number of asynchronous links.

		\textbf{Proof}

		Consider a synchronous consensus algorithm with epidemic dissemination and a system with $L$ one-way links, where either only faulty or only asynchronous links prevent delivery. Both cases are handled in a way taking longer yet bounded time. In the case with only faulty links, let the smallest sufficient for consensus set of messages $M$ is delivered over one of the smallest sets of correct links $S$ allowing delivery [Lemma 1], i.e. with highest tolerated faulty links $F$ [Lemma 2], $F=L-S$. In the case with only asynchronous links, set $S$ delivers the same set $M$, thus tolerating $A$ asynchronous links, where $A=L-S$ hence $A$ = $F$. As synchronous consensus is not possible with a larger $F$, it is also not possible with a larger $A$.

	\subsection{Leaderless Consensus}

		\textbf{Theorem 3}:	\textit{Leaderless consensus over a medium susceptible to asynchrony and faults.}

		Consensus algorithm, of a system of synchronous processes that communicate over a medium susceptible to asynchrony and faults, does not need to operate with a leader if it can ensure direct or indirect bounded delivery of messages among the required for consensus majority of correct processes.

		\textbf{Proof}

		Let us assume existence of a group $G$ of correct processes, equal or larger than the required for consensus quorum, with ensured bounded delivery, so that every message received by one process of $G$ is also received by every process of $G$ and included a group $M$ messages individually maintained by every process in $G$. Not included in $M$ are the messages: 1) directly received after expiry of 1 RTTB on processor's clock since the start of the current phase; 2) received over a 2-hop channel after expiry of 1.5 RTTB; and 3) received over a 3-hop channel after expiry of 2 RTTB intervals.

		Thus, all processes in $G$ receive within a bounded time the same set of messages $M$, extract exactly the same data, and produce atomically consistent individual states. The consensus value computed by the processes of $G$ is produced from atomically consistent states, and used as input to instances of the same deterministic function. Hence the consensus values individually produced by the processes of $G$ are atomically consistent, as if proposed by a leader.

	\subsection{Ensured Both Safety and Bounded Liveness}

		\textbf{Theorem 4}: \textit{ Possibility for deterministic Byzantine consensus with conceptually ensured simultaneous safety and bounded liveness in partial synchrony.}

		A synchronous deterministic Byzantine consensus algorithm, capable to tolerate asynchrony and faults on its communication medium, operates with conceptually ensured simultaneous safety and bounded liveness in the area within its boundaries of tolerance.

		\textbf{Proof}

		Use of asymmetrically authenticated messages \cite{RivestShamirAdleman78} lets tolerate some  asynchronous / faulty links.
		It prevents a Byzantine process from affecting consensus safety [see Handling Byzantine Deceit in subsection 3.3 and Theorem 3 proof]. Theorem 1 proves bounded delivery within the boundaries of tolerance to links' asynchrony and/or faults and faulty processes [see Handling Byzantine Omission and Handling Byzantine Delay in subsection 3.3]. Theorem 3 proves that under bounded delivery consensus does not need leader. Having ensured leaderless consensus and bounded delivery in spite of links' asynchrony and/or faults and in spite of processes' crashes and/or omissions and/or delays, nothing capable to prevent bounded termination has left non-eliminated. Hence, within its boundaries of tolerance the algorithm operates with conceptually ensured simultaneous safety and bounded liveness.

	\section{Summary of the Results}

		This work demonstrated the following new features and qualities related to deterministic consensus algorithms in partial synchrony:

		1. A concept for proactive handling of asynchrony with virtual indirect multi-hop channels.

		2. Higher tolerance to links asynchrony than the leader-based algorithms with asymmetrically authenticated messages.

		3. Tolerance to any fault of any process, within the tolerated limits of faults and asynchrony, with no effect on bounded liveness.

		4. A fully decentralized deterministic Byzantine consensus algorithm with precisely defined tolerance to asynchronous links.

		5. Conceptually ensured bounded termination and conceptually ensured simultaneous safety and bounded liveness.

		6. Simulator of consensus work, revealing events' permutations capable to prevent bounded liveness [see the Appendix].

		7. A methodology for regression analysis of simulation results and extrapolation [see the Appendix].

		8. Analytically defined tolerance to asynchrony in consensus systems per number of faulty processes [see the Appendix].

		9. Superlinear increase of the tolerated asynchronous links with every added pair of system processes [see the Appendix].

	\section{Conclusion}
		We presented a synchronous deterministic Byzantine consensus algorithm in partial synchrony. It operates with the weakest needs for communication synchrony, has no single point of failure, and ensures simultaneous safety and bounded liveness

		These features are outcome from a trade-off: the tolerance to faults and asynchrony is paid with limits on the efficient scalability and halved throughput. The gained non-existing at present features enable creation of new technologies with impact in areas ranging from financial services to cyber resilience.

		The algorithm lets build technologies solving the obstructed efficiency of financial markets: in terms of time – with real-time settlement of trades; and in terms of consistency – with elimination of conditions allowing creation of phantom stocks.

		A decentralized infrastructure built with the algorithm operates with enforced quantifiable cyber resilience.
		Multiple concurrent security breaches installing malicious code and multiple faulty and/or asynchronous links within the tolerated limits cannot disrupt it.

\begin{acks}
	This work is partly sponsored by the Australian Federal Government through the Research and Development Tax Incentive Scheme.
	The author expresses his gratitude to Simeon Simoff
	for his help with combinatorics, suggestions on formalization, and comments.
\end{acks}

\newpage

	\bibliographystyle{ACM-Reference-Format}


\section{Introduction}
\label{sec:intro}

Over the years vision transformers have shown the ability to rival deep convolution in the field of computer vision by focusing on the similarity between its own elements within an image to improve the semantic information of the representation.
However, the training of the transformer in the image domain is more difficult. First, There are natural differences between images and natural language e.g., images are continuous, natural language is discrete.
Second, The transformer is computationally expensive because it requires a global computation of the image.

In the field of self-supervised learning, the emergence of masked image modeling (MIM) has alleviated the above problems to some extent. MIM uses a auto-encoder (AE)\cite{hinton2006reducing} architecture to train the transformer.
It greatly reduces the computation of transformer by masking the input image token. MIM uses unmasked tokens to predict masked tokens, allowing the transformer model to grasp richer semantic information of the image at the encoding stage.

We propose that Contrastive Masked AutoEncoders (CMAE) aims to design a better paradigm to improve transformer performance based on MIM.
We have studied MIM and its variants in detail, and pointed out the following three directions to improve MIM:

(i) We find that the MIM model achieves representation learning by the encoder and decoder working together for mask token prediction.
However, the purpose of MIM is to make the encoder learn a good representation for the next downstream tasks during the prediction process. However, the presence of the decoder inevitably weakens the performance of the encoder.
Although MIM has been initially designed with an asymmetric structure of weak decoder for the mask token reconstruction task.  But we found in \cite{xie2021simmim} that the decoder can be reduced to a very low number of parameters.
We therefore believe that the capability of the encoder can be indirectly improved by continuing to weaken the decoder while maintaining the reconstruction token.

(ii) The loss function of MIM is a common constraint on the encoder and decoder and does not provide an independent loss function for the encoder.
Therefore the feature extraction capability of the encoder can be enhanced by adding new tasks to it. In CMAE, we designed two new tasks independently for the encoder to improve its performance during downstream tasks.
\cite{chen2022context} separately visualizes the regions that the MIM and the contrast learning model focus on by performing two different tasks separately. We found that the encoder in MIM focuses more on the image global by reconstructing the image.
Contrastive learning obtains unique features of an image by bringing positive samples closer and pushing negative samples farther in a high-dimensional space. Therefore, we designed the two tasks as one.
CMAE expects the encoder to perform image prediction tasks in a way that the features it extracts contain both global and image-specific information by means of contrast learning.
In addition, we found a focus on linguistic order in many natural language models that improve on BERT \cite{devlin2018bert}, such as ALBERT \cite{lan2019albert}. While MIM uses random masking, it gets the order of unmasked tokens in a random order.
In order to enable the encoder to independently grasp the spatial location information of each token, we designed a location prediction task for it.
This task can also be understood as a disorder recovery task since the correct position of the token is mastered to convert the disorder to order.

(iii) We consider that the input image may also have an impact on the MIM. Generally the input image contains not only the main object but also the background and other objects, and all objects in the image are rendered at different scales.
When the proportion of primary objects is relatively small or the unmasked tokens are mainly primary objects, the reconstruction of background or other objects is not meaningful for the encoder to learn the primary object features.
Also, to perform the contrastive learning task better, we introduce ContrastiveCrop \cite{peng2022crafting} to process the input images.
It helps to crop the primary object area by positioning the primary object with the semantic information extracted by the encoder, thus minimizing the interference of background and secondary objects.

The main contributions of this paper can be summarized as:

\begin{itemize}
  \item We discuss the use of a simpler architecture for the MIM decoder to indirectly improve the feature extraction capability of the encoder in MIM. We found that properly weakening the decoder helps the MIM perform downstream tasks while maintaining the recovered image quality.
\item CMAE makes the encoder perform the contrastive learning task while the MIM model performs the image recovery task. This enables the encoder to extract features that focus on both global and image-specific attributes.
\item Inspired by the improvement of Masked Language Model (MLM) in NLP, we designed the position prediction task for the encoder. This task helps the encoder to have information about the spatial location of each token in the image.
\item We consider the effect of the input image on the MIM. By introducing ContrastiveCrop into MIM, it makes MIM more focused on the main object and provides help for contrastive learning in CMAE.
\end{itemize}

\begin{figure*}[h]
  \centering

   \includegraphics[width=1\linewidth]{./figure/figure1.png}
   \caption{Our CMAE architecture. Our CMAE introduces ContrastiveCrop for MIM to optimize the input data of MIM. Meanwhile, we design independent tasks such as comparison learning and position prediction for the encoder of MIM.}
   \label{fig1}
\end{figure*}

\section{Related Work}

\textbf{Contrastive self-supervised learning.} The notion of contrastive learning has been proposed for a long time, but it was Chen et al.'s SIMCLR \cite{chen2020simple} that really made it popular.
The framework extracts representations that substantially outperform current SOTA, sparking a boom in contrastive self-supervised learning.
He et al. proposed MOCO v1 \cite{he2020momentum} and introduced the idea of queue in/out and encoder momentum update into the comparative learning, which solved the limitation of GPU memory on batch size.
With the introduction of SIMCLR, He et al. improved the data augment method based on MOCO v1 by adding a projection layer after the encoder and using cosine decay to create a more powerful MOCO v2 \cite{chen2020improved}.
Chen et al. also improved SIMCLR by adopting a deeper ResNet-152 as the encoder and using a deeper projection layer, updating it to SIMCLR v2 \cite{chen2020big}.
Since comparative learning requires many negative examples for comparison, which is both time and memory consuming, Caron et al. proposed SwAV \cite{caron2020unsupervised} to reduce the loss of comparative learning by means of clustering.
Caron et al. then proposed comparative learning training on larger open domain data, leading to the SEER \cite{goyal2021self}.
Grill et al. proposed BYOL \cite{grill2020bootstrap}, which solves the pattern collapse problem associated with contrastive learning by stopping the gradient and adding batch normalization to the projection layer in a way that allows the model to be compared implicitly.
By exploring the Siamese Network, He et al. found that stopping the gradient is is the key to avoid pattern collapse, and proposed SimSiam \cite{chen2021exploring}. To better train the encoders in the MIM model, we introduce a pre-training task of contrastive learning for CMAE.

\textbf{Generative self-supervised learning.} Generative self-supervised models are mainly auto-encoder and its variants, Hinton et al. were the first to propose a auto-encoder (AE) \cite{hinton2006reducing} for the purpose of dimensionality reduction of data.
To reduce computational consumption, Bengio et al. proposed a sparse auto-encoder \cite{vincent2010stacked}. Kingma et al. designed the powerful generative model of variational auto-encoder (VAE) \cite{kingma2013auto} by extrapolating the variational Bayes.
Vincent et al. proposed Denoising autoencoder (DAE) \cite{gidaris2019generating} to mitigate the overfitting problem of AE by adding noise to the input, which improved the robustness of AE.
With the popularity of convolutional neural networks (CNN) \cite{krizhevsky2012imagenet,he2016deep}, Masci et al. proposed a convolutional auto-encoder (CAE) \cite{chen2022context} based on the AE, Oord et al. created the Vector QuantisedVariational AutoEncoder (VQ-VAE) \cite{razavi2019generating}, which produces very realistic images, by making the encoder output discrete.
Recently, He et al. proposed a new auto-encoder called Masked AutoEncoders \cite{he2021masked} for training transformer by partially masking the image.
chen et al. designed the context autoencoder \cite{chen2022context} by separating the two tasks of image reconstruction and representation learning. Dong et al. created Peco \cite{dong2021peco} by combining MIM with a discrete codebook.
Xie et al. have also achieved good results in image recovery and downstream tasks using fully connected layers as decoders in simMIM \cite{xie2021simmim}. These related works have helped us tremendously in studying the improvements to MIM.

\textbf{Transformer.} The attention mechanism was first proposed by Vaswani, Ashish, et al. \cite{vaswani2017attention}. It is the core of the transformer.
In recent years, Dosovitskiy et al. proposed an efficient visual transformer by chunking images: the Vision Transformer (VIT) \cite{dosovitskiy2020image}, which achieved SOTA results in many tasks.
To moderate the reliance of VIT on large datasets, Touvron et al. used CNNs as teachers and transformers as students, and designed Deit \cite{touvron2021training} through this use of a teacher-student strategy in pretraining.
By knowledge distillation training strategy \cite{hinton2015distilling}, Touvron et al. also proposed CAIT \cite{touvron2021going}, which can train transformer without external data. Wang et al. proposed PVT \cite{wang2021pyramid}, which uses a pyramid structure to adapt the transformer to intensive prediction tasks.
In order to solve the problems of varying instance sizes and large pixel computations that exist in the field of transformer in images, Liu et al. proposed Swin Transformer \cite{liu2021swin} by moving the window to compute attention.
Our CMAE is dedicated to researching better training methods for vision transformers.

\section{Methodology}

\subsection{Contrastive Masked AutoEncoders Framework}

Our CMAE works on the improvement of MIM to exploit the greater potential of transformer in computer vision self-supervised learning (SSL). Our general framework is shown in Fig.\ref{fig1}. CMAE contains four major improvements:

\begin{itemize}
  \vspace{-5pt}
\item[1)] Data Augmentation. Given an input image, CMAE will use ContrastiveCrop for data augmentation after a certain number of epoch training. ContrastiveCrop will improve the input data of MIM.
\vspace{-5pt}
\item[2)] Contrastive Tasks. We introduce a contrastive task for the CMAE encoder to enhance the feature extraction capability of the encoder.
Contrastive learning allows the CMAE encoder to extract features unique to the image, further enhancing the performance of MIM when performing downstream tasks.
\vspace{-5pt}
\item[3)] Location Prediction Tasks. To enable the encoder of MIM to have the spatial position information of the image, we designed the position prediction task for the encoder of CMAE.
\vspace{-5pt}
\item[4)] Decoder. Through the study of \cite{xie2021simmim} we found that the decoder in MIM can use a simpler structure.Therefore, we have experimented with various decoder architectures to find the decoder framework that can improve the performance of MIM.
\end{itemize}

\subsection{Data Augmentation}
\begin{figure}[t]
  \centering

   \includegraphics[width=1\linewidth]{./figure/figure2.png}
   \caption{The first row shows two types of problems that may result from random masking of MIM input data with unmasked tokens all primary objects (a) and masked tokens all primary objects (b). The second row shows the effect of introducing ContrastiveCrop (c)(d).}
   \label{fig2}
\end{figure}

We first discuss improvement options for the MIM input. We found that when the proportion of the main object in the MIM input image is relatively small or there are more other objects may affect the performance of MIM.
As shown in Fig.\ref{fig2}, since the MIM performs random masking, all the markers associated with the primary object may be unmasked markers when the above two cases occur Fig.\ref{fig2}(a).
At this point the MIM performs the use of primary object tokens to predict background or other irrelevant objects. This does not achieve the purpose of the MIM to learn the primary object representations by mutual prediction between the primary object tokens.
Or random masks may also cause the images in the above two cases to appear as in Fig.\ref{fig2}(b). It is also not logical to recover the token of the main object that is masked by the token of the unmasked background and other objects at this point.
Therefore, we introduce ContrastiveCrop \cite{peng2022crafting} to perform data augmentation on the input images in MIM.
Since contrastive learning draws the positive case samples closer and pushes the negative case samples farther in the high-dimensional space. This forces the model to focus on the main object to discover unique features of the image.
As a result, ContrastiveCrop automatically locates the main objects for cropping based on the main semantic information extracted by the contrast learning model.
Fig.\ref{fig2}(c)(d) shows the possible results of using ContrastiveCrop for data augmentation of the input image with random masking.
We can observe that this method maximizes the proportion of the main object in the input image and greatly suppresses the background and other object information.
When the image is basically the main object, the above two types of problems can be avoided as much as possible, thus achieving the original purpose of MIM.
And ContrastiveCrop plays a mutually reinforcing role with the contrast learning task we added to MIM.  ContrastiveCrop usually uses the weighted result of each channel of the last layer of the feature map of the convolution layer to produce a heat map (M) to locate the main object position for cropping, which can be written as,

\begin{equation}
  \begin{split}
  &({x_1},{x_2},{x_3},{x_4}) = {R_{crop}}(s,r,I)\\
  &I = F(1[M > k])
\end{split}
  \label{eq1}
\end{equation}

where $R_{crop}$() is a random sampling function that is used to return quaternions ($x_1$, $x_2$, $x_3$, $x_4$) representing the crop, s denotes scaling, r denotes aspect ratio. k is a threshold value between 0 and 1, s, 1 is the indicator function and F is used to calculate the rectangular region I after feature map activation.
Since we explored how to better train the transformer using MIM, while ContrastiveCrop only investigated localization using convolutional feature maps.
Therefore, we tested the results of using the feature output of the last layer of VIT \cite{dosovitskiy2020image} and the multi-headed attention map using the last stage separately.
The reason we consider multi-headed attention maps is that we think that attention maps in the transformer may be more suitable for heat map production of the main objects than the last layer of output.
Because the attention map represents the most relevant regions in the feature map.

\subsection{Contrastive Tasks}

Self-supervised learning includes contrastive self-supervised learning and generative self-supervised learning. Contrastive self-supervised learning uncovers unique features of images by comparing positive and negative examples in a high-dimensional space.
Generative self-supervised learning learns image information by reconstructing the image. MIM belongs to generative self-supervised learning in self-supervised learning. \cite{chen2022context} shows the regions of interest for MIM and contrastive learning, respectively.
We find that MIM prefers to observe the image globally in order to meet the need for image recovery. MOCO-v3 \cite{chen2021empirical}, on the other hand, is more oriented to observe unique regions of the image in order to bring the positive examples closer and move away from the negative ones.
Thus, in order to make MIM better train the transformer, we introduce contrastive learning as an independent task of the MIM encoder. Thereby, the transformer in CMAE can both mine the unique features of the image and retain the global information of the image.
We first initialize two encoders of the same weight, E and ME, where ME is updated by the E momentum.
Then two data-enhanced images $x_q$, $x_k$ belonging to the same object will be subjected to random masking operations to obtain the unmasked vector $q_1$,$k_1$ and the masked vector $q_2$,$k_2$ respectively.
Then E will extract the features of $q_1$ and $q_2$, and ME will extract the features of $k_1$, $k_2$, but since $q_2$ belongs to the unmasked vector, CMAE will not record the gradient of $q_2$.
Eventually, as shown in Eq.\ref{eq2}, the two types of token representations belonging to the same image are merged and the correct order is restored.

\begin{equation}
  \begin{split}
  &{{\rm{h}}_1} = restore(concat[{q_1},detach({q_2})])\\
  &{{\rm{h}}_{\rm{2}}} = restore(concat[{k_1},{k_2}])
\end{split}
  \label{eq2}
\end{equation}

where detach() means stopping the gradient operation, concat() means merging the vectors, and restore() means restoring the order.
Finally $h_1$ and $h_2$ will be input into the projection layer P and the projection layer MP updated by the momentum of P (MP is initialized by the weights of P), respectively, to obtain the higher order vectors $z_q$, $z_k$.
The dot product is used to measure the similarity between $z_q$,$z_k$ and InfoNCE \cite{van2018representation} is used as the loss function for the comparative task:
\begin{equation}
\begin{split}
{L_{{\rm{ctr}}}} =  - \log \frac{{\exp ({z_q}.{z_k}/\tau )}}{{\exp ({z_q}.{z_k}/\tau ) + \sum\limits_{{z_{{k^ - }}}} {\exp ({z_q}.{z_{{k^ - }}}/\tau )} }}
\end{split}
\label{eq3}
\end{equation}

Where $\tau$ is a temperature hyper-parameter \cite{wu2018unsupervised}, The set ${z_{k-}}$ consists of other image outputs of ME and MP.

\subsection{Location Prediction Tasks}

By studying algorithms such as albert \cite{lan2019albert} in NLP, we found that having spatial location information helps to improve encoder performance.
Through further research in the field of computer vision about \cite{chen2019destruction} we found that the spatial location information is beneficial to improve the local modeling capability of the model.
So we designed another location prediction task for the MIM encoder to enhance the transformer's understanding of the image local information. Since MIM uses a random mask, this guarantees us the feasibility of this task. Meanwhile, predicting the position of each token will restore each token to its correct position.
Consequently, this task can also be considered as a disorder recovery task. Because we do not want the encoder to observe the masked token, CMAE only predicts the correct location of the unmasked token. As it is a random mask, each location is considered.
As illustrated in Eq.\ref{eq4}, we use only two MLP layers for location prediction.
\begin{equation}
    {\rm{p}} = MLP(MLP({q_1}))
  \label{eq4}
  \end{equation}

p denotes the spatial coordinates of the unmasked token q1 predicted by CMAE. Note that q1 does not contain the cls token at this point because the cls token does not have a real position in the image.
Then CMAE converts the real coordinates to the unique thermal encoding form t. The location prediction losses are as follows,

\begin{equation}
{L_{{\rm{loc}}}} = ||q - t|{|_2}
\label{eq5}
\end{equation}

\subsection{Decoder Framework}

Motivated by \cite{xie2021simmim}, we expect to find weakened decoder architectures for MIM to indirectly enhance the efficiency of the encoder when performing downstream tasks.
The weaker decoder also helps to reduce the number of parameters of CMAE and optimize its efficiency. We designed four scenarios for the weakened decoder.
\begin{itemize}
  \vspace{-5pt}
\item[1)] Lowering parameters. We consider both cases of decoder layer reduction and decoder dimension reduction. We tested CMAE by reducing two layers per 	decoder.
On the other hand we have designed a series of dimensions such as [512,256,128,64] for the decoder.
\vspace{-5pt}
\item[2)] MLP decoder. We replace all the transformer architectures in the MIM decoder	with MLP for testing. The decoder dimension is same as the corresponding MIM decoder dimension. The decoder depth is kept as the corresponding MIM 	decoder depth.
\vspace{-5pt}
\item[3)] Convolutional decoder. We designed a deep convolutional model with 	convolutional kernel of 3, step size of 1 and padding of 1 as the convolutional decoder of CMAE.
The number of channels and depth of the 	convolutional decoder are aligned with the dimensionality and depth of the 	corresponding MIM decoder.
\vspace{-5pt}
\item[4)] Hybrid decoder. We try to degrade the decoder performance by mixing the 	transformer decoder in MIM with MLP and convolution respectively. We replace 	the decoder middle layer while keeping the original MIM decoder hyperparameters.
Deep convolution contributes to the MIM decoder's ability 	to improve channel and local modeling. It also provides multi-scale information for the decoder in MIM.
MLP provides a simpler architecture compared to transformer, which helps to improve decoder efficiency.
\end{itemize}
We still use the MSE loss as reconstruction loss $L_{con}$ to recover the mask token by reconstructing the pixel form.

\subsection{Objective function}
The loss function of CMAE consists of a contrast loss $L_{ctr}$, a location prediction loss $L_{loc}$, and a pixel reconstruction loss $L_{con}$. we can finally formulate our loss as
\begin{equation}
L = {\lambda _{ctr}}{L_{ctr}} + {\lambda _{{\rm{loc}}}}{L_{{\rm{loc}}}} + {\lambda _{con}}{L_{con}}
  \label{eq6}
  \end{equation}

$\lambda_{ctr}$,$\lambda_{loc}$ and $\lambda_{con}$ are the hyperparameters of contrast loss,location prediction loss and reconstruction loss,respectively. We default them all to 1.

\section{Experiments}
In this section we conduct experiments to verify the efficiency of CMAE. We first describe the data set and comparison methods in section 4.1. We then describe the experimental procedure in section 4.2.
Then, we compare CMAE with other methods and show the experimental results in section 4.3.

\subsection{Dataset and Baseline Methodology}

We compared it with varies state-of-the-art self-supervised algorithms on tiny-imagenet. Tiny ImageNet contains 100000 images of 200 classes (500 for each class) downsized to 64×64 colored images.
Each class has 500 training images, 50 validation images and 50 test images. We compared CMAE with MOCO-v1 \cite{he2020momentum}, MOCO-v2 \cite{chen2020improved}, and MAE \cite{he2021masked}.

\subsection{Experimental Details}
For MOCO-v1, we used ResNet18 as its base model, pre-trained with 500 epochs and the batch size set to 512. Then linear classification was performed using 100 epochs.

For MOCO-v2, we use ResNet50 for pre-training of 200 epochs in a batch size of 128. Then freeze the pre-trained model and perform linear classification with 100 epochs.

For MAE, we use ViT-Base as the base model in tiny-imagenet for 300 epochs of pre-training. MAE uses a mask ratio of 0.75 and a weight decay rate of 0.05. The default batch size is 64 and the base learning rate is 1e-3.
The scheduled solution is cosine annealing. Next, the pre-trained model is frozen and fine-tuned for 100 epochs.

For CMAE, the details of our experiments are all consistent with MAE.

\subsection{Experimental Results}
\setlength\tabcolsep{1pt}

\begin{table}[htbp]

\tablestyle{5pt}{1.05}
\caption{Classification results of the self-supervised model on tiny-imagenet.}
\begin{tabular}{llccc}
    \toprule
    Method & Architecture & Epochs & Batch & Top-1 accuracy \\
    \midrule
    MOCO-v1 & \scriptsize ResNet-18 & 500   & 512   & 47.09\% \\
    MOCO-v2 & \scriptsize ResNet-50 & 200   & 128   & 45.82\% \\
    MAE   & \scriptsize ViT-B & 300   & 64    & 62.95\% \\
    CMAE  & \scriptsize ViT-B & 300   & 64    & \textbf{65.84}\% \\
    \bottomrule
    \end{tabular}%
  \label{tab1}%
\end{table}%

Our results on tiny-imagenet are shown in Tab.\ref{tab1}.

\section{Conclusion}
For better optimization of transformer training in self-supervised learning, we have discussed and investigated on the basis of MIM. We specifically studied three directions of improvement of the MIM paradigm.
First we studied the improvement of the MIM input. We have introduced ContrastiveCrop into MIM in order to make MIM better for the purpose of recovering the main objects of images.
And we have also explored how ContrastiveCrop can be better used for transformer. Second, we discussed the task of enhancing MIM.
We introduced a contrastive task and a position prediction task for the MIM encoder to enhance the MIM's ability to perform downstream tasks.
Third, we explore how the MIM decoder can be weakened so that indirect MIM can improve encoder performance. In terms of the results of tiny-imagenet, our study has achieved good results that provide other researchers with an in-depth exploration of MIM.

We will continue to update this paper, so stay tuned.

{\small
\bibliographystyle{ieee_fullname}