416 Distributed Systems: Assignment 1 [Nim]

Due: January 24 at 6pm PST

Winter 2022

In this assignment you will get started with programming in the Go language. To solve this assignment you will need to install Go, figure out how to compile, run, and debug a Go program. You will practice Go in the context of the two-person normal play version of the game of Nim. Specifically, you will implement the client codebase and we will provide you with a running server that you can test against.

Overview

Go (or golang, as it helps to search for it) is an imperative programming language generally aimed at the development of distributed systems. In some ways, it is related to systems languages like C and Rust, in that programs are built using structs and functions (and like Rust, while it supports "methods", they are basically just special functions). In other ways it is more similar to managed languages like C# and Java, in that, while it does not have a VM, it has a lot of "managed" features: it has a garbage collector, full runtime type information, and the design strives to have essentially no undefined behaviour.

This assignment's objective in particular is to help you get to grips with Go's basic features. You will learn:

• How to use basic data structures like slices
• How to work with simple struct definitions and methods
• How to work with Go's built-in testing infrastructure (recommended)
• The basics of network programming in Go with UDP

This assignment will also introduce you to our tracing library. You'll use this library throughout the course to test and debug your Go systems, And, we will use this library to help us mark your submitted solutions.

Nim overview

Nim is a two-player game. A game of nim starts with a board that contains some number of rows, and each row contains some number of coins. The two players take turns removing any non-zero number of coins, with the constraint that all the coins that are removed in a turn must come from a single row. A player's goal in nim is to make the last move, taking the final coin.

High-level system description

There are two kinds of nodes in the system: a server (that we will implement), and a client (that you will implement), which will play a game of Nim against each other. You will test and debug your solution against a running server instance, but you will not have access to the server code.

The server listens to connections from clients and expects UDP packets containing a serialized [StateMoveMessage]. This is a Go struct and the only message format used in this assignment. There are multiple special values that represent different things, but you only have to worry about one format they are packaged in. This is described further below.

The client reads the [config/client_config.json] JSON file. This file specifies the UDP IP:port of the server (other player) that it is to connect to. The client receives a randomization seed on the command line (the only command line input). Then, the client follows the following steps:

1. The client sends an initial [StateMoveMessage] via UDP to the server with the random seed it received on the command line.
2. The client receives a [StateMoveMessage] reply from the server that contains a slice of bytes GameState, representing the opening state of the board.
3. The client decides on a move to play, computes the new resulting GameState and sends both back to the server in another [StateMoveMessage].
4. The server verifies the client's move is legal on receive and continues play, if applicable. If the received move is not legal on receive, the server will re-send its previous message.
5. The client and server repeat from step 3 until there are no more coins in any row in the last GameState transmitted.

The diagram below is a time-space diagram that illustrates the client-server interactions described above. Messages are arrows between the two timelines, from client to server, or from server to client. Message content is listed between the brackets on each message arrow:

Message Format

The declaration of [StateMoveMessage] is:

type StateMoveMessage struct{
	GameState []uint8
	MoveRow int8
	MoveCount int8
}

In each message:

• [GameState] represents the state of the game board as a slice of unsigned bytes. This state is the state of the board after the move has been made (this move is also specified in the message). Each element of this slice represents one row of coins. For example, below a GameState of [6,6,4] represents a game board with three rows. The first two rows contain 6 coins and the third row contains 4 coins.
• [MoveRow] either represents the row from which coins are to be removed in a normal move, or indicates an opening message (-1).
• [MoveCount] either represents the number of coins to be removed in a normal move, or indicates a provided random seed.

• {nil, -1, [seed]}
• The opening message the client sends to the server to start a new game. [seed] is the random seed the server uses to generate the initial board. This is always considered legal on receive. If a game was already in progress, that game is considered abandoned.
• {GameState, -1, [seed]}
• The opening message the server sends to the client, on creating a new game board. This is considered legal on receive with respect to an opening message from the client with the same seed.
• {GameState, MoveRow >= 0, MoveCount > 0}
• A move in the game with some valid number of coins to remove, and the row these are being removed from. This is considered legal on receive with respect to a StateMoveMessage{GameState', _, _} if [GameState] is the state reached after removing [MoveCount] coins from row [MoveRow] in [GameState'].

Message Loss

Packets sent via UDP are not guaranteed to arrive at their destination. This means there will be no reply received if either the client message or the server message is dropped by the network. It is the client's responsibility to re-attempt a message exchange, after a timeout of 1s (after not receiving a response from the server 1s after sending a message to the server). You can assume that the server will hang onto the last known state indefinitely, until the client is able to make progress (get a message through to the server).

