Abstract
The importance of distributed systems in current information systems is due to their
potential capabilities to support the growing requirements of increasingly demanding
applications. However, developing distributed applications is not easy. On the contrary,
specic diculties arise as they are devised to oer scalability, fault tolerance
and higher availability. Therefore, it is most useful to count on specic distributed
components that provide, at a lower level, a suit of well{dened services upon which
higher level applications, or other such services, can build up.
This is the case of group oriented services, extensively used by distributed applications,
as they allow them to abstract from the details of communications. Such
services provide basic primitives to achieve one-to-one and one-to-many communications
with specic guarantees. One particular case of them are group membership
services, on which this thesis is focused. Group membership services provide their
users with an image of the set of system processes or machines that are simultaneously
correct and connected. Moreover, the various participants receive this information with
well{dened consistency guarantees. Thus they are a fundamental building block for
group communication services, also useful for other distributed applications.
Although the group membership problem has been largely discussed in the literature
from a theoretical and a practical point of view, and despite the existence of
multiple empirical realisations, there is no unique formulation of the problem. On
the contrary, the characteristics required from a membership service depend on the
particular system for which it is devised. The original specications and implementations
were directed to classical settings, with reduced number of members, and well
behaved connections (typically over LANs). However, with the development of modern
systems, the expansion of the Internet, wireless communications, etc., more dynamic
scenarios have become predominant. For them, the classical distributed services are
not well suited. Dierent membership services have therefore then been dened for
more changing environments.
In this work we focus on the specication and realisation of group membership services
for certain dynamic systems of practical interest for highly available applications.
In particular, we have studied three dierent scenarios.
9
 Systems with well{known topology and moderate size, where partitions are likely
to occur, as could be the case of a system composed of several sites connected
through a WAN with high speed links. For this kind of systems, we have designed
and implemented a partitionable group membership service, HMS, that provides
the most strict classical guarantees plus the property of Uniform Majority View
Agreement to ease the recovery of user applications after a failed member rejoins
the group.
 Large client{server architectures, where a reduced group of servers receive requests
of a large, dynamic set of clients, of a priori unknown identities and number.
For them a Client Membership Service has been specied that provides
clients and servers with the relevant information regarding the opposite group,
so to unify the maintenance of volatile client connections, also in case of core
node faults. This specication has been realised and fully implemented in the
HaloMS protocol, also described in this work.
 Mobile ad hoc networks introduce new challenges to the development of distributed
services. In particular, the energy and bandwidth consumption become
relevant for the design of protocols. For these and other systems with a similar
concern for saving resources we have specied an On Demand Membership
Service, capable of providing strong consistency guarantees only for nite periods
of time, decided as a function of user application requirements. This avoids
the resource consumption derived from agreement rounds and costly recongurations
when no component is making use of membership information. We present
also a realisation of this service in the MODUS protocol, which provides the On
Demand guarantees from a generic membership service.
For the specic scenario of ad hoc networks, in addition, the lack of a priori
knowledge about the topology raises a special diculty for the development of
membership and other agreement based services. To supply this initial information
we have analysed the usage of a membership estimation service in the
epidemic style. Such service will not provide strict consistency guarantees but
will serve as basis for more demanding protocols, e.g. strict group membership.
We have taken into account that such service will be used in conjunction with
routing. Our analysis, based on simulation, studies two possible architectures
that provide both support services, and compares their performance in dierent
scenarios.
This work describes the specication of all these services, and the implementation
of the corresponding protocols. All of them have been fully implemented and are now
available for downloading. Since the goal of this work is to oer a practical support
for the development of applications in the various studied scenarios, all these implementations
t within a more general, modular framework. The latter is characterised
by independent components for each service. These components have clearly dened
interfaces that can be employed by user applications as well as by other services in the
system.