Consenso Bizantino entre Participantes Desconhecidos
Resumo
O problema do consenso é a base para a solução da maioria dos problemas que envolvem sistemas distribuı́dos confiáveis. Apesar do consenso estar amplamente estudado em ambientes clássicos, onde o conjunto de participantes é conhecido, poucos trabalhos consideram este problema em ambientes dinâmicos e auto-organizáveis, onde os participantes da computação são, a priori, desconhecidos. Neste trabalho, propomos duas soluções para o consenso bizantino entre participantes desconhecidos (BFT-CUP), com e sem o uso de assinaturas digitais, e provamos que o grau de conhecimento sobre os participantes do sistema necessário nestas soluções é o mı́nimo necessário para resolver o BFT-CUP.Referências
Awerbuch, B., Holmer, D., Nita-Rotaru, C., and Rubens, H. (2002). An on-demand secure routing protocol resilient to byzantine failures. In WiSE ’02: Proceedings of the 1st ACM workshop on Wireless security, pages 21–30, New York, NY, USA. ACM.
Castro, M., Druschel, P., Ganesh, A., Rowstron, A., and Wallach, D. S. (2002). Secure routing for structured peer-to-peer overlay networks. SIGOPS Oper. Syst. Rev., 36(SI):299–314.
Castro, M. and Liskov, B. (2002). Practical Byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398–461.
Cavin, D., Sasson, Y., and Schiper, A. (2004). Consensus with unknown participants or fundamental self-organization. In Proc. of the 3rd Int. Conf. on Ad hoc Networks and Wireless, pages 135–148.
Cavin, D., Sasson, Y., and Schiper, A. (2005). Reaching agreement with unknown participants in mobile self-organized networks in spite of process crashes. Technical Report IC/2005/026, EPFL - LSR.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Dolev, D. (1982). The Byzantine generals strike again. Journal of Algorithms, (3):14–30.
Dwork, C., Lynch, N. A., and Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of ACM, 35(2):288–322.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382.
Greve, F. G. P. and Tixeuil, S. (2007). Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. In Proc. of the Int. Conf. on Dependable Systems and Networks - DSN 2007, pages 82–91.
Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.
Castro, M., Druschel, P., Ganesh, A., Rowstron, A., and Wallach, D. S. (2002). Secure routing for structured peer-to-peer overlay networks. SIGOPS Oper. Syst. Rev., 36(SI):299–314.
Castro, M. and Liskov, B. (2002). Practical Byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398–461.
Cavin, D., Sasson, Y., and Schiper, A. (2004). Consensus with unknown participants or fundamental self-organization. In Proc. of the 3rd Int. Conf. on Ad hoc Networks and Wireless, pages 135–148.
Cavin, D., Sasson, Y., and Schiper, A. (2005). Reaching agreement with unknown participants in mobile self-organized networks in spite of process crashes. Technical Report IC/2005/026, EPFL - LSR.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Dolev, D. (1982). The Byzantine generals strike again. Journal of Algorithms, (3):14–30.
Dwork, C., Lynch, N. A., and Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of ACM, 35(2):288–322.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382.
Greve, F. G. P. and Tixeuil, S. (2007). Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. In Proc. of the Int. Conf. on Dependable Systems and Networks - DSN 2007, pages 82–91.
Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.
Publicado
27/05/2008
Como Citar
ALCHIERI, Eduardo A. P.; BESSANI, Alysson N.; FRAGA, Joni S.; GREVE, Fabíola.
Consenso Bizantino entre Participantes Desconhecidos. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 9. , 2008, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 156-169.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2008.23153.
