Update

• Added clarification to Javadoc for ConcurrentPublisher.removeObserver. It was mentioned in the description below, but not the API documentation.
• Project deadline is now 4/19 (rather than 4/15).
• Parts 3 and 4 will be part of project 6.

Overview

This project is to develop infrastructure for a distributed gaming system. One central site, called the state server, will maintain the global state of a given game, such as the game map, player positions, etc. Each player will also be running a program, the player server, that has its own copy of the state. There are many interesting challenges in maintaining consistent copies of that state throughout the distributed environment.

The project can be divided into four conceptual components. In this project you will implement two of them; the remaining two will be implemented in project 6. Here are the four parts:

1. Concurrent Observer pattern. Every time a player modifies the game state, it will notify the state server. Assuming this change of state is legal, the server will then notify all the player servers of the change. This notification process is essentially a form of the observer pattern, but we will generalize things a bit so that updates can take place concurrently.
2. Transactional State. While there is conceptually a single shared state managed by the state server, the player servers have their own copies for performance reasons. They can make changes to their local copies and then attempt to "commit" the changes to the state server, similar to database transactions. This reduces synchronization overhead and delays under the optimistic assumption that commits usually succeed. This will be true if players are operating in different places of the game map at different times. For the second part of 5a, you will implement a transactional BooleanGrid abstraction to represent a game map.
3. Concurrent communication patterns. With transactional state in hand, you will implement the communication patterns for maintaining and updating state within a multi-threaded context. There will be one thread for the state server, and one thread to represent each player server.
4. Distributed communication. With multithreaded player support in place, you must extend the code to actually work with distributed messages. This is done by creating "stubs" and "skeletons" to encapsulate the communication between processes, in the style of RMI (but you will implement it "by hand").

We have provided you with an detailed specification for this project. We have left much of the design and implementation details up to you.

1. Concurrent Observer

A concurrent observer differs from a sequential one in two ways. First, your code should be thread-safe: multiple threads may attempt to call the Observable's methods at the same time, and interference must be prevented. Second, the Observable should always make progress, whereby delays publishing to one observer do not affect publishing to another observer. Since you will use concurrency to achieve this, be aware that messages should be published to observers in a serial fashion. If messages A and B are given to the observable in this order, then they should be received at the observers in the same order. See the documentation on ConcurrentPublisher for further details.

We impose several restrictions on your implementation of ConcurrentPublisher. First, you should delegate thread safety issues to thread-safe classes from java.util.concurrent in the Java API, rather than trying to do it "manually." In particular, you should not use the following (with one exception, see below):

• synchronization (e.g., synchronized blocks and wait/notify),
• any classes from java.util.concurrent.locks or java.util.concurrent.atomic, or
• the class java.util.concurrent.Semaphore

You should strive to make all of your code non-blocking, so that one thread is never required to wait in your code for another thread to complete something. There is one exception to this rule that is documented in the specification. Specifically, when you remove an observer by calling removeObserver, this operation should block until all messages (values) have been published to that observer. You may use synchronization (e.g., classes from java.util.concurrent.locks) to implement this requirement.

As with Project 4, we have provided you with a framework (in threadController.jar) for writing multithreaded test cases. You can again see an example of using this framework in PublicTests. You should use this framework when writing your StudentTests.

Study the Java 1.5/5.0 API documentation, especially the allowed classes under java.util.concurrent, in detail. Chances are something you think isn't there is actually there.

The finer details of this project are much trickier than you may suspect. Remember, you are not allowed to use synchronization. Now imagine what sequence of code executions could happen if one thread is deleting an observer, while another thread is adding an observer, and yet another thread is sending a message to all observers except the one that's currently being deleted. There will be some synchronization in the underlying Java API data structures you employ, but you still have to plan and think very carefully that not only is progress made, but also that progress is made in a consistent and correct fashion.

2. Transactional State

Rather than implement a realistic global state for a game (the terrain, the locations of each of the players, the weapons they have, etc.), we will implement a much-simplified "boolean grid." The idea is that each player server will make modifications to its own copy of the grid based on the actions of its own players, and then attempt to update the global state with these changes.

This works through the interaction of implementations of two interfaces:

public interface TransactionalState {
  public TransactionKey newTransaction(T command);
}
public interface TransactionKey {
	boolean beginTransaction() throws IllegalTransactionStateException;
	void endTransaction() throws IllegalTransactionStateException;
}

You will write a BooleanGrid class to implement the the TransactionalState interface, and a corresponding class to implement the TransationKey interface. The contents of BooleanGrid are a 2-D array of boolean values. Commands to update the grid are of the type GridCommand. This object should represent the following information:

• The x and y coordinates of one or more cells that are to be modified.
• For each cell, the old value of that cell (according to the player server's current copy of the grid), and the proposed new value.

A transaction to a BooleanGrid will succeed if the old values mentioned in the grid command match the current values of the relevant cells in the grid. In this case, the current values are replaced with the new proposed ones.

In addition to the update() method inherited from TransactionalState, you will also implement some helper methods for printing, testing, and generating commands from two grids. See the JavaDoc for details.

Finally, a word about synchronization. The integrity of the grid in a BooleanGrid is protected by locks acquired in the call to beginTransactdion, and these locks are released by the call to endTransaction. Since lock acquires and releases are not scoped, you cannot use synchronized for this, but will have to use a suitable class from java.util.concurrent.locks. Moroever, you have a choice about how fine- or coarse-grained will be your protection. In particular, updates to one part of the grid could safely proceed in parallel to updates to a different part of the grid, but overlapping updates should be prohibited. You can always be safe and protect concurrent updates, but you might enjoy thinking about how be more efficient (while avoiding deadlock!).