Multi-player fully distributed game lab
Distributed systems
The goal of these labs is to implement several synchronization algorithms. For this we will use a small multi-player board game. The provided version does not manage the synchronization between players. It leads to a final state where several players have a different view on the results. You will have to implement several algorithms seen during the lessons.
- Centralized approach (as baseline)
- Token-based approach
- Ricart and Agrawala mutual exclusion
- Ernest Chang and Rosemary Roberts. An improved algorithm for decentralized extrema-finding in circular configurations of processes. Communications of the ACM, 22(5) :281, 283, 1979. 2
- Edsger Wybe Dijkstra. Solution of a Problem in Concurrent Programming Control. Communications of the ACM, 8(9) :569, 1965.
The associated files are available here
The game
The board game is a 3x3 board game where each tile has three different possible elements
- An horizontal arrow (the three top tiles in the example bellow)
- A vertical arrow (the center-left tile in the example bellow)
- A chest (in the center tile in the example bellow)
P0
██ ██ ██ ██ ██ ██
█ █ █ █ █ █
█──────────────█ █──────────────█ █──────────────█
█──────────────█ █──────────────█ █──────────────█
█ █ █ █ █ █
██ ██ ██ ██ ██ ██
[== ] [=== ] [= ]
██████████ ██████████ ██
██░░░░░░░░░░██ ██░░░░░░░░░░██ █║║█
█ ▀▀▀▀▀▀▀▀▀▀ █ █ ▀▀▀▀▀▀▀▀▀▀ █ █ ║║ █
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄█ █▄▄▄▄▄▄▄▄▄▄▄▄▄▄█ ║║
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄█ █▄▄▄▄▄▄▄▄▄▄▄▄▄▄█ ║║
█░░░░░║╬╬║░░░░░█ █░░░░░║╬╬║░░░░░█ █ ║║ █
█░░░░░║╬╬║░░░░░█ █░░░░░║╬╬║░░░░░█ █║║█
████████████████ ████████████████ ██
[== ] [== ] [=== ]
██████████
██ ██ ██░░░░░░░░░░██ ██ ██
█ █ █ ▀▀▀▀▀▀▀▀▀▀ █ █ █
█──────────────█ █▄▄▄▄▄▄▄▄▄▄▄▄▄▄█ █──────────────█
█──────────────█ █▄▄▄▄▄▄▄▄▄▄▄▄▄▄█ █──────────────█
█ █ █░░░░░║╬╬║░░░░░█ █ █
██ ██ █░░░░░║╬╬║░░░░░█ ██ ██
████████████████
[==== ] [==== ] [= ]
Scores: [0]
The position of the players are on the upper left space of each tile. In the example player 0 is on the upper left tile. When a player moves, if the target tile is ready, the corresponding action activates and the timer for the tile is reinitialized. The tile is ready when the gauge below the tile is full. The actions are the following:
- Horizontal (resp. vertical) arrow: horizontal (resp. vertical) mirror of the board
- Chest: Score one point
The game ends after 10 moves for each player. At the end of the game the moves are displayed in the order they were received. As an example, the output for a two player game would be:
The screen of player 0:
[(1, 0, -1), (0, 0, -1), (1, -1, 0), (0, 0, -1), (1, 0, 1), (0, -1, 0), (1, 1, 0), (0, 0, 1), (1, -1, 0), (0, 0, 1), (0, 0, 1), (1, 0, -1), (0, 0, -1), (1, 1, 0), (0, 0, -1), (1, 1, 0), (0, 1, 0), (1, 0, -1), (0, 0, -1), (1, 1, 0)]
[0, 3]
█ █ █ █ ██ █ █ █ █
█ █ █ █ █ █ █ █ █ █
The screen of player 1:
[(1, 0, -1), (1, -1, 0), (0, 0, -1), (1, 0, 1), (0, 0, -1), (1, 1, 0), (0, -1, 0), (1, -1, 0), (0, 0, 1), (1, 0, -1), (0, 0, 1), (0, 0, 1), (1, 1, 0), (0, 0, -1), (1, 1, 0), (0, 0, -1), (1, 0, -1), (0, 1, 0), (1, 1, 0), (0, 0, -1)]
[1, 3]
█ █ █ █ ██ █ █ █ █
██ █ █ █ █ █ █ █ █
In both case the first line is the sequence of movement. Both start with (1, 0, -1) meaning both consider that the first move is done by player P1 who moves vertically downward: The horizontal movement is 0, while the vertical movement is -1
At the end of this game, player 0 consider the final score is [0, 3] while player 1 consider it is [1, 3].
The last part is a time-diagram showing the order of the moves. From the point of view of player 0, the second move is done by P0 while from the point of view of player 1, it is by P1
Minimized version
As the board game is quite large, a smaller version is also available
P0
<---> <---> <--->
[== ] [=== ] [= ]
█████ █████ ^
█░░░█ █░░░█ |
▀▀▀▀▀ ▀▀▀▀▀ v
[== ] [== ] [=== ]
█████
<---> █░░░█ <--->
▀▀▀▀▀
[==== ] [==== ] [= ]
Scores: [0]
Provided software architecture
Display
$ python3 display.py --help
usage: GUI [-h] [-p PORT] [-n NB] [-m]
Show one player gameboard
options:
-h, --help show this help message and exit
-p PORT, --port PORT
-n NB, --nb NB
-m, --mini
The display part of the game. It listen on a particular port using TCP, it needs to know how many players there are. If you add the -m flag, it will use the Minimized version.
Player
Two players are available. A player controlled by the keyboard, and a player playing randomly. Each player needs an id. For example in there are three players, the id must be 0, 1, 2. The also need the port of the displays send them the moves.
The random player will play 10 random moves:
$ python3 ./player.py
Usage : code.py player_id port1 port2 port3
The keyboard player will send the 10 moves according to the key pressed:
$ python3 ./player_kb.py
Usage : code.py player_id port1 port2 port3
Demo
Open four terminals in which you run
Terminal 0:
python3 display.py -m -n 2 -p 9000
Terminal 1:
python3 display.py -m -n 2 -p 9001
Terminal 2:
python3 player_kb.py 0 9000 9001
Terminal 3:
python3 player_kb.py 1 9001 9000
Demo zellij
Zellij is a terminal multiplexer which will helps displaying multiple terminal inside one
All the documentation is available here: https://zellij.dev/
As an example, running zellij --layout layout_two_mini_random.kdl produce the following:
┌ python3 display.py -m -n 2 -p 9000 ────────┐┌ python3 display.py -m -n 2 -p 9001 ────────┐
│P0 P1 ││P0 P1 │
│ ││ │
│ <---> <---> <---> ││ <---> <---> <---> │
│ ││ │
│[== ] [=== ] [= ] ││[== ] [=== ] [= ] │
│ ││ │
│ ││ │
│ ││ │
│ █████ █████ ^ ││ █████ █████ ^ │
│ █░░░█ █░░░█ | ││ █░░░█ █░░░█ | │
│ ▀▀▀▀▀ ▀▀▀▀▀ v ││ ▀▀▀▀▀ ▀▀▀▀▀ v │
│[== ] [== ] [=== ] ││[== ] [== ] [=== ] │
│ ││ │
│ ││ │
│ ││ │
│ █████ ││ █████ │
│ <---> █░░░█ <---> ││ <---> █░░░█ <---> │
│ ▀▀▀▀▀ ││ ▀▀▀▀▀ │
│[==== ] [==== ] [= ] ││[==== ] [==== ] [= ] │
│ ││ │
│ ││ │
│ ││ │
│ ││ │
│Scores: [0, 0] ││Scores: [0, 0] │
│ ││ │
│ ││ │
│ ││ │
└────────────────────────────────────────────┘└────────────────────────────────────────────┘
Waiting to run: bash -c python3 ./player.py 0 9000 9001 & python3 ./player.py 1 9001 9000
<ENTER> to run, <Ctrl-c> to exit
Pressing Enter then runs the line on the bottom of the screen, running two different random players.
The available layouts are:
- layout_one_player.kdl: Runs the game for one player with the keyboard
- layout_two_random.kdl: Runs the game for two random players
- layout_two_mini_random.kdl: Runs the game for two random players using the small tiles
- layout_four_random.kdl: Runs the game for four players using small tiles
If you have an error while running the display code, it certainly means the terminal is too small. The error then looks like:
$ python3 ./display.py
Traceback (most recent call last):
File "./display.py", line 128, in <module>
wrapper(main) # To start main with graphical interface initialization
^^^^^^^^^^^^^
File "/usr/lib/python3.11/curses/__init__.py", line 94, in wrapper
return func(stdscr, *args, **kwds)
^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "./display.py", line 93, in main
display_curses(board, stdscr)
File "./display.py", line 69, in display_curses
put_at(screen, sp, x*dx, y*dy+1)
File "./display.py", line 59, in put_at
screen.addstr(y+idx, x, line)
_curses.error: addwstr() returned ERR
Subject of the labs
The goal will be to implement the following algorithms:
- Centralized approach
- Distributed approach
- Ricart and Agrawala mutual exclusion
- The bakery algorithm of mutual exclusion from Lamport
- The distributed synchronized lists
The current network architecture is the one on the left of the following picture. The centralized is the one in the middle. The distributed is the one on the left.
The red elements are the code of player.py (or player_kb.py), the blue elements are the code of display.py and should not be modified. The green elements are the one you have to program. We keep the hypotheses of non-faulty programs and communications. We also assume having the port number available for all elements. For example in the distributed version, display with port number 9000 can be associated with the distributed synchronization element using the port 10000
Code to provide
A server named server.py with the following usage
$ python3 ./server.py
Usage : server.py local_port port1 port2 port3
Where the local_port is the one used to receive the messages from the players, and port1, ... are the port for the display elements
The codes for the distributed algorithms must be called distributed_code.py with code replaced by ricart, bakery, lists depending on the implemented algorithm. The usage will always be:
$ python3 ./distributed_lists.py
Usage : distributed_lists.py n id display0 display1 .. displayn-1 systemp0 systemp1 ... systempn-1
where n is the number of players, id between 0 and n-1 the id of the player. display? are the port of the display modules, while systemp? are the ports used to contact the other distributed applications.
Verification
To check if your code is working, you can use a zellij as explained before to compare the output of the different programs.