Optimal Self-Stabilizing Mobile Byzantine-Tolerant Regular Register with bounded timestamp

Abstract : This paper proposes the first implementation of a self-stabilizing regular register emulated by $n$ servers that is tolerant to both mobile Byzantine agents, and \emph{transient failures} in a round-free synchronous model. Differently from existing Mobile Byzantine tolerant register implementations, this paper considers a more powerful adversary where (i) the message delay (i.e., $\delta$) and the period of mobile Byzantine agents movement (i.e., $\Delta$) are completely decoupled and (ii) servers are not aware of their state i.e., they do not know if they have been corrupted or not by a mobile Byzantine agent. The proposed protocol tolerates \emph{(i)} any number of transient failures, and \emph{(ii)} up to $f$ Mobile Byzantine agents. In addition, our implementation uses bounded timestamps from the $\mathcal{Z}_{13}$ domain and it is optimal with respect to the number of servers needed to tolerate $f$ mobile Byzantine agents in the given model.
Complete list of metadatas

Contributor : Antonella Del Pozzo <>
Submitted on : Monday, October 22, 2018 - 3:02:36 PM
Last modification on : Tuesday, May 14, 2019 - 10:14:18 AM
Long-term archiving on : Wednesday, January 23, 2019 - 12:49:41 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License


  • HAL Id : hal-01362193, version 2
  • ARXIV : 1609.02694


Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru, Sébastien Tixeuil. Optimal Self-Stabilizing Mobile Byzantine-Tolerant Regular Register with bounded timestamp. [Research Report] UPMC - Université Paris 6 Pierre et Marie Curie; Sapienza Università di Roma (Italie). 2016. ⟨hal-01362193v2⟩



Record views


Files downloads