This paper proposes the first implementation of a self-stabilizing atomic register that is tolerant to both Mobile Byzantine Agents and transient failures. The register is maintained by n servers and our algorithm tolerates (i) any number of transient failures and (ii) up to f Mobile Byzantine Failures. In the Mobile Byzantine Failure model, faulty agents move from one server to another and when they are affecting a server, it behaves arbitrarily. Our implementation is designed for the round-based synchronous model where agents are moved from round to round. The paper considers four Mobile Byzantine Failure models differing for the diagnosis capabilities at server side i.e., when servers can diagnose their failure state (that is, be aware that the mobile Byzantine agent has left the server), and when servers cannot self-diagnose. We first prove lower bounds on the number of servers n necessary to construct a register tolerant to the presence of f Mobile Byzantine Failures for each of the Mobile Byzantine Failure models considered and then we propose a parametric algorithm working in all the models and matching the lower bounds.
Tight self-stabilizing mobile byzantine-tolerant atomic register / Bonomi, Silvia; DEL POZZO, Antonella; Potop Butucaru, Maria. - ELETTRONICO. - 04-07 January 2016:(2016), pp. 1-10. (Intervento presentato al convegno 17th International Conference on Distributed Computing and Networking tenutosi a Singapore) [10.1145/2833312.2833320].
Tight self-stabilizing mobile byzantine-tolerant atomic register
BONOMI, Silvia;DEL POZZO, ANTONELLA;
2016
Abstract
This paper proposes the first implementation of a self-stabilizing atomic register that is tolerant to both Mobile Byzantine Agents and transient failures. The register is maintained by n servers and our algorithm tolerates (i) any number of transient failures and (ii) up to f Mobile Byzantine Failures. In the Mobile Byzantine Failure model, faulty agents move from one server to another and when they are affecting a server, it behaves arbitrarily. Our implementation is designed for the round-based synchronous model where agents are moved from round to round. The paper considers four Mobile Byzantine Failure models differing for the diagnosis capabilities at server side i.e., when servers can diagnose their failure state (that is, be aware that the mobile Byzantine agent has left the server), and when servers cannot self-diagnose. We first prove lower bounds on the number of servers n necessary to construct a register tolerant to the presence of f Mobile Byzantine Failures for each of the Mobile Byzantine Failure models considered and then we propose a parametric algorithm working in all the models and matching the lower bounds.File | Dimensione | Formato | |
---|---|---|---|
Bonomi_Tight-Self-Stabilizing_2016.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
410.95 kB
Formato
Adobe PDF
|
410.95 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.