Introduction

A distributed system is a system composed of group(s) of processes that coordinate their activities by exchanging messages over a network. For such systems, pair-wise exchange of messages need not be the most efficient or reliable way to communicate. Multicast is an operation that sends a message from one process to a group of processes. This is typically achieved without the sending process having explicit knowledge of the group members. Common applications include, but are not limited to:

Replication-based fault-tolerance: A replicated service is composed of multiple servers forming a group. Client requests are treated by all servers, allowing some servers to crash without affecting the availability of the service.
Ad-hoc network service discovery: Multicast messages are used by clients to discover, and register to, services.
Replication for high-performance data access: Commonly used data are replicated locally for performance improvements. Updates to data replicas are propagated using multicast-messages.
Propagation of event messages

A middleware is a software layer that abstracts and hides the heterogeneity of underlying networks, operating systems and programming languages. Examples include CORBA [DS4,5,20] and Java RMI [DS:5.5], although the latter merely supports a single programming language. In addition to solving the heterogeneity problem, a middleware provides a model for distributed communication, e.g., remote method invocation and remote event notification. CORBA and Java RMI implement the former approach, i.e., a program can invoke a method in an object located on another computer.

The goal of this project is to design and implement GCom, a middleware for group communication. The middleware must be provided as an API to be used by programmers to development applications that makes use of reliable messaging. GCom must support various types of multicast, guarantee different types of message ordering and handle group membership issues. The middleware need however not support more than one programming language.

Group membership management is a complicated problem and has been the focus of much research. For this project, we will accept simplified solutions to the group membership problem and instead focus on the multicast types and message ordering algorithms.

The project must be solved individually by groups of two students.

Purpose

The overall aim of this project is to increase your knowledge of distributed systems and distributed programming. More specific goals include:

Understanding of different communication types, their characteristics and scenario suitability.
Understanding of different message ordering algorithms, their characteristics and effects.
Understanding of system architecture design impact, with special focus on differences between centralized and distributed solutions.
Development of software engineering skills. practice in the ability to make a loosely specified problem concrete, design a solution and implement the design.
Development of written communication skills.

Description

The GCom middleware consists of three (logical) modules, the group management module, the communication module and the message ordering module. These are, respectively, responsible for handling group membership issues, communication message exchange semantics and message (re)ordering issues. All of these modules need to function properly in order for your system to ensure correct message delivery semantics.

Group management module

In order to send messages to the processes in a group, GCom must keep track of the members of a group. This can be done either statically or dynamically. In a static group, no new members can join once the group is established. The group management module must however be able to handle that members may leave static groups at any time (due to crashes). In dynamic groups, members may join and leave the group at any time. The four main tasks of the group management module is:

To provide an interface for group management: The group management module provides operations to create and remove groups, as well as add and remove members from a group.
To detect errors: The module monitors a group and indicates when a member of the group crashes (or for some other reason become unreachable).
To notify changes in group membership: The module notifies all group members about changes in group composition.
To resolve group names: When a process sends a message to the group, the group management module resolves the group name into a list of group members.

Consider the following issues when designing the group management module:

Scalability, e.g., is it suitable to keep a complete list of all groups in each process?
Limitations, e.g., can your group management module handle all types of errors? What can the system not guarantee?
Partitioning: What happens if the group is partitioned, e.g., due to a network segmentation?

Communication module

Processes in a group can communicate via various mechanisms. The sender of a message specifies which communication mechanism to use. GCom must support the following mechanisms:

Basic non-reliable multicast.
Basic reliable multicast.
Tree-based reliable multicast (bonus level).

For the tree-based multicast algorithm, read about multicast routing, e.g., in [DK:4.7.2]. For reliability issues regarding tree-based multicast, see e.g. IP-multicast described in [DS:12.4.2].

Message ordering module

Various types of delays in networks and computers may cause reordering of messages in a process, e.g., the reply to a certain request may, in some process, arrive before the request. For some applications, this type of behavior is unacceptable. The GCom middleware must be able to deliver messages according to the following orderings:

Non-ordered
FIFO
Causal
Total
Causal-Total

The definition of total ordering is that messages may be delivered in arbitrary order, as long as all processes in a group deliver the messages in exactly the same order. Hybrid message orderings such as FIFO-Total add extra ordering requirements. Total ordering combined with reliable multicast is also referred to as atomic multicast, and is often used for replication and transactions.

Test application

In order to ensure the correctness of the GCom middleware, you must implement a test application based on the GCom API. This application should test the general functionality of GCom as well as estimate its performance. The test application must clearly demonstrate:

That messages are delivered according to the specified ordering: A debug-mode where messages can be delayed is useful for this purpose.
How messages are propagated in the network: Show both the path a message takes and how many times a certain process has received a certain message.
The content of hold-back queues and other buffers: Present all messages waiting to be sent or delivered as well as values of vector clocks and other counters.
Current system performance: As a measure of the system performance, count the number of messages (including control messages) required to perform an operation (send one message with certain ordering + multicast).

clearly

Tools

