Assignment 3 — Tuple space

In this assignment, you will implement an interprocess communication mechanism and use it for a simple chat system. In the following, "should" is used to denote a weak requirement; something characteristic of a good solution. "must" and "may not" denote strong requirements; failure to achieve these in your own code may cause your assignment to be failed; conversely, you may assume that all requirements on other code marked using these always hold.

Background

You have been assigned to write a prototype for a new platform-independent chat system that is intended to allow users to participate in a conversation from a wide range of devices. To make it easier to balance the load between servers and make the system less dependent on a specific communcations mechanism, your boss has decreed that you use tuple spaces to distribute messages between threads and the various servers in the system. Your job is to implement a basic tuple space system (the design team is still arguing about which tuple space implementation to use) and get the message distribution part of the chat system running.

Task description

Your task is to write a simple tuple space implementation using standard Java synchronisation mechanisms and use it for the message passing part of a simple chat system. These are two separate tasks; your tuple space implementation must work with any compliant chat system implementation and vice versa.

The tuple space implementation must be thread-safe (any method may be called at any time by any thread), but it need not be capable of communication between virtual machines; however, it must be capable of working with this network tuple space proxy and server (see source code for documentation).

Tuple space API

Your tuple space implementation must conform to the following specification (Java source):

All the classes below are in package tuplespaces.

• public class LocalTupleSpace implements TupleSpace
  • public LocalTupleSpace()
    • Create an empty tuple space (a bag of tuples that are represented by String arrays).
• public interface TupleSpace
  • public String[] get(String[] pattern)
    • Remove and return a tuple (an array of entries) matching pattern (which may not be null) from tuple space. Block until one is available. A tuple matches a pattern if both have the same amount of entries and every entry matches. A null entry in the pattern matches any object in that entry in the tuple. Any other object p in the pattern matches any object t in the corresponding entry in the tuple for which p.equals(t) (i.e. contains the same character string). If several matching tuples are found in the tuple space, any one of them may be returned.
    • The returned tuple must have exactly the same textual contents as the tuple that was put (contain the same amount of String objects as the original and each String equals the String in the same position in the original), but may be a different array object and may contain different String objects).
  • public void put(String[] tuple)
    • Insert tuple in tuple space. tuple is an array of any length greater than zero and is not null. tuple may not contain null values. Tuples stored in the tuple space may not be affected by changes made to the tuple array after put has completed.

Chat system

The chat system is based on channels (identified by Strings) to which messages can be sent. It is also possible to listen to a channel. When a listener connects to a channel, the first messages it must receive are the rows last messages (or the total amount sent to the channel, whichever is less) sent to the channel before connection (where rows is a value specified at server startup). After that, the listener must receive all messages sent to the channel since it connected to it, in the order they are sent, until it disconnects from the channel.

The chat server is a distributed system running on multiple nodes (e.g. WWW servers, SMS gateways, TV outputs) connected by a tuple space. All nodes run a Java process containing a ChatServer object which can be used by many threads within the node at once to access the chat system. All nodes share channels; i.e. messages sent on one node must reach listeners to that channel on all other nodes using the same tuple space.

The chat system must conform to the following:

All the classes below are in package chat:

• public class ChatServer
  • public ChatServer(TupleSpace t, int rows, String[] channelNames)
    • Create a new chat server with a set of channels identified by the Strings in channelNames and a buffer of rows messages for each channel (the rows last messages must be sent to new listeners connecting to the channel, if available) in empty tuple space t. Only one channel set may be created in each tuple space. Channel names consist of 1 or more alphabetic characters and are unique and case-sensitive.
  • public ChatServer(TupleSpace t)
    • Connect to a chat server created with the above method using tuple space t.
  • public void writeMessage(String channel, String message)
    • Write message message to channel channel. This call may block if there is no space in the buffer to write the message.
  • public ChatListener openConnection(String channel)
    • Open a listening connection to channel.
  • public String[] getChannels()
    • Return list of channels.
• public class ChatListener
  • You may assume that each ChatListener is used by only one thread.
  • public String getNextMessage()
    • Get the next message from the channel. If no message exists, wait until it appears.
  • public void closeConnection()
    • Disconnect the ChatListener from the channel. After this, the ChatListener may not be used any more.

All parameters above are non-null.

