Semantically reliable group communication

A utilização de computadores e redes de transmissão de dados em diversas aplicações do quotidiano, torna desejável a adopção de técnicas de tolerância a faltas em sistemas baseados em hardware e software não especializados. A comunicação em grupo é, neste contexto, uma tecnologia particularmente atraente, pois oferece ao programador garantias de fiabilidade que simplificam significativamente a aplicação de técnicas de tolerância a faltas. No entanto, a experiência tem mostrado que a concretização deste modelo em sistemas heterogéneos e de grande escala levanta problemas de desempenho. Embora as limitações de desempenho possam ser evitadas através de um relaxamento das garantias de fiabilidade, os protocolos resultantes são normalmente menos úteis, nomeadamente, na replicação com coerência forte. O desafio reside pois no relaxamento das garantias de fiabilidade sem deixar de oferecer um modelo adequado à programação de aplicações tolerantes a faltas. Esta dissertação estuda modelos e mecanismos que permitem conciliar as vantagens da comunicação em grupo com o elevado desempenho, recorrendo para isso ao enfraquecimento selectivo das garantias oferecidas pelos protocolos. A nossa proposta consiste no uso pelo protocolo de informação sobre a semântica das mensagens, por forma a escolher quais delas têm que ser fiavelmente transmitidas, daí a fiabilidade semântica. Em diversas aplicações, algumas mensagens revogam ou transmitem implicitamente outras mensagens enviadas recentemente, tornando-as obsoletas durante a sua transmissão. Ao omitir apenas as mensagens obsoletas, o desempenho pode ser melhorado sem impacto na correcção da aplicação. São apresentados as especificações e os algoritmos de um conjunto protocolos de comunicação em grupo com fiabilidade semântica, incluindo ordenação e sincronismo virtual. Os protocolos são então avaliados com um modelo analítico, um modelo de simulação e um protótipo. A discussão de uma aplicação concreta ilustra a interface de programação e o desempenho resultanteCurrent usage of computers and data communication networks for a variety of daily tasks, calls for widespread deployment of fault tolerance techniques with inexpensive off-the-shelf hardware and software. Group communication is in this context a particularly appealing technology, as it provides to the application programmer reliability guarantees that highly simplify many fault tolerance techniques. It has however been reported that the performance of group communication toolkits in large and heterogeneous systems is frequently disappointing. Although this can be overcome by relaxing reliability guarantees, the resulting protocol is often much less useful than group communication, in particular, for strong consistent replication. The challenge is thus to relax reliability and still provide a convenient set of guarantees for fault tolerant programming. This thesis addresses models and mechanisms that by selectively relaxing reliability guarantees, offer both the convenience of group communication for fault tolerant programming and high performance. The key to our proposal is to use knowledge about the semantics of messages exchanged to determine which messages need to be reliably delivered, hence semantic reliability. In many applications, some messages implicitly convey or overwrite other messages sent recently before, making them obsolete while still in transit. By omitting only the delivery of obsolete messages, performance can be improved without impact on the correctness of the application. Specifications and algorithms for a complete semantically reliable group communication protocol suite are introduced, encompassing ordered and view synchronous multicast. The protocols are then evaluated with analytical and simulation models and with a prototype implementation. The discussion of a concrete application illustrates the resulting programming interface and performance.Fundação para a Ciência e a Tecnologia - SHIFT (POSI/32869/CHS/2000)