CS [4|5]113 Fall 2021

Distributed Operating Systems

Final Project

Here we describe to you the requirements and expectations for your final project this semester in distributed operating systems.

Description

You will implement asynchronous chess (a-chess). If you don’t know how to play the ordinary chess, here are the rules and a preliminary introduction. You may also learn the chess notation I use here.

Ordinary Chess

The difference between a-chess and the ordinary-chess is mostly defined by the independence of the move order. In ordinary chess players must take their turn, e. g., under one minute. The move dynamics restrict that at every minute, exactly one piece may be moved by only one of the players while the current player can not be the same as the one who moved their piece last-time. I. e., no one moves their pieces twice in a row. Here is an example checkmate using the famous Napoleon opening.

Minute	Player	Move
1	White	e4
2	Black	e5
3	White	Qf3
4	Black	a6
5	White	Bc4
5	Black	b6
6	White	Qf7

Asynchronous Chess

In a-chess however, we lift these movement and time dynamics and drive the chessboard a little closer to an actual battle field where all troops move independent of each other and turn-parity. A-chess allows for multiple moves at the same step, e. g., you may see both e4 and e5 simultaneously. Bellow we give a game table which is now possible due to the relaxed constrains in the asynchronous case.

Step	Move
1	e4’, e5
2	Qf3’, a6, Bc4’
3	Qf7’, b6

We denote the white’s moves by a prime mark.

Disambiguation

Most of these should be pretty intuitive. In any event, bellow are some additional disambiguation and rules of ordinary chess that still apply. Note that the professor expect discussions to help the class design the game.

1. Each movement must adhere to the standard chess movements for the piece. For example, rooks can only move along rows or columns.

2. Once a piece is in motion, its path cannot be changed.

3. Pieces stop moving when they reach their destination or intersect another piece, friend or foe.

4. If a piece attempts to move into a space already occupied by another one of the pieces of the same colour, the moving piece is stopped at its current location.

5. If a piece moves into a space occupied by a non-moving piece of different colour, then the stationary piece is captured and the moving piece is parked at that location.

6. If a piece is currently moving, then a new move for it is rejected, i. e., moves for a piece are not stacked.

7. If multiple pieces attempt to move into the same unoccupied space at the same time, then it is left upon the implementer to handle this appropriately.

8. Server stops accepting any moves at checkmate or stalemate.

9. Pieces move at a specified rate which is defined as milliseconds (ms). You may evaluate the rate of any piece as the function,

   \[f(v) = c|v| \text{ ms}, \quad v\sim \mathcal{N}(0, 1)\]

E. g., $v$ is a random variable with normal distribution having zero mean and one variance. For undergraduates $c=100$ and the board size is standard 8 by 8 blocks while for graduate students $c=0$ (absolutely no waits) and the board size is 32 by 32.

Implementation Stack

You will be using Python 3 for this assignment. You may ask the professor for permission if you’d like to use a different one.

1. Docker
2. gRPC
3. Protocol Buffers

Examples and Guides

You may install Docker on GNU/Linux by running:

sudo apt install docker.io
sudo systemctl enable --now docker
sudo usermod -aG docker myusername

Exiting the console, log-out and log back in.

The directory tree under your code-directory should look like this,

.
├── docker-compose.yml
├── Dockerfile
├── guessing_game.proto
├── node.py
└── requirements.txt

0 directories, 5 files

Assuming you have a python file called node.py, bellow is an example Dockerfile.

FROM ubuntu:rolling

MAINTAINER harry@hogwarts.edu

ARG DEBIAN_FRONTEND=noninteractive

