Assignment One for CS5223 June 2021

(If you have feedbacks on this assignment, please let us know so we can improve it for next year.) This
assignment should be done in teams, where each team can have at most 3 students. Throughout the document,
“you” means “your team”. You can use Java, C, or variant versions of C such as C++ or C#, for this assignment.
If you would like to use a programming language other than those mentioned above, you are required to let me
know and obtain permission from me no more than one week after the assignment starts. Regardless of which
programming language you use, you will need to use the “StressTest” program that we provide during the demo to
stress test your program.
1 Background
The objective of this assignment is to give you hands-on experience in designing and implementing distributed
systems. Distributed systems tend to easily grow in complexity. Make sure that you finish the basic goals before
moving on to more complex functionalities. A major design choice is whether to use RMI or sockets. It is not an
obvious choice and each has its pros and cons for this project. You should apply what you learned in class to make
your decision. You are allowed (and encouraged) to discuss with other students. For example, you are welcome to
do so on the general student discussion forum on LumiNUS . But you should build your system independently and
should never copy any code. Consult me if you are unclear with this policy.
2 Designing and Implementing A Peer-to-Peer Distributed Maze Game
2.1 Overview
You are to implement a distributed maze game. The maze is an N-by-N grid, consisting of N*N “cells”. Each
cell contains either no “treasure” or exactly one “treasure”. At the start of the game, there are K treasures placed
randomly at the grid.
The number of players is arbitrary. Each player can be viewed as running on a separate node in the distributed
system. Each player aims to collect as many treasures as possible. A player collects one or more treasures when the
player’s location is the same as the treasure’s location. A player cannot occupy a cell that another player occupies.
Each player has a current score which equals to the number of treasures the player has collected.
The number of remaining treasures in the game will always be K — this means that when a treasure is taken by
a player, the game should automatically create a new treasure at some random location.
We want the system to be fault-tolerant. Namely, we want the system to be robust against player crashes.
2.2 The Tracker Program
For implementing this distributed game, you should first design and implement a program called the Tracker. The
tracker will have a well-known IP address and port number (i.e., known to all people who want to play the game).
Furthermore, the tracker knows the values of N and K.

Whenever a new player wants to join the game, the new player should contact the tracker first (at the wellknown IP address and port number). This allows the new player to obtain information about the existing players
(e.g., their IP addresses and port numbers) in the game, as well as N and K. If you are familiar with BitTorrent, our
tracker here provides a similar functionality to a BitTorrent tracker. It is up to you what information a new player
gets from the tracker. For example, the tracker can return the entire list of current players in the game. Or the
tracker can return a random current player in the game.
After the new player gets such information from the tracker, the new player will contact the existing player(s)
(based on such information) to actually join the game. Note that since we allow player crashes, it is possible that
the information returned from the tracker becomes stale by the time the new player tries to use it. So you should
design your program carefully to deal with such cases.
It is important to note that a player is allowed to contact the tracker only when i) it first joins the game and ii)
some player crashes and the system is trying to regenerate the game servers (see later). A player is not allowed to
contact the tracker during its normal gameplay (e.g., when doing moves). The tracker should not maintain
any information about the current game state (such as the location of the players in the maze and which
player is the primary/backup server), other than the list of current players, N, and K. The reason is that the
tracker is a single node, and hence a good design should always minimize the load on the tracker.
Your tracker program should be invoked in the following way:
• If you are using Java, you should have a “Tracker.class” in the working directory after compilation. Then
you should run:
java Tracker [port-number] [N] [K]
• If you are using C, please name your binary file as “Tracker.exe” after compilation. Then you should run:
Tracker.exe [port-number] [N] [K]
Here port-number is the port over which the Tracker is listening, while N and K are the parameters for the maze.
The (implicit) IP address will be the local machine’s IP address on which the tracker runs.
2.3 Restriction on the Use of rmiregistry
If you use RMI (or equivalent mechanisms in other programming languages), you should have a single rmiregistry
(or a single equivalent bootstrapping process in other programming languages). The single rmiregistry should
running on the same node (machine) as the tracker. The rmiregistry should be used only for registering and
locating the tracker. You should not register any other remote objects (such as the primary server, the
backup server, and the players) with the rmiregistry.
The above restriction is set in place because a good design of an RMI-based system usually never use more
than one RMI registry — using multiple rmiregistries adds complexity, makes the system less secure, and also
makes the system less robust. Also, we want to minimize the load on the rmiregistry, for exactly the same reason as
minimizing the load of the tracker. Note that it is still possible to use RMI to complete everything in this assignment,
despite the above restriction. How to do so is part of the assignment, and each team will need to work it out itself.
2.4 The Game Program
You should design and implement a program called Game, which will be the main program in this assignment.
A user should be able to execute Game (from any node/computer) to join the maze game as a new player. As
explained earlier, this Game program should contact the tracker as a bootstrapping point. Each player has a name,
which has exactly two characters.
The player should join the maze game in the following way:

