In this paper we prove lower and matching upper bounds for the number of servers required to implement a regular shared register that tolerates unsynchronized Mobile Byzantine failures. We consider the strongest model of Mobile Byzantine failures to date: agents are moved arbitrarily by an omniscient adversary from a server to another in order to deviate their computation in an unforeseen manner. When a server is infected by an Byzantine agent, it behaves arbitrarily until the adversary decides to move the agent to another server. Previous approaches considered asynchronous servers with synchronous mobile Byzantine agents (yielding impossibility results), and synchronous servers with synchronous mobile Byzantine agents (yielding optimal solutions for regular register implementation, even in the case where servers and agents periods are decoupled). We consider the remaining open case of synchronous servers with unsynchronized agents, that can move at their own pace, and change their pace during the execution of the protocol. Most of our findings relate to lower bounds, and characterizing the model parameters that make the problem solvable. It turns out that unsynchronized mobile Byzantine agent movements requires completely new proof arguments, that can be of independent interest when studying other problems in this model. Additionally, we propose a generic server-based algorithm that emulates a regular register in this model, that is tight with respect to the number of mobile Byzantine agents that can be tolerated. Our emulation spans two awareness models: servers with and without self-diagnose mechanisms. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state.

Optimal Storage under Unsynchronized Mobile Byzantine Faults / Bonomi, Silvia; Pozzo, Antonella Del; Potop-Butucaru, Maria; Tixeuil, Sebastien. - (2017), pp. 154-163. (Intervento presentato al convegno 36th IEEE Symposium on Reliable Distributed Systems, (SRDS) 2017 tenutosi a Hong Kong; Hong Kong nel September 26-29, 2017) [10.1109/SRDS.2017.20].

Optimal Storage under Unsynchronized Mobile Byzantine Faults

Bonomi, Silvia
;
Pozzo, Antonella Del
;
Potop-Butucaru, Maria;Tixeuil, Sebastien
2017

Abstract

In this paper we prove lower and matching upper bounds for the number of servers required to implement a regular shared register that tolerates unsynchronized Mobile Byzantine failures. We consider the strongest model of Mobile Byzantine failures to date: agents are moved arbitrarily by an omniscient adversary from a server to another in order to deviate their computation in an unforeseen manner. When a server is infected by an Byzantine agent, it behaves arbitrarily until the adversary decides to move the agent to another server. Previous approaches considered asynchronous servers with synchronous mobile Byzantine agents (yielding impossibility results), and synchronous servers with synchronous mobile Byzantine agents (yielding optimal solutions for regular register implementation, even in the case where servers and agents periods are decoupled). We consider the remaining open case of synchronous servers with unsynchronized agents, that can move at their own pace, and change their pace during the execution of the protocol. Most of our findings relate to lower bounds, and characterizing the model parameters that make the problem solvable. It turns out that unsynchronized mobile Byzantine agent movements requires completely new proof arguments, that can be of independent interest when studying other problems in this model. Additionally, we propose a generic server-based algorithm that emulates a regular register in this model, that is tight with respect to the number of mobile Byzantine agents that can be tolerated. Our emulation spans two awareness models: servers with and without self-diagnose mechanisms. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state.
2017
36th IEEE Symposium on Reliable Distributed Systems, (SRDS) 2017
Mobile Byzantine failures; Regular register; Round free synchronous computation
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Optimal Storage under Unsynchronized Mobile Byzantine Faults / Bonomi, Silvia; Pozzo, Antonella Del; Potop-Butucaru, Maria; Tixeuil, Sebastien. - (2017), pp. 154-163. (Intervento presentato al convegno 36th IEEE Symposium on Reliable Distributed Systems, (SRDS) 2017 tenutosi a Hong Kong; Hong Kong nel September 26-29, 2017) [10.1109/SRDS.2017.20].
File allegati a questo prodotto
File Dimensione Formato  
Bonomi_Postprint_Optimal-Storage_2017.pdf

accesso aperto

Note: https://ieeexplore.ieee.org/document/8069078
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 501.29 kB
Formato Adobe PDF
501.29 kB Adobe PDF
Bonomi_Optimal-Storage_2017.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 559.45 kB
Formato Adobe PDF
559.45 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1022950
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact