Garantindo a Circulação e Unicidade do Token em Algoritmos com Nós Organizados em Anel Sujeitos a Falhas

• Luciana Arantes LIP6 / Université de Paris 6 / INRIA
• Julien Sopena LIP6 / Université de Paris 6 / INRIA

DOI: https://doi.org/10.5753/wtf.2010.23093

Resumo

Apresentamos neste artigo um algoritmo que oferece um conjunto pequeno de funções que, quando chamadas por algoritmos distribuídos do tipo token-ring, fazem com que o token utilizado por estes se torne tolerante a falhas. Ele garante assim a circulação e unicidade to token em presença de falhas por parada dos nós. O número máximo de falhas consecutivas toleradas é limitado a k. A perda do token é evitada mantendo-se cópias temporárias deste em k outros nós. O algoritmo é escalável pois um nó monitora no máximo k nós, não necessita de uma eleição de líder, que envolva todos os nós do sistema e nem a utilização de primitivas de difusão para recriar um novo token. Nossa solução para recriá-lo é bastante eficaz em termos de latência. Além disso, se o token armazena alguma informação, esta pode ser mais facilmente restaurada em caso de falha do nó que detém o token.

Referências

Amir, Y., Moser, L. E., Melliar-Smith, P. M., Agarwal, D. A., and Ciarfella, P. (1995). The totem single-ring ordering and membership protocol. ACM Trans. Comput. Syst., 13(4):311–342.

Chang, E. and Roberts, R. (1979). An improved algorithm for decentralized extrema-finding in circular configurations of processes. Commun. ACM, 22(5):281–283.

Chang, I., Singhal, M., and Liu, M. T. (1990). A fault tolerant algorithm for distributed mutual exclusion. In Proceedings of the IEEE 9th Symposium on Reliable Distributed Systems, pages 146–154.

Chang, J.-M. and Maxemchuck, N. F. (1984). Reliable broadcast protocols. ACM Trans. Comput. Syst., 2(3):351–273.

Défago, X., Schiper, A., and Urbán, P. (2004). Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv., 36(4):372–421.

Dijkstra, E. W., Feijen, W. H. J., and van Gasteren, A. J. M. (1986). Derivation of a termination detection algorithm for distributed computations. In Proc. of the NATO Advanced Study Institute on Control flow and data flow: concepts of distributed programming, pages 507–512.

Ekwall, R., A.Schiper, and Urbán, P. (2004). Token-based atomic broadcast using unreliable failure detectors. In SRDS, pages 52–65.

Franklin, R. W. (1982). On an improved algorithm for decentralized extrema finding in circular configurations of processors. Communications of the ACM, 25(5):336–337.

Lann, G. L. (1977). Distributed systems - towards a formal approach. In IFIP Congress, pages 155–160.

Manivannan, D. and Singhal, M. (1994). An efficient fault-tolerant mutual exclusion algorithm for distributed systems. In ISCA International Conference on Parallel and Distributed Computing Systems, pages 525–530.

Misra, J. (1983). Detecting termination of distributed computations using markers. In PODC ’83: Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 290–294.

Mueller, F. (2001). Fault tolerance for token-based synchronization protocols. Workshop on Fault-Tolerant Parallel and Distributed Systems, IEEE.

Nishio, S., Li, K. F., and Manning, E. G. (1990). A resilient mutual exclusion algorithm for computer networks. IEEE Trans. on Parallel and Distributed Systems, 1(3):344–355.

Peterson, G. L. (1982). An O(nlog n) unidirectional algorithm for the circular extrema problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(4):758–762.