• If you are using Java, you should have a “Game.class” in the working directory after compilation. Then you
should run:
java Game [IP-address] [port-number] [player-id]
• If you are using C, please name your binary file as “Game.exe” after compilation. Then you should run:
Game.exe [IP-address] [port-number] [player-id]
Here IP-address is the well-known IP address of the Tracker and port-number is the port over which the Tracker is
listening. The player-id is the two-character name of the player.
The Game program should have a GUI, showing:
• The name of the local player (should be shown at the top bar of the window, i.e., the title of the window).
• The current score of all the players (should be shown at the left part of the window).
• The maze as a grid (should be shown at the right part of the window).
• Each treasure in the current maze should be shown as a “*” on the grid.
• The current positions of all players (including both the local player and all other players) in the grid, by
indicating in the respective cells the players’ two-character names.
• The name of the player currently acting as the primary server and the name of the player currently acting as
the backup server. (See the definitions of the primary server and the backup server later.) These should be
indicated in the left part of the window (together with the scores of all the players).
Additional eye candies in your GUI are allowed but will not earn you extra credits, since the focus of this assignment
is on distributed systems.
The Game program should read text lines from standard input:
• If the line equals “0”, then the player does not move but refreshes its local state (i.e., so that its local state
contains the most up-to-date game state information, including the scores of all the players, the positions of
all the treasures, as well as the positions of all the players).
• If the line equals “1”, then the player moves West by one step and refreshes its local state.
• If the line equals “2”, then the player moves South by one step and refreshes its local state.
• If the line equals “3”, then the player moves East by one step and refreshes its local state.
• If the line equals “4”, then the player moves North by one step and refreshes its local state.
• If the line equals “9”, then the player exits, and all other players should delete this player from the game (so
that this player is no longer shown in their GUIs).
• For all other cases, the program does nothing.
The grid boundaries are solid, e.g. a player cannot move south if he/she is already at the south-most row. Players
should be able to move in an asynchronous fashion. For example, it should be possible for one player to move five
steps when another player only makes one move. How fast a player moves should only be constrained by how fast
the user inputs the directions.

