Memória Compartilhada em Sistemas Bizantinos Dinâmicos
Abstract
Byzantine quorum systems are a useful tool to implement consistent and available data storage systems in the presence of arbitrary faults. In this work we consider a dynamic variant of this system and propose a set of Byzantine fault-tolerant protocols, called QUINCUNX, that emulates a register in dynamic asynchronous systems. Particularly, we present a reconfiguration protocol that does not require consensus and that is loosely coupled with read/write protocols, making it easy to use with any other static Byzantine fault-tolerant register implementation.
References
Aguilera, M. (2004). A pleasant stroll through the land of infinitely many creatures. SIGACT News, 35(2):36–59.
Aguilera, M. K., Keidar, I., Malkhi, D., and Shraer, A. (2011). Dynamic atomic storage without consensus. JACM, 58:7:1–7:32.
Alchieri, E. A. P. (2011). Protocolos Tolerantes a Faltas Bizantinas para Sistemas Distribuı́dos Dinâmicos. Tese de doutorado em engenharia de automação e sistemas, Universidade Federal de Santa Catarina.
Bazzi, R. A. and Ding, Y. (2004). Non-skipping timestamps for Byzantine data storage systems. In Proc. of 18th Int. Symposium on Distributed Computing, DISC 2004, volume 3274 of LNCS, pages 405–419.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Dierks, T. and Allen, C. (1999). The TLS Protocol Version 1.0 (RFC 2246). IETF Request For Comments.
Gifford, D. (1979). Weighted voting for replicated data. In Proc. of the 7th ACM Symposium on Operating Systems Principles, pages 150–162.
Herlihy, M. (1991). Wait-free synchronization. ACM Transactions on Programing Languages and Systems, 13(1):124–149.
Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.
Lamport, L. (1986). On interprocess communication (part II). Distributed Computing, 1(1):203–213.
Lynch, N. and Shvartsman, A. A. (2002). Rambo: A reconfigurable atomic memory service for dynamic networks. In 16th International Symposium on Distributed Computing - DISC, pages 173–190.
Malkhi, D. and Reiter, M. (1998a). Byzantine quorum systems. Distributed Computing, 11(4):203–213.
Malkhi, D. and Reiter, M. (1998b). Secure and scalable replication in Phalanx. In Proc. of 17th Symposium on Reliable Distributed Systems, pages 51–60.
Martin, J.-P. and Alvisi, L. (2004). A framework for dynamic Byzantine storage. In Proceedings of the International Conference on Dependable Systems and Networks. IEEE Computer Society.
Rodrigues, R. and Liskov, B. (2004). Rosebud: A scalable Byzantine-fault-tolerant storage architecture. MIT-LCS-TR 932, MIT Laboratory for Computer Science.
Shraer, A., Martin, J.-P., Malkhi, D., and Keidar, I. (2010). Data-centric reconfiguration with network-attached disks. In Proceedings of the 4th International Workshop on Large Scale Distributed Systems and Middleware.
Aguilera, M. K., Keidar, I., Malkhi, D., and Shraer, A. (2011). Dynamic atomic storage without consensus. JACM, 58:7:1–7:32.
Alchieri, E. A. P. (2011). Protocolos Tolerantes a Faltas Bizantinas para Sistemas Distribuı́dos Dinâmicos. Tese de doutorado em engenharia de automação e sistemas, Universidade Federal de Santa Catarina.
Bazzi, R. A. and Ding, Y. (2004). Non-skipping timestamps for Byzantine data storage systems. In Proc. of 18th Int. Symposium on Distributed Computing, DISC 2004, volume 3274 of LNCS, pages 405–419.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Dierks, T. and Allen, C. (1999). The TLS Protocol Version 1.0 (RFC 2246). IETF Request For Comments.
Gifford, D. (1979). Weighted voting for replicated data. In Proc. of the 7th ACM Symposium on Operating Systems Principles, pages 150–162.
Herlihy, M. (1991). Wait-free synchronization. ACM Transactions on Programing Languages and Systems, 13(1):124–149.
Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.
Lamport, L. (1986). On interprocess communication (part II). Distributed Computing, 1(1):203–213.
Lynch, N. and Shvartsman, A. A. (2002). Rambo: A reconfigurable atomic memory service for dynamic networks. In 16th International Symposium on Distributed Computing - DISC, pages 173–190.
Malkhi, D. and Reiter, M. (1998a). Byzantine quorum systems. Distributed Computing, 11(4):203–213.
Malkhi, D. and Reiter, M. (1998b). Secure and scalable replication in Phalanx. In Proc. of 17th Symposium on Reliable Distributed Systems, pages 51–60.
Martin, J.-P. and Alvisi, L. (2004). A framework for dynamic Byzantine storage. In Proceedings of the International Conference on Dependable Systems and Networks. IEEE Computer Society.
Rodrigues, R. and Liskov, B. (2004). Rosebud: A scalable Byzantine-fault-tolerant storage architecture. MIT-LCS-TR 932, MIT Laboratory for Computer Science.
Shraer, A., Martin, J.-P., Malkhi, D., and Keidar, I. (2010). Data-centric reconfiguration with network-attached disks. In Proceedings of the 4th International Workshop on Large Scale Distributed Systems and Middleware.
Published
2012-04-30
How to Cite
ALCHIERI, Eduardo Adilio Pelinson; BESSANI, Alysson Neves; FRAGA, Joni da Silva; GREVE, Fabíola.
Memória Compartilhada em Sistemas Bizantinos Dinâmicos. In: FAULT TOLERANCE WORKSHOP (WTF), 13. , 2012, Ouro Preto/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 57-70.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2012.23080.