Note that when using UDP, a message may also arrive out of order, and/or be duplicated by the network. Your solution must be able to deal with both of these cases.

If the server makes the last move, the client can terminate on receiving this move. If the client makes the last move, the client can terminate as soon as it transmits the move message, regardless of delivery at the server.

Tracing Library

This assignment introduces the tracing library, which will be used to test whether your code is behaving correctly. The library has online documentation that you should familiarize yourself with.

Tracing is like logging. We say that a process records/reports/traces actions or events. What this means is that the process calls a tracing library method to record a particular struct type. A key difference with logging is that tracing can be used to reconcile ordering of events across networked nodes. To trace your program, the program needs to connect to a tracing server. In this assignment your client will have its own tracing server – your client code will need to start this tracing server, connect to it, run the client logic while recording actions at specific points in the execution, and later terminate the tracing server before exiting. A client-server example that illustrates how to use the tracing library can be found here. (Note, however, that in this example, the client and server use the same tracing server and also use tracing tokens. In this assignment your client will have its own tracing server and you will not need to deal with tracing tokens.)

Tracing Semantics

Your solution must precisely follow the tracing semantics described below. Your grade depends on the type of tracing log that your solution generates. For example, if traced actions are in the wrong order, or are missing, then you will lose points.

You will use the tracing library to report actions using calls to trace.RecordAction, using a singular trace object obtained via tracer.CreateTrace. You only need to implement tracing for actions within your own client. There are four types of actions that your client code must trace:

• [GameStart{Seed}] marks the start of a new game.
• This action should appear exactly once, before any other actions are recorded.
• Seed must be the randomization seed provided on the command line.
• [ClientMove{GameState, MoveRow, MoveCount}] indicates that a client has made a move.
• This action must be recorded just before sending the corresponding client move to the server, including the opening "move".
• The exception below aside, this action must happen after a [ServerMoveReceive]. The [ClientMove] action must be legal on receive relative to its unique preceding [ServerMoveReceive], considering the first of any duplicates, if the same [ServerMoveReceive] is logged more than once.
• The above condition does not apply to an initial [ClientMove], which must match the pattern [ClientMove{nil, -1, _}] for this exception to apply.
  (One way of interpreting the above two bullets is that they pin client progress to server progress.)
• [ServerMoveReceive{GameState, MoveRow, MoveCount}] indicates that a server's move has been received.
• This action must be recorded just after receiving a move from the server, including the opening "move".
• If this action is recorded, there must exist at least one [ClientMove] that happens-before it.
• [GameComplete{Winner}] marks the end of a game.
• This action must be recorded exactly once, after either a legal [ServerMoveReceive] or [ClientMove] (depending on the winner) with all entries in its [GameState] equal to 0.
• This action must always be the last recorded action in a trace.

Example Execution

Below is an example sequence of messages from a correct execution of this system with one client and one server (these messages also illustrated in a diagram below):

From client: StateMoveMessage {
       	GameState: nil
	MoveRow: -1
	MoveCount: 32
}
From server: StateMoveMessage {
	GameState: [6,6,4]
	MoveRow: -1
	MoveCount: 32
}
From client: StateMoveMessage {
        GameState: [6,1,4]
        MoveRow: 1
        MoveCount: 5 
}
From server: StateMoveMessage {
        GameState: [6,6,4]
	MoveRow: -1
	MoveCount: 32
} (duplicated)
From server: StateMoveMessage {
	GameState: [0,1,4]
	MoveRow: 0
	MoveCount: 6
}
From client: StateMoveMessage {
	GameState: [0,1,1]
	MoveRow: 2
	MoveCount: 3
} (lost)
From client: StateMoveMessage {
	GameState: [0,1,1]
	MoveRow: 2
	MoveCount: 3
}
From server: StateMoveMessage {
	GameState: [0,0,1]
	MoveRow: 1
	MoveCount: 1
}
From client: StateMoveMessage {
	GameState: [0,0,0]
	MoveRow: 2
	MoveCount: 1
} (lost)

The diagram below illustrates the above execution as a time space diagram. In addition, this diagram lists the traced actions as boxes on the client timeline. Note that the traced actions are located at very precise points in the client timeline relative to when the client received or sent each message.

An important feature of the above execution (and tracing semantics in this assignment) is that actions are recorded in response to all received/generated messages (i.e., even those that are received as duplicated by the client or those that are re-sent by the client because of message loss).

Solution Spec

You are to write a single go program called client.go that acts as a client in the protocol described above. Your program must be executable from the terminal using the following command:
$ go run client.go [seed]
Where [seed] is the random seed to be sent to the server in the client's first move to generate a game board.

