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

Abstract

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.