Large scale selective event dissemination

Event-based systems usually denote distributed infrastructures that are used to asynchronously disseminate information among geographically distant computing units. In these systems, the information sources (a.k.a. publishers) produce events and the system delivers these events to destinations (a.k.a. subscribers). Subscribers are "decoupled" from publishers in the sense that they do not need to know each other or even be "up" at the same time. The subscribers can specify the kind of information they like to receive in order not to be flooded with events of all kinds. Depending on the applications, different requirements are imposed on the event-based system. On the one hand, some applications require very strong reliability guarantees while other applications can tolerate a certain percentage of event-losses. On the other hand, while some applications can tolerate large delivery latency, others require latency to be small. In certain cases, it is adequate that the subscribers receive a particular "type" of events irrespective of their actual content. In others, the subscribers like to receive a given type of events with a specific content. The event filtering mechanisms used in these applications need to be decentralized to favor the scalability of the applications. Gossip-based broadcast (also called epidemic) algorithms are particularly appropriate for large scale event dissemination. In these algorithms, processes forward the events they receive to other processes they know of (most of the time in a randomized manner): this continues until all or at least a significant percentage of the processes, receive the events. These broadcast algorithms can be tuned to deliver events according to their type. This is done by mapping a broadcast group to a type. However, more elaborate schemes are necessary to deliver events according to their content. This thesis investigates a number of algorithms that can be used in the context of event dissemination. First, we examine two mechanisms in order to make gossip-based algorithms more reliable for event dissemination. More precisely, we propose a garbage collection technique that can be used to purge events according to their level of dissemination among processes. Furthermore, we introduce an adaptation mechanism to increase the reliability of gossip-based broadcast algorithms. The mechanism controls the amount of events injected into the system and adjusts the broadcast rate according to the buffer resources at processes. Then we discuss how clustering of processes according to their network locality can be useful in delivering events. This clustering mechanism could help to reduce the congestion in network links and also helps to disseminate time sensitive events. Finally, we propose an algorithm to achieve a fine-grained event selection in a completely decentralized environment. To this end, processes use gossip messages to form a structured overlay network and a dictionary based subscription model when joining the overlay.

Towards reliable communication and agreement in mobile ad-hoc networks

David Cavin

During the last decade, the number of wireless devices like digital organizers, mobile phones and laptop computers has drastically increased. At the same time, several technologies, like Bluetooth, GPRS, or WiFi have become mature and offer a high-performance wireless infrastructure to mobile users. However, there exist still many non-equipped areas where no infrastructure is available. For example, during emergency operations, rescuers may want to deploy temporarily an autonomous (or ad-hoc) network. Under these settings, mobile devices (or nodes) operate in a self-organized manner and can only communicate with their immediate wireless neighbors. To send a packet to a remote destination, a node relies on the routing capabilities of the other nodes. In a mobile ad-hoc network (MANET), problems are inherently more complicated to solve than in a regular wired network because of the dynamic topology and the absence of an underlying communication infrastructure. Many algorithms and protocols have been proposed for mobile ad-hoc networks, but very little has been done to evaluate these solutions in real environments. In most cases, algorithms are evaluated by simulation. Such a solution leads however to incorrect conclusions, as we show in the thesis. In order to avoid the shortcomings of simulations, an adequate software framework must be available, in order to ease the development and the deployment of applications or algorithms. We have developed FRANC, a lightweight Java framework dedicated to the implementation of real ad-hoc applications. FRANC is composed of an extensible library of building blocks that can be composed to build more complex applications. The thesis is not limited to practical contributions. We have also addressed two important problems that are at the root of many other distributed computing algorithms. Although extensively studied in wired networks, this research domain is however still in its early stages in MANETs. We first propose a simple broadcast protocol that disseminates efficiently and reliably a message in a one dimensional graph like a car highway. Then, we study the consensus problem and identify the necessary and sufficient conditions for solving it in self-organized networks when the participants are unknown (in the absence of crashes). Finally, we discuss a pragmatic solution to consensus with crashes based on weak ordering oracles. More specifically, we propose an implementation of these oracles and present results collected in a real small-scale wireless testbed.

EPFL2006

Type-based event dissemination

Sébastien Bähni

With the explosion of broadband Internet connections in the late 80s, new types of applications, called distributed applications, came to light. These applications typically seek to provide a user with remote services that appear to that user as if they were local. For instance, when a user browses the Internet, web pages are downloaded from different servers and are displayed on the screen of the client's computer as if they were directly available on the computer itself. Typically one distinguishes two kinds of actors in such applications: clients, searching for information, and servers, providing the information. Furthermore, there are generally two models of interaction according to which these actors exchange information. In the first model, the client requests specific information and waits until the server replies to it. In the second model, the client registers its interests in some information with a set of servers and is notified when new information is available. Both models have their advantages and disadvantages but the second has obvious asynchrony benefits in a large-scale system in which it is very difficult to know the time taken to answer a request. The second model is usually encapsulated within the celebrated publish/subscribe abstraction. According to this abstraction, clients are either subscribers which express interest in specific information, or publishers which create and send pieces of information usually transmitted in the form of events (e.g., as HTML pages or plain data). The subscriber does not need to know a publisher or to be on-line with it to receive its published events. These properties are sometimes refer to as space and time decoupling respectively. Newsgroups are the most well known example of publish/subscribe system. While indeed appealing, the publish/subscribe abstraction is not easy to implement effectively. There are at least two challenging issues: (1) the representation of the events and (2) their dissemination on a large-scale or in a mobile environment. Events are usually transferred as XML messages or byte arrays. The system must therefore transform events into pieces of software implemented in its underlying language (e.g., Java, C#) before handling them. In addition, the reliable dissemination on a large-scale or in a mobile environment is not trivial, especially as in practice it is necessary to minimize the number of duplicates and parasite events (i.e., events of no interest) to save bandwidth and processing power. We focus in this thesis on devising and implementing algorithms which address the above two issues in publish/subscribe systems implemented in object-oriented languages (e.g., Java, C#) and such that the events that are transferred between the different actors correspond to serialized objects. These systems are also called type-based publish/subscribe systems. We first present techniques to detect events of interest and throw away parasite events. We show that these techniques are of major use for reliably disseminating events either on a large-scale or in a mobile environment without flooding the network. Finally, we illustrate type interoperable rules that let instances of two different types, but still representing the same entity, to be used indistinguishably. Together with the algorithms, we exhibit implementation prototypes and performance measures conducted over them.

