Optimal self-stabilizing synchronous mobile Byzantine-tolerant atomic register

摘要

AbstractThis paper addresses for the first time the problem of MWMR atomic memory in aMobile Byzantine Agentsmodel. The register is maintained bynservers and faulty (Byzantine) agents move from one server to another and when they are affecting a server, this one behaves arbitrarily. This paper addresses the round-based synchronous communication model. We focus on four Mobile Byzantine Failure models differing in the diagnosis capabilities at server side. We address the case when servers can diagnose their failure state (that is, servers are aware that the mobile Byzantine agent has left), and the case when servers cannot self-diagnose.We first prove lower bounds on the number of serversnnecessary to construct a safe register tolerant to the presence off/mml:mo>nMobile Byzantine Failures for four Mobile Byzantine Failure models. Additionally, we prove that our lower bounds do not change when the system is affected by any number oftransient failures.Furthermore, we propose a parametric algorithm that implements an atomic MWMR register algorithm working in all the above models and matches the lower bounds. Additionally, our algorithm is also self-stabilizing. That is, started in an arbitrary state (i.e. after the occurrence of a transient failure) it is able to self-recover a correct behavior in a finite, bounded number of rounds. Our algorithm tolerates (i) any number of transient failures and (ii) up tofMobile Byzantine Failures.]]>