The order of messages on channels must be consistent across the different listeners on a channel (if one message precedes another, it does so for all listeners) and consistent with the order messages are written (if one writeMessage completes before another starts, the message written by the first precedes the message written by the second).

For testing purposes, you can use this simple chat system user interface. To start it, run:

java chatui.ChatUI <host>:<port> [<buffer size> [<channel name 1> [<channel name 2> [...]]]]

<host> and <port> are the host name and TCP port of an active tuple server. Specify the buffer size and channel names to create a new chat server (you may assume that only one chat server is created in each tuple space).

Communication

The chat system must use tuples (and nothing but tuples) to communicate between threads. In other words, the system must be capable of working between machines connected only through the tuple space.

Concurrency and synchronisation requirements

Synchronisation in the tuple space system must be done using nothing but the basic Java synchronisation primitives (those built into the language and java.lang, not java.util.concurrent). Inefficient solutions, such as polling and busy-waiting, will be rejected. Use of unsafe methods such as java.lang.Thread.destroy() will also lead to rejection.

The chat system must use only tuple spaces for synchronisation. Each ChatListener is used by only one thread at a time. However, a ChatServer may be used by multiple threads.

Error handling

To keep this assignment simple, you may ignore many of the errors a tuple space implementation may face. For example, the put and get operations in this simplified implementation may not fail. In a real distributed tuple space implementation, many bad things can happen such as connection failures and timeouts. You may assume that no node is removed from the distributed chat system while an operation is pending or a listener is active (the nodes are all servers on the same corporate net, and if that fails everything breaks anyway).

Throwing exceptions in the case of invalid parameters is recommended but not required.

Style requirements

The program should be written in clear, reasonably object-oriented Java. We will not accept programs that are hard to read, violate basic object-oriented programming principles or contain a large amount of repeated code with minor variations. Cryptic method and variable names should not be used.

Explanatory comments are required for code that is not self-explanatory to a programmer fluent in Java. However, you should not clutter your program by stating the obvious. As an example, Javadoc comments describing the syntax of trivial methods (such as accessors) will be tolerated but are discouraged.

Language (updated on 2007-11-15)

Comments, variable and method names and reports may be written in English, Swedish or Finnish. We recommend that you use only English; if you use Finnish or Swedish, you must specify this when submitting.

Report (added on 2007-11-15)

Your submission must contain a report describing briefly:

• The reasoning behind your solution, in particular:
  • how the message order is kept consistent across listeners
  • how the chat system ensures that messages are not lost or duplicated (for example when a new listener connects to a channel)
• What measures you have taken to ensure your solution is correct (e.g. model checking, proofs, testing).
• Any unexpected behaviour you may have encountered during testing and how you have investigated and resolved it.

The report should not exceed 2 A4 pages of 10-12 point text. Please focus on explaining your reasoning rather than what your solution does in detail.

Hints

• Although it is possible to create a fast tuple matching algorithm using a lot of indexing, this assignment is not about indexing. An algorithm that performs reasonably well in most cases is enough for our purposes. Optimising for your chat implementation is a good idea.
• Testing your tuple space implementation with a lot of concurrent threads putting and getting tuples at once is a very good idea.
• Tuples can easily be used like semaphores, so similar synchronisation techniques apply.
• A chat channel is like a bounded buffer, except it has multiple readers that all get the same data. Test accordingly.
• You can use System.err for debug output. Using System.out is not allowed.
• Use this example code to check your tuple space and chat implementations' interfaces.

Submission

Before the deadline (2007-12-03 23:59, resubmission 2008-03-06 23:59), you must submit a gzipped tar archive containing your solution using the form below. The archive must contain the following files (all other files will be ignored):

tuplespaces/	The Java (version 1.4 or earlier) source code of your tuple space implementation (the directory corresponds to the tuplespaces package).
chat/	The Java (version 1.4 or earlier) source code of your chat system implementation (the directory corresponds to the chat package).
report.pdf	The report describing your solution (as PDF).

Your program will be compiled and run with the standard library and testing code included in the classpath.

You may work in pairs. The grading does not depend on whether you are working alone or in a pair.

Results will be sent to <student number>@students.hut.fi.

Student number 1
Student number 2
File
Language	English
	Finnish
	Swedish
Hours of work required to complete the assignment (total for both students)

Page last updated by Jan Lönnberg 2008-02-21.