2.5 The Game State
The game state includes the current positions of all the treasures and the current positions/scores of all the players.
Since we are designing a peer-to-peer distributed game, there will be no servers storing the game state. Rather, the
players themselves have to do the job and maintain the game state. There are compelling commercial reasons to get
rid of the server – if your company can support distributed games without maintaining servers, it means that your
company can collect revenue while incurring minimum operational cost.
To do a peer-to-peer game, among all the players, one player should act as the primary server (in addition to
being a player itself), and another player should act as the backup server (in addition to being a player itself). The
notions of primary server and backup server are logical here, since there are actually no dedicated game servers.
When the game initially starts, whoever joins first should be the primary server, and whoever joins second should
be the backup server.
Both the primary server and the backup server should maintain up-to-date game state. When a player moves,
it is allowed to communication with the primary server and/or the backup server to update the game state as well
as retrieve the latest game state. The primary server and the backup server may communicate with each other as
well if you would like them to. However, the primary server and the backup server should not communicate
with other players (i.e., other than the player making the move request). In particular, they are not allowed
to immediately broadcast the updated state to the other players. The updated game state should be sent to the
other players only when they make their moves. In other words, the other players will often see a game state that is
slightly stale. This requirement serves to make sure that your design is realistic – in the real world for large-scale
games, immediately updating all players incurs prohibitive overhead.
Your primary server and backup server are also responsible for creating new treasures when existing treasures
are collected by the players. Recall that the total number of remaining treasures in the maze game should always
be K.
2.6 Server Multi-threading
The server logic should be multi-threaded. If you are using RMI, then RMI implicitly is already multi-threaded and
you need to ensure properly mutual exclusion when access shared data among different threads.
If you are using sockets, then for a new player, the server should create a corresponding “player thread”. A
player thread should keep track of that player’s location and score. All player threads access the same data structure
for the number and location of available treasures, and for the location of other players. Consequently, you need to
provide mutual exclusion when accessing these shared data structure.
Furthermore, if you are using sockets, then the server’s main thread should demultiplex each incoming message
to the corresponding playing thread. In other words, only the main dispatch thread should directly receive messages from clients. When a message arrives, the dispatch thread has to notify (wake up) the corresponding player
thread to process that message and relay the message to that player thread. We understand that this requirement
will not impact the end functionality. However, real multi-threaded servers are usually done in this way because
doing so is somewhat more efficient and stable. Hence we need the students to do the assignment in a way that is
similar to real-world servers. Hint: You may want to consider using non-blocking I/O in the main thread. For
RMI, it internally already has a dispatch thread, and hence directly satisfies this requirement.
2.7 Fault-tolerance
We want the game to be fault-tolerant. The tracker is assumed to never fail. But a player may crash at any point of
time, and we want to be able to tolerate player crashes. “Player crash” here means that the player process is killed,
or the power cord of the computer running the player program is unplugged. Normal player exit is not considered
as crash. Ask your lecturer if you are still not sure. “Tolerate player crash” means that the game (including all the

other players that have not crashed) should continue as usual despite that some players have crashed. The crashed
player should be removed from the maze so that we don’t end up having many ”dead bodies” in the maze. You are
allowed to use background pinging among the players to monitor which players have crashed. Such pinging should
be done at a rate of one ping every 0.5 second, and the total number of pings done (in the whole system) in 0.5
second should be O(N) (and not N2
).
Since we are having a peer-to-peer architecture, dealing with player crashes will be tricky since the crashed
player may be acting as the primary server or the backup server. We want to make sure that those players who have
not crashed can continue playing the game, regardless of who else has crashed. In particular, you will need to do
the following:
• If the player acting as the primary server crashes, your system should be able to “regenerate” the primary
server on another (uncrashed) player. You need to properly make sure that the game state on the new primary
server is brought up-to-date. (You need to think how to achieve this.)
• The same applies if the player acting as the backup server crashes.
• As long as there are at least two players, your primary server and backup server should not be on the same
player.
To make your job easier (or perhaps to make your job possible), for dealing with player crashes, you are allowed
to assume:
• A player that has crashed never revives.
• Messages never get lost (under TCP and RMI) and message propagation delay is at most 0.2 second.
• No two players crash at the same time – there is at least 2-second gap between two successive crashes (so
that you can have enough failure-free time to do what you need to do).
3 Some Hints
• Think thoroughly before you implement. This is the single most importance hint I can give you. Think
through your entire design, think through all possible cases and in particular corner cases, think through all
the possible alternative designs, before start programming. Resist the temptation to start programming until
you have thought thoroughly. Doing so will save you a lot of trouble later. I have seen numerous cases where
the students do not think through, and end up with an unnecessarily complicated design that takes a lot of
time to implement, or end up having a buggy design that is very hard to debug.
• Do NOT use StreeTest to debug your program! You should first debug your program separately to ensure
it is bug-free, and then try running StressTest — see more on this in Section 4.4.
• For debugging, you should start from simple cases where the players and the tracker are different Java processes running on the same computer. This will save you the trouble of using multiple computers. You should
NOT use virtual machines. Virtual machines have impact on networking, and may require some extra tuning
to make things work properly.
• You will need to worry a lot about consistency: Since you have two copies of the game state, how do you
ensure that they are consistent? In particular, you need to avoid running into the situation where player A
gets the treasure in one copy, while player B gets the same treasure in another copy. Should you have the
player directly update the two copies, or should you have the player update the primary and let the primary

