Course Project
In this project, groups consisting of 2(-3) (two students as far as possible, a single group may be allowed to be three) students are to design and implement a group communication middleware.Introduction
A distributed system is 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:
A middleware is a software layer that abstracts and hides the heterogeneity of underlying networks, operating systems, and programming languages. Examples include CORBA [DS5: 8.3] and Java RMI (see ZIP with example from tutorial [DS5: 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 implement some API that in turn can be used by programmers to develop applications that make use of reliable messaging. GCom must support various types of multicast, guarantee causal message ordering and handle group membership issues.
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 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:
In a static group the structure of the group is predefined and
only group members can join the group.
Until all members have joined no member can send data messages to the group.
Once the group is established,
message sharing can begin and no new members can join (or re-join) the group.
The group management module must however be able to handle
that members may leave static groups at any time (due to crashes).
In contrast,
in dynamic groups members may join and leave the group at any time.
Processes that re-join the group may be handled as any other joining process.
The four main tasks of the group management module are:
Consider the following issues when designing the group management module:
The requirements for the reliable tree-based multicast are simply as follows:
Hybrid message orderings add extra ordering requirements.
For example, in Causal-Total messages are
first sorted according to causal ordering then according to total ordering.
Total ordering combined with reliable multicast is also referred to as
atomic multicast and is often used for replication and transactions.
The GCom middleware must be able to deliver messages according to
unordered (i.e., as they arrive) and causal orderings.
Note that GCom must be able to deliver messages using either ordering and
all types of communication mechanisms that you implement,
basic non-reliable, basic reliable multicast, and
tree-based reliable multicast if you aim for the bonus points.
Recommended reading: DS5: 15.4.3
Note that it is perfectly fine to let the test and debug application be
one and the same application, although it is nicer from a
software engineering point of view if you keep them separated logically.
You have to agree that regular users do not want to get a full debugging
view when they start a program,
so if you make a combined test and debug application,
at least keep the functionality separated so
the debug view can be enabled upon request, rather than always enabled.
Your test application will (together with your debug utility)
be used during your practical demonstration of this project.
It is hence paramount that you not only implement GCom,
but also clearly are able to demonstrate that your implementation is correct.
This should be obvious,
as you probably want to convince yourselves that your solution is correct
before attempting to convince the teachers.
The debug utility and test application (combined) must
clearly demonstrate at least:
As middleware-development is part of the course focus,
you are not allowed to implement GCom using TCP/IP sockets.
More specifically:
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 be able 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.
Communication Module
Processes in a group can communicate via various mechanisms.
The creator of a group specifies which communication mechanism to use
for all data messages in that group.
GCom must support the following mechanisms:
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 most common ordering requirements are:
Testing and Demonstration
In order to ensure the correctness of the GCom middleware,
you must implement a chat application.
You must also implement a debug application that allows you to
simulate dropped, rearranged, or delayed packages,
as this will allow you to test whether your message ordering module and
reliable multicast modules are working correctly.
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.
Advice
Some helpful hints:
Project Requirements
The mandatory features that must be implemented are.
- Group management for dynamic groups
- Basic non-reliable multicast
- Unordered and Causal message ordering
- Debug application that clearly demonstrates the correctness of GCom
- Test application
In addition, you must demonstrate your solution to us and hand in a complete report fulfilling the requirements as described below.
Bonus Points
Everything on the mandatory part + Tree-based reliable multicast. In order to obtain the bonus points, all features from the mandatory part must work correctly. If you decide to work on this part of the project, make sure that you and your partner have the same ambitions and goals for this project. If you attempt to solve it, you must come by our office and explain your approach. Bring your idea in writing (images preferred). This is to avoid misunderstandings that end up costing your group important time that would be better spent testing and maintaining your obligatory code.Deliverables
As an aid in planning your work, we divided the project into two deliverables. Read both the specification and suggested literature carefully before starting to work on deliverableDeliverable 1 - Analysis and Design (Optional)
This deliverable is optional but we encourage you to do it since we can offer you feedback about your overall plan and design. If you decide to work on this deliverable, you must include at least the following sections:
Deliverable 2 - Implementation and Full Report
Please note that you can base the full report on the first analysis and design document, which means that a good first report will make the full report easier to complete! It is a strong requirement that your system can easily be started from a Unix terminal. If you have a complicated command line, please include the appropriate scripts for each component. See, e.g., bash scripting tutorial for a quick guide on scripting.Deadlines
Deliverable deadlines are found in the course schedule. Keep in mind the policy for late submissions. The project consists of two or three hand-ins:Demonstration
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 protocol should include tests for a combination of message orderings and all multicast types that you implement. Bring a copy of the test protocol on paper, see [DS5: 668] for suggested notation. Your test protocol must clearly state your names, user names, and what level you intend to demonstrate.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, just for the sake of it – at this point in your education, you are more than able to decide what parts are important and what could be left out. 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, as well as to which extent you could adhere to the project plan. Finally, remember that GCom is a general middleware, which just so happens to be used by a chat application for the project, this means that it is important to document how one would use it to develop other applications requiring group management and group communication.
Try to maintain a focus on readability while writing the report.
Make the description of your system as clear as possible, and
consider your report’s 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
(for the Latex crowd, use "aspell -lang=en_US -c filename.tex
",
nice typesetting does not make spelling mistakes less of a distraction),
and yes, the report must be written in English.
To make it easier for us to test your implementation, state the complete command line required to execute your solution on the front page of the report.
Final Note
Remember, you need to get at least 50 points on the aggregate of all projects to pass the course. Any bonus points from the assignment can only be used to get a higher grade once you pass. Furthermore, any bonus points obtained only count during the four exams offered for the course during the next 12 months, not for later offerings of the course.References
Examination
The course project is to be addressed in groups of 2(-3) students. Place all files pertaining to your solution in
~/edu/5dv186/project/
Source code should be placed in
~/edu/5dv186/project/src/
The project report should be placed in
~/edu/5dv186/project/report/