2026-07-25T03:07:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25180 2026-03-19T12:59:15Z ddc:004 open_access

Mobile Byzantine Agreement in a Trusted World Pan, Bo Potop-Butucaru, Maria Byzantine Agreement Mobile Faults Trusted Abstractions 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 two representative models: Garay’s and Buhrman’s models. In Garay’s model, when a process has been left by the Byzantine agent, it enters a cured state, is aware of its condition, and can remain silent for a round to prevent the dissemination of incorrect information. In Buhrman’s model, a Byzantine agent moves together with the message. It has been shown that solving Byzantine Agreement requires at least 4t + 1 processes in Garay’s model, and at least 3t + 1 in Buhrman’s model. In this paper, we aim to increase the tolerance to mobile Byzantine agents by integrating a trusted counter abstraction into both models. This abstraction prevents nodes from equivocating. In the new models, we prove that at least 3t+1, respectively 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 both Garay’s and Buhrman’s models, achieving agreement in 𝒪(n) synchronous rounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bo Pan and Maria Potop-Butucaru 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.7 urn:nbn:de:0030-drops-251809 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.7 eng https://creativecommons.org/licenses/by/4.0/legalcode