update the backup copy? In particular, what if someone fails while you are updating the states? These are by
far not trivial problems, and even just thinking about them will help you to get more out of this module.
• If you create a new primary (backup) server, how do you bring its state up-to-date?
• The primary (backup) server can crash at any point of time. In particular, it may crash while it is processing
a request. How do you handle that?
• There are a lot of parallelism in the system. For example, while your system is creating a new primary
(backup) server, the players may still be issuing requests to the servers. What should you do?
• You can test your system in various interesting ways. For example, you can start with 5 players, and then
keep killing the primary (backup) server, until you have only 2 players left. (Since you need a primary server
and a backup server, 2 players is the minimum possible number.)
• Proper mutual exclusion access on global shared data on the server is critical for correctness. Make sure
that you have a clear thinking of such mutual exclusion. Try-and-debug will not help you solve problems
introduced by improper mutual exclusion, and will suck up ALL your time.
4 Deliverable and Assessment
4.1 Schedule
• 2 Sept 2021: Assignment starts.
• Whole day, Saturday and Sunday 9-10 Oct 2021: Each team will be assigned a time slot on one of the two
days, during which the team will show TA a demo of the implemented system by doing the StressTest
(described below), together with the source code. You will be required to download your source code
and StressTest.java from LumiNUS, and do the demo using the downloaded code. In rare occasions,
you may be also requested to explain your code to me later. ALL team members must be present for the
demo.
• If you prefer, you are allowed to submit your code and to do the demo with the TA before the deadlines.
Doing so does not give you extra credits, though it does allow you to move on to Assignment Two earlier. If
you would like to do so, please contact the TA directly to arrange a time to do the demo. You are required to
submit the code to LumiNUS before doing the demo with the TA.
4.2 Source Code Submission Instructions
• You should download “AssignmentOneSubmissionSummary.docx” from the “AssignmentOne” folder on LumiNUS, and fill in the information in that file. The completed softcopy MUST be submitted together with
your source code. Without this file submitted, you will not be allowed to do the demo.

• 11:59pm, 7 Oct 2021: Deadline for uploading your source code to LumiNUS. This will allow us to
examine your code, and also to check for plagiarism, both before and after your demo. Late source code
submissions onto LumiNUS will result in ZERO mark for this assignment. The reason is that demos will be
done on the next two days, and without the source code we cannot let you do the demo. With such a policy,
even if you do not finish on time, you should submit whatever you have by the deadline. Doing so will
earn you some partial marks – otherwise you will get ZERO mark.
• You should only submit the final version of your code.
• You should zip all your source files (.java, .c, .h, etc.), together with “AssignmentOneSubmissionSummary.docx”, into a single zip file. You should NOT include any other files. No need to include instructions
on how to compile/run your code. We will not compile/run your code – we will only examine your source
code.
• All your source files must be in the same directory with no subdirectories when you zip them – NO
multiple directories or nested directories.
• The submission file name must be in the following form: “[Team member 1’s student #] [Team member 2’s
student #] [Team member 3’s student #].zip”. For example, if the student numbers are A11, A22 and A33,
then the file name should be A11 A22 A33.zip. Deviation from such naming scheme may cause mistakes
when processing your submission. For teams with less than 3 students, the submission file name should just
include all your team members. For example, the file name can be A44 A55.zip for two-member team with
student numbers A44 and A55.
• No multiple submissions allowed. Each team should make sure that the team only submits exactly once.
If a team submits two versions, we will retain the earliest version and discard all later versions. The team will
then be graded on the earliest version. For this reason, if you want to update your submission, you should
first delete your old submission and then submit a new one.
• Your zip file should be uploaded to the “StudentSubmission-AssignmentOne” folder in LumiNUS Files.
4.3 Stress Test for the Demo
The demo will be done in an automatically way using the “StressTest” program. The source file of that program, named “StressTest.java”, is given to you at the beginning of the assignment. You should read through
”StressTest.java” very carefully, at the very beginning of the assignment, to understand what it does. The
comments in “StressTest.java” tells you how to do the demo properly. Before the demo, you should set up RMI
registry (if needed) and the Tracker program properly. During the demo, you will be asked to compile and then
execute the “StressTest” program. (Other than running the ”StressTest” program, there is nothing else you need
to do during the demo.) You must run StressTest by invoking “java StressTest [IP-address] [port-number]
[your Game program]” directly from command line, instead of for example, invoking StressTest from within
an IDE. The StressTest will create many players (by invoking your Game program), inject move requests to the
players, kill players, and so on. We will not change the “StressTest” program in any way during the demo, and
hence you can view this as an “open-book” test. The maze size for the StressTest must be 15*15, and the number
of treasures must be 10.
You should do the demo on your own computer. If your team does not have a computer, please inform the TA
at least two weeks before the demo so that the TA can arrange a computer for you.
4.4 Completing Stress Test before the Demo
You should execute the “StressTest” program well before you come to the demo and make sure everything
works since you will not be given opportunities to debug your program during the demo. Remember that you
are required to write done how many checkpoints your program can correctly pass under this StressTest in your
“AssignmentOneSubmissionSummary.docx” before you can submit your code to LumiNUS.
While “StressTest.java” is given to you at the beginning of the assignment, note that the steps done in this
program will be “stressful” to your program. Namely, the execution path it results will be extremely complicated.

(This is precisely the reason why we do not need to hide this test program from you.