Distributed Systems ECE419, Winter 2025 University of Toronto Instructor: Ashvin Goel

Lab 1: Learning Go

Due date: Jan 26

In this assignment you will get started with programming in the Go language. You will learn how to compile, run, and debug a Go program. You will practice Go in the context of the two-person version of the game of Nim. Specifically, you will implement the client codebase and we will provide you with a running server for you to test your client.

Starter code and testing servers

First, start with the lab setup instructions. These instructions also provide git instructions for initializing your git development repository. Then, ensure you're in the ece419 directory.

You can get the latest starter code that we provide for all labs in the student repository by running:

git pull upstream main

This command will merge our code into your development repository.

If you are not familiar with merging code in Git, make sure to read chapters 3.1 and 3.2 in the Pro Git Book. This is how software developers coordinate and work together in large projects. For this course, you should always merge to maintain proper history between the student repository and your repository. You should not rebase in this course. It will be important to keep your code up-to-date during this lab as the test cases may change with your help.

The lab code is available in the lab1 directory.

The addresses of servers to which your client can connect will be posted on Piazza. These servers may not be accessible outside the lab subnet, so you will likely need run the client code on the lab machines.

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. In other ways it is more similar to managed languages like C# and Java, in that 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 behavior.

This assignment's objective is to help you become familiar 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.
• The basics of network programming in Go with UDP.

This assignment will also introduce you to a tracing library. You'll use this library to test and debug this assignment. Also, we will use it to help mark your submitted code.

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. In each turn, the coins must be removed from a single row. A player wins when their last move takes the final coin, so none of the rows have any coins left.

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). Your client will play a game of Nim against the server. 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 message. This is a Go struct and the only message format used in this assignment. There are multiple special values in this message as described below.

The user provides the client program with a random seed on the command line (the only command line input). Then, the client follows the following steps:

1. The client sends an initial StateMoveMessage message 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 GameState, which represents the opening state of the board. GameState is a slice of bytes.
3. The client decides on a move to play and computes the new resulting GameState. It sends the move and the GameState back to the server in another StateMoveMessage.
4. The server verifies that the client's received move is valid and continues play, if applicable. If the received move is not valid, the server will resend its previous message.
5. The client and server repeat steps 3 and 4 until there are no more coins in any row in the last GameState transmitted.

The diagram below 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, the starting GameState of [6,6,4] shown in the example below 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 random seed in an opening message.

A StateMoveMessage message has three valid forms.

• {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 received message is always considered valid. If a game was already in progress that game is abandoned by the server.

• {GameState, -1, seed}: The opening message the server sends to the client after a new game board. This received message is considered a valid response for 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 (MoveCount) and the row these coins are being removed from (MoveRow). This received message is considered valid with respect to the previously sent StateMoveMessage{PrevGameState, _, _} message if GameState is the state reached after removing MoveCount coins from row MoveRow in PrevGameState.

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 game 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 (winning) move, the client can terminate on receiving this move. If the client makes the last (winning) 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. 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 use 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 simple client-server example illustrates how to use the tracing library. (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 create its own tracing server and you will not need to deal with tracing tokens.)

Please familiarize yourself with the tracing library documentation.

Tracing semantics

Your solution must follow the tracing semantics described below. Your grade depends on the tracing log generated by your solution. 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 single 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.
  • Unless this is the initial move, this action must happen after the previously received corresponding ServerMoveReceive message. If duplicate ServerMoveReceive messages are received, this action must happen after the first such message.

• 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 valid 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
} (duplicate)
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 execution shown above. This diagram also lists the traced actions as boxes on the client timeline. Note that the traced actions are located at specific 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 duplicates by the client or those that are re-sent by the client due to message loss).

Solution specification

You need to write a single go program called nim-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 nim-client.go seed

Here seed is the random seed to be sent to the server in the client's first move to generate a game board.

The client reads the config/nim-client-config.json configuration file. This file specifies the UDP IP address and port of your client, the server (that we are running), and the tracing server (that you are running).

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 implements correct game logic (does not misbehave).
• Messages are not 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

• Messages must be encoded using the encoding/gob Go package.
• Your solution can only use standard library Go packages, i.e., your solution cannot use any external (third-party) libraries other than the tracing library.
• Your solution code must be formatted using gofmt.

Testing

For this lab, we have provided you a tool that allows checking whether the tracing output meets the requirements specified in the lab instructions. After setting your path variable, you can run the tool as follows:

ece419-lab1-check seed output.log

The seed should be the same value as specified on the command line of the client program. The output.log file is the output of the tracing server.

The checking tool's output will be strongly correlated with what our autograder will consider correct (though we may test additional scenarios during grading).

Submission requirements

Your client code must be runnable on the UG machines and be compatible with the Go version installed on those machines.

You must use UDP and the message types used in the initial code. Do not change this format.

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

We provide a stub nim-client.go file in which you must write all your code. We will only use this file from your repository for marking.

The client code must use the config/nim-client-config.json configuration file. You may need to change the client and tracing server addresses in this file in case of conflicts with other students running the client code on the same machine. The client code should also start and stop a tracing server. Add the config file for your tracing server at config/tracing-server-config.json.

If you do not follow these requirements, you will likely get a 0 mark for the assignment.

Submission

Please see lab submission.

Grading criteria

• 70% mark if your code works correctly for the happy path, i.e., when there are no message errors.
• 10% mark for correctly handling duplicate messages.
• 10% mark for correctly handling delayed messages.
• 10% mark for correctly handling lost messages.
• 5% bonus mark for always winning against our server.

Advice

• Read the Lab 1 FAQ.

• 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 UG machines.

Acknowledgements

Prof. Ivan Beschastnikh and his team at UBC developed this lab. They have graciously shared the lab code with us.