EPFL2006

Protocol composition frameworks and modular group communication

Sergio Mena

It is noticeable that our society is increasingly relying on computer systems. Nowadays, computer networks can be found at places where it would have been unthinkable a few decades ago, supporting in some cases critical applications on which human lives may depend. Although this growing reliance on networked systems is generally perceived as technological progress, one should bear in mind that such systems are constantly growing in size and complexity, to such an extent that assuring their correct operation is sometimes a challenging task. Hence, dependability of distributed systems has become a crucial issue, and is responsible for an important body of research over the last years. No matter how much effort we put on ensuring our distributed system's correctness, we will be unable to prevent crashes. Therefore, designing distributed systems to tolerate rather than prevent such crashes is a reasonable approach. This is the purpose of fault-tolerance. Among all techniques that provide fault tolerance, replication is the only one that allows the system to mask process crashes. The intuition behind replication is simple: instead of having one instance of a service, we run several of them. If one of the replicas crashes, the rest can take over so that the crash does not prevent the system from delivering the expected service. A replicated service needs to keep all its replicas consistent, and group communication protocols provide abstractions to preserve such consistency. Group communication toolkits have been present since the late 80s. At the beginning, they were monolithic and later on they became modular. Modular group communication toolkits are composed of a set of off-the-shelf protocol modules that can be tailored to the application's needs. Composing protocols requires to set up basic rules that define how modules are composed and interact. Sometimes, these rules are devised exclusively for a particular protocol suite, but it is more sensible to agree on a carefully chosen set of rules and reuse them: this is the essence of protocol composition frameworks. There is a great diversity of protocol composition frameworks at present, and none is commonly considered the best. Furthermore, any attempt to defend a framework as being the best finds strong opposition with plenty of arguments pointing out its drawbacks. Given the complexity of current group communication toolkits and their configurability requirements, we believe that research on modular group communication and protocol composition frameworks must go hand-in-hand. The main goal of this thesis is to advance the state of the art in these two fields jointly and demonstrate how protocols can benefit from frameworks, as well as frameworks can benefit from protocols. The thesis is structured in three parts. Part I focuses on issues related to protocol composition frameworks. Part II is devoted to modular group communication. Finally, Part III presents our modular group communication prototype: Fortika. Part III combines the results of the two previous parts, thereby acting as the convergence point. At the beginning of Part I, we propose four perspectives to describe and compare frameworks on which we base our research on protocol frameworks. These perspectives are: composition model (how the composition looks like), interaction model (how the components interact), concurrency model (how concurrency is managed within the framework), and interaction with the environment (how the framework communicates with the outside world). We compare Appia and Cactus, two relevant protocol composition frameworks with a very different design. Overall, we cannot tell which framework is better. However, a thorough comparison using the four perspectives mentioned above showed that Appia is better in certain aspects, while Cactus is better in other aspects. Concurrency control to avoid race conditions and deadlocks should be ensured by the protocol framework. However this is not always the case. We survey the concurrency model of eight protocol composition frameworks and propose new features to improve concurrency management. Events are the basic mechanism that protocol modules use to communicate with each other. Most protocol composition frameworks include events at the core of their interaction model. However, events are seemingly not as good as one may expect. We point out the drawbacks of events and propose an alternative interaction scheme that uses message headers instead of events: the header-driven model. Part II starts by discussing common features of traditional group communication toolkits and the problems they entail. Then, a new modular group communication architecture is presented. It is less complex, more powerful, and more responsive to failures than traditional architectures. Crash-recovery is a model where crashed processes can be restarted and continue where they were executing just before they crashed. This requires to log the state to disk periodically. We argue that current specifications of atomic broadcast (an important group communication primitive) are not satisfactory. We propose a novel specification that intends to overcome the problems we spotted in existing specifications. Additionally, we come up with two implementations of our atomic broadcast specification and compare their performance. Fortika is the main prototype of the thesis, and the subject of Part III. Fortika is a group communication toolkit written in Java that can use third-party frameworks like Cactus or Appia for composition. Fortika was the testbed for architectures, models and algorithms proposed in the thesis. Finally, we performed software-based fault injection on Fortika to assess its fault-tolerance. The results were valuable to improve the design of Fortika.

EPFL2006

Towards reliable communication and agreement in mobile ad-hoc networks

David Cavin

EPFL2006

Type-based event dissemination

Sébastien Bähni

EPFL2006

Protocol composition frameworks and modular group communication

Sergio Mena

EPFL2006