International Association
for Cryptologic Research

In this paper, we address the Byzantine Agreement problem in synchronous systems where Byzantine agents can move from process to process, corrupting their host. We focus on three representative models: \emph{Garay's}, \emph{Bonnet's} and \emph{Buhrman's} models. In \emph{Garay's model} when a process has been left by the Byzantine, it is in the \emph{cured} state and it is aware of its condition and thus can remain silent for a round to prevent the dissemination of wrong information. In \emph{Bonnet's model} a cured process may send messages (based on a state corrupted by the malicious agent), however it will behave correctly in the way it sends those messages: i.e., send messages according to the algorithm. In \emph{Buhrman's model} Byzantine agents move together with the message. It has been shown that in order to solve Byzantine Agreement in the \emph{Garay's model} at least $4t+1$ processors are needed, for \emph{Bonnet's model} at least $5t+1$ processors are needed, while for \emph{Buhrman's model} at least $3t+1$ processors are needed. In this paper we target to increase the tolerance to mobile Byzantines by integrating a trusted counter abstraction to the above models. This abstraction prevents nodes to equivocate. In the new models we prove that at least $3t+1$, respectively $4t+1$, and $2t+1$ processors are needed to tolerate $t$ mobile Byzantine agents. Furthermore, we propose novel Mobile Byzantine Agreement algorithms that match these new lower bounds for \emph{Garay's}, \emph{Bonnet's} and \emph{Buhrman's} models.