You are free to use any tools you want for this project, in fact, selection of appropriate tools is considered part of the assignment. You will however have to motivate your choice of tools with respect to, and in terms of, what you expect to learn from this course and project. If you find a tool (there exists quite a few) that solves the assignment with little or no effort from your side, you are naturally not allowed to use it. (One such tool is for example JGroup) You are of course allowed to use documentation and research papers from existing solutions when designing GCom. As middleware-development is part of the course focus, you are not allowed to implement GCom using TCP/IP sockets.

Advice

Some helpful hints:

Design and implement GCom modularly to simplify the combination of message orders and multicast types, this is useful, e.g., when constructing hybrid message orders.
Integrate testing and implementation. Test separate modules as the are implemented. Early unit testing makes it easier to detect, and limit effects of, bugs. Also perform integration testing to ensure correctness in inter-module communication.
Read the algorithms in [DS] carefully and consider what data structures are required to implement them. The algorithms in [DS] are described using a high level of abstraction, and cannot be implemented as is.
The fact that a system cannot be formally proven to work does not make it impossible to implement - consider for example the Internet. Read pages 498 and 508 in [DS].
Analyze (and reanalyze) your design before you start implementing it!

Bonus points

This project is divided into three levels and each student group chooses which level of functionality to implement themselves. Solving a higher level may award bonus points to the exam. In order to receive bonus points your project must be graded G. It is also possible to get the points if you get a K or O, if all errors are resolved on the subsequent hand-in. See Bonus points for more information.

Level 1

This level is mandatory for all project groups. The following must be implemented and demonstrated:

Group management for static groups
Basic non-reliable multicast
Basic reliable multicast
All message ordering algorithms
Test application that clearly demonstrates the correctness of GCom

Level 2

Everything on level 1 and:

Management of dynamic groups

must

Level 3

Everything on level 2 and:

Tree-based reliable multicast

must

Deliverables

As an aid in planning your work, this project is divided into two deliverables. Read both the specification and the suggested literature carefully before starting to work on deliverable 1.

Deliverable 1 - Analysis and Design

Analyze the problem. What should be done, and what problems needs to be solved? Formulate a list of GCom requirements, based on the problems you identify. What must be implemented, and what may be implemented, time permitting? See [RFC 2119] for suggestions on how to write a requirement list. The first deliverable should also include the bonus point level you are aiming for.
Identify suitable tools. Is there an existing middleware or third party component that should be used? Learn the benefits and drawbacks of possible choices by implementing a test application before choosing. The sooner you learn the limitations of a technology you use, the better.
Motivate your choice of technology. What made you choose that particular middleware? Why did you choose it? Reflect upon the aspects covered in the lecture about middleware.
Design a solution. Write a detailed design for your solution. Try to implement conceptual parts of the design to convince yourself that it is feasible. Having a sound, modular design is important. Your design should be detailed enough to not need any major additions during implementation. Minor modifications are allowed of course - even the most carefully designed system may require changes due to unforseen properties of the used tools.

Deliverable 2 - Implementation

Hand-ins

The project consists of four hand-ins:

Written hand-in of deliverable 1.
Demo of your system.
Written hand-in of deliverable 2 (complete report).
Any additional hand-ins of steps 1 - 3.

Demo

During your demo, you will need to convince the teachers that your implementation works. Bring a test protocol, i.e., a series of tests that clearly demonstrates that your GCom fulfills the requirements and a test tool which can be used to apply it. The test protocol should include, e.g., tests of all message orders and multicast types. Bring a copy of the test protocol on paper, see page 491 in [DS] for suggested notation.

Report

A written presentation of your results is an important part of the project. This is true not only for this project, but in virtually any software development process. People lacking the skills required to communicate the results of their work (verbally and in writing) will find it difficult to work in the software industry. The purpose of the report is hence not to make the teachers happy, but to improve your communication skills.

Try to focus on the specific characteristics of this project when you write the report. Do not follow some predefined outline from some previous course for the report. As this project emphasizes analysis and investigation of a loosely specified problem, include any assumptions you made during the analysis phase in your report. Also discuss problems encountered and alternative solutions considered in the analysis. The report should also discuss to what extent the requirement list is fulfilled.

Try to maintain a focus on readability while writing the report. Make the description of your system as clear as possible, and consider your reports level of detail. Your report is the first impression users (and teachers) get of your system. Ensure that figures and diagrams are easy to read. Proof-read your report carefully and use spelling-checking tools.

Dates

Important dates:

Project presentation: September 7 2007 (11.45)
Deadline deliverable 1: September 19 2007 (23:59)
Review and handout of deliverable 1: September 21 2007 (11:45)
Demo: October 22 2007 (exact time to be announced later)
Deadline deliverable 2: October 24 2007 (23.59)
Additional hand-ins: determined individually

References

[DS] Coulouris G., Dollimore J. and Kindberg T.: Distributed Systems - Concept and Design. Fourth edn. Addison Wesley (2005)
[DK] Kurose J.F. and Ross K.W.: Computer Networking - A Top-Down Approach Featuring the Internet. Third edn. Addison Wesley (2005)