RUN apt-get update && \
    apt-get install -y locales && rm -rf /var/lib/apt/lists/* \
    && localedef -i en_US -c -f UTF-8 -A /usr/share/locale/locale.alias en_US.UTF-8
ENV LANG en_US.utf8

RUN apt-get update && \
    apt-get upgrade -y \
    && apt-get install -y python3-pip ipython3

RUN apt-get install -y emacs nmap iputils-ping ssh netcat htop slurm net-tools

ENV GRPC_PYTHON_VERSION 1.15.0

RUN apt-get install -y libprotoc-dev protobuf-compiler

RUN python3 -m pip install --upgrade pip && python3 -m pip install click grpcio grpcio-tools

RUN mkdir -p /usr/src/app
WORKDIR /usr/src/app

# Build python stuff
COPY requirements.txt /usr/src/app/
RUN pip install --no-cache-dir -r requirements.txt
COPY . /usr/src/app

# Create the protobuf files
# RUN protoc --python_out=. guessing_game.proto
# Code below works similarly
RUN python3 -m grpc_tools.protoc -I. --python_out=. --grpc_python_out=. guessing_game.proto

EXPOSE 22
EXPOSE 80
EXPOSE 50050-50100

# Unbuffer to see logs with docker logs <containername>
ENV PYTHONUNBUFFERED=1

# Run the node
CMD ["python3", "node.py"]

You’ll also need a docker-compose.yml. Each of the pieces are meant as a node/vertex in the distributed system. You need a naming convention that uniquely identifies each piece. One way to do this for the undergraduates (and may be adapted for the graduates) is to just call them by their initial position, e. g., the white knight is then called commissioner gordon Nb1’ or Ng1’.

version: '3.7'

services:
  server:
    build: .
    hostname: server
    container_name: Server
    networks:
      - default
  client1:
    build: .
    hostname: Ra1'
    container_name: White Rook at a1
    networks:
      - default
  # [snip]
  client32:
    build: .
    hostname: Rh8
    container_name: Black Rook at h8
    networks:
      - default

networks:
  default:
    driver: bridge

You may setup the protocol buffer definitions in a file like this,

syntax = "proto3";

package a_chess;


service AChessService { // service ran on the server
  rpc example_rpc (ExampleMessage) returns (ExampleResponse) {}
  // rest of the RPC definitions
}

message ExampleMessage {
  // Fill me.
}

message ExampleResponse {
  // Fill me.
}

// rest of the message definitions

The requirements.txt maybe empty. To spin up the server and clients:

docker-compose up --build

To tear down the machines:

docker-compose down

Front End

Your implementation must include a view of your a-chess system. You don’t necessarily need graphics for this. Here is a Unicode text display of the initial board state.

♜♞♝♛♚♝♞♜
♟♟♟♟♟♟♟♟




♙♙♙♙♙♙♙♙
♖♘♗♕♔♗♘♖

Here is the board state for the checkmate shown in the table above.

♜♞♝♛♚♝♞♜
  ♟♟ ♕♟♟
♟♟
    ♟   
  ♗ ♙    
          
♙♙♙♙ ♙♙♙
♖♘♗ ♔ ♘♖

If you choose to represent your server state like this, then unlike me, use a mono-spaced font (that supports these Unicode glyphs) and a bigger font size! Also, clear the screen/console after each every 100 ms.

Submission

.
├── code
│   ├── docker-compose.yml
│   ├── Dockerfile
│   ├── a_chess.proto
│   ├── node.py  # or other python files
│   └── requirements.txt
├── COLLABORATORS
├── media
│   └── demo.gif
└── readme.md

2 directories, 8 files

Given above is a possible project structure. The collaborators file should contain a comma-separated list describing who you worked with and text description describing the nature of the collaboration. This information could be listed in three fields as in the example is below:

Christan Grant, cgrant@ou.edu, Instructor of CS [4|5]113.
https://docs.docker.com/engine/reference/builder/#env, Stuck at tzdata prompt during build.
https://grpc.github.io/grpc/python/, GRPC Documentation.
https://github.com/grpc/grpc/tree/v1.20.0/examples/python/helloworld, hello-world example.

The readme.md file should contain a walk through of your Python files and other source code you may write including a demo.gif at the top demonstrating the running of the machines playing a-chess described above.

Submit all source code to a private github repository named cs4113fa21-fproj or cs5113fa21-fproj. Submit a link to the private repository to Canvas. Also, you must add @cegme and @simurgh9 as collaborators to the repository. Code must accessible by the instructor and tashfeen to receive any credit. The video/annotated .gif should also be uploaded.

This is project may not be done in groups. Any code copying is subject to the university’s academic dishonesty policy. Any websites or discussion should be added to a COLLABORATORS file.

PS. Prof. Grant wrote additional instructions about submission material, final presentation etc.

---

Back to CS 4|5113