The ports to be used by the client to connect to the server at and to listen on are provided/configured in [config/client_config.json].

• [ClientAddress]: local address that the client uses to connect to both the server and the fserver (i.e., the external IP of the machine the client is running on)
• [NimServerAddress]: the UDP address on which the server receives new client connections
• [TracingServerAddress]: the UDP address at which you are to run the tracing server

Your solution cannot use any external libraries other than those related to the tracing library.

Assumptions you can make

• All messages fit into 1024 bytes
• The board for a game does not exceed 16 rows
• The number of coins in each row does not exceed 10
• The server does not fail and responds in a timely manner
• The server follows correct game logic (does not logically misbehave)
• Messages will not be corrupted
• The opening messages sent from clients can't be duplicated or severely delayed

Assumptions you cannot make

• UDP is reliable

Protocol corner cases

• During a game, the server expects each incoming move to be valid for the directly preceding game state. If it is not, the server resends the previous move it made.
• Your code should use a 1 second timeout for message loss (before attempting to retransmit a message)

Implementation requirements

• The client code must be runnable on CS ugrad machines and be compatible with Go version 1.16.7 (which is installed on ugrad machines)
• You must use UDP and the message types given out in the initial code
• Messages must be encoded using encoding/gob.
• Your solution can only use standard library Go packages
• Your solution code must be Gofmt'd using gofmt

Starter code and testing servers

We make four files available for you as starter code for this assignment, as well as an automated checking tool to analyze your distributed traces.

1. client.go : starter code for your client.go. This file assumes a tracing configuration file that is available in ./config/client_config.json.
2. client_config.json : config file that you can use for this assignment. (Note that you may need to change port numbers in case other students are running the tracing server/client on the same ugrad server.)
3. go.mod : contains dependency tracking metadata, including a dependency on https://github.com/DistributedClocks/tracing, the tracing library.
4. go.sum : contains auto-generated metadata (checksums for module dependencies). You should not need to touch or understand this file.

The list of nim servers you can test against will be posted to piazza.

The provided checking tool's output will be strongly correlated with what our autograder will consider correct (though our test scenarios themselves remain secret), so make sure to try it. It is much easier to investigate and ask questions before the deadline than to be surprised after.

Handin instructions

Keep the provided file layout at the top-level in your solution repository. You may include additional files, but we do not expect this will be necessary. Do not reference any additional libraries in your solution.

Your code must be in a single client.go file, including the tracing server set up. You shall not use a separate file to run the tracing server. (This requirement only affects your Go files, you should still have a config file for your tracing server, and place it at config/tracing_server_config.json).

Your code must not change the UDP message format and tracing spec. Your code must work on ugrad servers (e.g., remote.students.cs.ubc.ca).

If any of these are violated, your mark for this assignment is 0. This is true regardless of how many characters had to be changed to make your solution compile, and regardless of how well your solution works with a different API or on a different machine.

For a list of server machines you can use, please see this page. Note that the right version of Go (version 1.16.7) is installed in /cs/local/bin/go.

More instructions about submitting using a git repository via https://github.students.cs.ubc.ca/ will be posted here and on Piazza.

Grading Criteria

• 70% Standard test cases, traces pass trace conditions on happy-path scenarios
• 5% GameStart is reported correctly
• 15% Initializes game state correctly with the seed passed via command-line
• The opening ClientMove and matching opening ServerMoveReceive are recorded
• 20% Is able to make one valid move
• At least one non-opening ClientMove reported is legal on receive with respect to the preceding recorded ServerMoveReceive
• 25% Plays to completion
• An alternating series of ClientMove and ServerMoveReceive actions recorded are legal on receive, each with respect to the preceding action in the series, the final move in which has all entries in its [GameState] equal to 0
• 5% GameComplete is recorded correctly
• 30% : Scenario testing, traces pass trace conditions under special scenarios
• 10% Is able to handle receiving repeated messages and continue normal play
• 10% Is able to handle receiving delayed messages and continue normal play
• 10% Is able to deal correctly with lost messages
• Bonus 5%: Note that you do not have to win to complete this assignment, but it is possible to make an optimal strategy and always win against our server from the starting configuration. If your solution always wins against our server, then you will be rewarded an extra 5%.

Advice

• Start simple, and do not worry about UDP edge cases until the happy path works.
• Be extra careful with where and when you trace actions. These must be correct for you to receive the above marks.
• Do not attempt to win the game as a starting point. Leave the bonus to the end.
• Compile and run your code on the ugrad servers.

Make sure to follow the course collaboration policy and refer to the submission instructions that detail how to submit your solution.