Fast Adaptable Uniform Consensus Using Global State Digests
Resumo
Protocols that solve the consensus problem have been widely recognized as important building blocks for the design of reliable distributed systems. This fact explains why considerable amount of work has been devoted both to establish the minimal system requirements that allow a solution to the problem, as well as to provide efficient protocols to solve it. We propose the use of global state digests to design efficient and adaptable consensus protocols. A global state digest is a bounded and consistent summarized representation of the local states of all processes that run the protocol. By frequently providing processes with new global state digests, it is possible to allow processes to terminate the protocol soon after the minimal condition necessary to solve the problem holds, whatever are the contention levels experienced by the system. We present the design of a family of fast adaptable consensus protocols using this abstraction. Further, a global state digest provider can be implemented whenever the same assumptions required to implement perfect failure detectors hold (basically the ability to convey a bounded amount of information within a bounded interval of time).
Palavras-chave:
agreement protocols, perfect failure detection, consistent global state, synchronous and asynchronous distributed systems, wormholes
Referências
AGUILERA, M. K., LANN, G. L., AND TOUEG, S. On the impact of fast failure detectors on real-time fault-tolerant systems. In 16 th International Symposium on Distributed Computing (DISC 2002) (Tolouse, France, October 2002), pp. 354–369.
BRASILEIRO, F. V., GREVE , F., MOSTEFAOUI, A., AND RAYNAL, M. Consensus in one communication step is possible. Research Report 1321, INRIA, 2001.
BRITO, A., AND BRASILEIRO, F. Programando um subsistema síncrono para suporte a mecanismos eficientes de tolerância a falhas. In Workshop de Tolerância a Falhas (2004).
BRITO, A., AND BRASILEIRO, F. A cheap and safe cots wormhole for local area network. In Proceedings of the 10th IEEE Workshop on Dependable Parallel, Distributed and Network-Centric Systems (DPDNS’05) (2005).
CHANDRA, T., AND TOUEG, S. Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43, 2 (Mar 1996), 225–267.
CHANDRA, T. D., HADZILACOS, V., AND TOUEG, S. The weakest failure detector for solving consensus. Journal of the ACM 43, 4 (Jul 1996), 685–722.
CRISTIAN, F., AGHILI, H., STRONG, R., AND DOLEV, D. Atomic broadcast: from simple message diffusion to Byzantine agreement. In Proceedings of the 15 th IEEE International Symposium on Fault-Tolerant Computing (FTCS’85) (Ann Arbor, Jun 1985), pp. 200–206.
DOLEV, D., DWORK, C., AND STOCKMEYER, L. On the minimal synchronism needed for distributed consensus. Journal of the ACM 34, 1 (Jan 1987), 77–97.
DUTTA, P., AND GUERRAOUI, R. Fast indulgent consensus with zero degradation. In Proceedings of the 4th European Dependable Computing Conference (EDCC4) (Toulouse, France, Oct 2002).
DWORK, C., LYNCH, N. A., AND STOCKMEYER, L. Consensus in the presence of partial synchrony. Journal of the ACM 35, 2 (Apr 1988), 288–323.
FISCHER, M. J. The consensus problem in unreliable distributed systems. Research Report 273, Yale University, Jun 1983.
FISCHER, M. J., LYNCH, N. A., AND PATERSON, M. D. Impossibility of distributed consensus with one faulty process. Journal of ACM 32, 2 (Apr 1985), 374–382.
HURFIN, M., AND RAYNAL, M. A simple and fast asynchronous consensus protocol based on a weak failure detector. Distributed Computing 12, 4 (1999), 209–223.
MOSTEFAOUI, A., AND RAYNAL, M. Solving consensus using chandra toueg’s unreliable failure detectors: a general quorum based approach. In Proceedings of the 13 th International Symposium on Distributed Computing (DISC’99) (Bratislava, Slovaquia, Sep 1999), pp. 49–63.
SAMPAIO, L. M. R., BRASILEIRO, F. V., DA C. CIRNE, W., AND DE FIGUEIREDO, J. C. A. How bad are wrong suspicions? towards adaptive distributed protocols. In Proceedings of the International Conference on Dependable Systems and Networks (DSN’2003) (San Franciso, California, USA, June 2003), pp. 551–560.
SCHIPER, A. Early consensus in an asynchronous system with a weak failure detector. Distributed Computing 10, 3 (Apr. 1997), 149–157.
VERÍSSIMO, P. Uncertainty and predictability: Can they be reconciled? Future Directions in Distributed Computing, Springer Verlag LNCS 2584 (May 2003), 108–113.
VERÍSSIMO, P., AND C ASIMIRO , A. The Timely Computing Base model and architecture. Transactions on Computers - Special Issue on Asynchronous Real-Time Systems 51, 8 (Aug. 2002).
BRASILEIRO, F. V., GREVE , F., MOSTEFAOUI, A., AND RAYNAL, M. Consensus in one communication step is possible. Research Report 1321, INRIA, 2001.
BRITO, A., AND BRASILEIRO, F. Programando um subsistema síncrono para suporte a mecanismos eficientes de tolerância a falhas. In Workshop de Tolerância a Falhas (2004).
BRITO, A., AND BRASILEIRO, F. A cheap and safe cots wormhole for local area network. In Proceedings of the 10th IEEE Workshop on Dependable Parallel, Distributed and Network-Centric Systems (DPDNS’05) (2005).
CHANDRA, T., AND TOUEG, S. Unreliable failure detectors for reliable distributed systems. Journal of the ACM 43, 2 (Mar 1996), 225–267.
CHANDRA, T. D., HADZILACOS, V., AND TOUEG, S. The weakest failure detector for solving consensus. Journal of the ACM 43, 4 (Jul 1996), 685–722.
CRISTIAN, F., AGHILI, H., STRONG, R., AND DOLEV, D. Atomic broadcast: from simple message diffusion to Byzantine agreement. In Proceedings of the 15 th IEEE International Symposium on Fault-Tolerant Computing (FTCS’85) (Ann Arbor, Jun 1985), pp. 200–206.
DOLEV, D., DWORK, C., AND STOCKMEYER, L. On the minimal synchronism needed for distributed consensus. Journal of the ACM 34, 1 (Jan 1987), 77–97.
DUTTA, P., AND GUERRAOUI, R. Fast indulgent consensus with zero degradation. In Proceedings of the 4th European Dependable Computing Conference (EDCC4) (Toulouse, France, Oct 2002).
DWORK, C., LYNCH, N. A., AND STOCKMEYER, L. Consensus in the presence of partial synchrony. Journal of the ACM 35, 2 (Apr 1988), 288–323.
FISCHER, M. J. The consensus problem in unreliable distributed systems. Research Report 273, Yale University, Jun 1983.
FISCHER, M. J., LYNCH, N. A., AND PATERSON, M. D. Impossibility of distributed consensus with one faulty process. Journal of ACM 32, 2 (Apr 1985), 374–382.
HURFIN, M., AND RAYNAL, M. A simple and fast asynchronous consensus protocol based on a weak failure detector. Distributed Computing 12, 4 (1999), 209–223.
MOSTEFAOUI, A., AND RAYNAL, M. Solving consensus using chandra toueg’s unreliable failure detectors: a general quorum based approach. In Proceedings of the 13 th International Symposium on Distributed Computing (DISC’99) (Bratislava, Slovaquia, Sep 1999), pp. 49–63.
SAMPAIO, L. M. R., BRASILEIRO, F. V., DA C. CIRNE, W., AND DE FIGUEIREDO, J. C. A. How bad are wrong suspicions? towards adaptive distributed protocols. In Proceedings of the International Conference on Dependable Systems and Networks (DSN’2003) (San Franciso, California, USA, June 2003), pp. 551–560.
SCHIPER, A. Early consensus in an asynchronous system with a weak failure detector. Distributed Computing 10, 3 (Apr. 1997), 149–157.
VERÍSSIMO, P. Uncertainty and predictability: Can they be reconciled? Future Directions in Distributed Computing, Springer Verlag LNCS 2584 (May 2003), 108–113.
VERÍSSIMO, P., AND C ASIMIRO , A. The Timely Computing Base model and architecture. Transactions on Computers - Special Issue on Asynchronous Real-Time Systems 51, 8 (Aug. 2002).
Publicado
09/05/2005
Como Citar
BRITO, Andrey; BRASILEIRO, Francisco; CIRNE, Walfredo.
Fast Adaptable Uniform Consensus Using Global State Digests. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 6. , 2005, Fortaleza/CE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2005
.
p. 85-96.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2005.23373.
