Uso de mensagens em cadeia aplicados no problema do multicast atômico genuíno

Abstract

O multicast atômico provê garantias de entrega e ordem a sub-conjuntos de processos destinatários, sendo um mecanismo fundamental para o provimento de serviços escaláveis com consistência forte. Enquanto muitos algoritmos genuínos de multicast atômico são derivados do algoritmo de Skeen, que usa comunicação de todos para todos processos, temos em outro lado do espectro o protocolo também genuíno de Delporte-Gallet e Fauconnier. Este restringe a direcionalidade da comunicação e é atrativo por sua simplicidade. Sofre porém do efeito comboio. A partir de avaliações de ambos, esta dissertação propõe um protocolo alternativo, com o objetivo de eliminar o efeito comboio de Delporte-Gallet e Fauconnier, contudo abrindo mão da genuinidade em alguns momentos. Este é o primeiro algoritmo multicast atômico parcialmente genuíno que se utiliza de mensagens em cadeia para garantir a ordem global acíclica dentro de um grafo acíclico dirigido. Além disso, uma proposta de aceleração do protocolo é apresentada, de tal modo que, em determinadas cargas de trabalho o algoritmo torna-se totalmente genuíno e com uma alta vazão.

Atomic multicast provides delivery and order guarantees to subsets of recipient processes, being a fundamental mechanism for providing scalable services with strong consistency. While many genuine atomic multicast algorithms are derived from Skeen´s algorithm, which uses communication of all for all processes, we have on the other side of the spectrum the also genuine protocol of Delporte-Gallet and Fauconnier. This restricts the directionality of communication and is attractive for its simplicity. However, it suffers from the convoy effect. Based on evaluations of both, this dissertation proposes an alternative protocol, with the aim of eliminating the convoy effect of Delporte-Gallet and Fauconnier, however giving up genuineness at times. This is the first genuine partially atomic multicast algorithm that uses chain messages to guarantee global acyclic order within a directed acyclic graph. Furthermore, a proposal to accelerate the protocol is presented, such that, in certain workloads, the algorithm becomes completely genuine and with a high throughput.