- Project description
- Files description
- Running with zellij
- Algorithmic complexity reference
- Reference
The objective of the project is to implement several synchronization algorithms. To achieve this, we use a small multiplayer game. The files player.py and display.py do not handle synchronization between players, which leads to a final state where each player has a different view of the results. Therefore, several algorithms have been implemented to solve this problem.
The game’s rules and explanations are detailed in the GAME.md file.
-
Centralized approach: A single coordinator is responsible for granting access to the critical section. Players must request permission from this central authority before making a move.
-
Token-based approach: A unique token circulates among players. Only the player holding the token can access the critical section, ensuring mutual exclusion.
-
Ricart and Agrawala mutual exclusion: A fully distributed algorithm where a player sends timestamped requests to all others and waits for replies before entering the critical section. This ensures total ordering of events.
-
Naimi-Trehel approach: An optimized token-based method where the token is passed along a dynamic logical tree based on request paths, reducing unnecessary message passing.
-
Maekawa approach: Each player communicates only with a predefined subset (quorum) of other players. Mutual exclusion is achieved when all members of the quorum grant permission, minimizing communication overhead.
.
├── README.md
├── GAME.md
├── EXPLANATION.md
├── layout
│ ├── layout_server_*.kdl
├── srv
│ ├── server_*.py
├── display.py
├── player.py
├── sprites.py
├── sprites_bomb.py
├── sprites_micro.py
├── sprites_small.py
└── zellij
-
GAME.md: Game-specific documentation explaining how it works and its rules. -
README.md: Main project description file. Presents the purpose and usage of the project. -
EXPLANATION.md: This file summarizes five algorithms with their termination methods, complexity, and related code.
-
display.py: Acts as the main game server. It usescursesto display the board, receives player actions, and applies game logic (movement, bombs, scoring…). -
player.py: Client script used by each player to send their moves to the server. Can simulate automatic (random) behavior. -
server.py: Basic version of the server without synchronization. Serves as a reference to understand consistency issues between players. -
server_jeton.py: Implements synchronization based on token passing. -
server_ricart.py: Implements the Ricart and Agrawala mutual exclusion algorithm, which uses timestamped distributed requests. -
server_naimi.py: Implements the Naimi-Trehel method, an optimized token-based algorithm using a logical tree structure. -
server_maekawa.py: Implements the Maekawa algorithm, which uses quorums to reduce the number of messages needed for mutual exclusion.
sprites.py/sprites_bomb.py/sprites_micro.py/sprites_small.py: Contain variables or functions defining ASCII sprites or characters used to represent players, bombs, etc., on the screen.
layout_server.kdland variants (layout_server_jeton.kdl, etc.): Configuration files used to define the process/server layout for each algorithm version. The.kdlformat structures logical topologies.
zellij: File used to automate or manage terminal sessions with Zellij, a terminal workspace manager.
To run the different synchronization approaches, simply execute the following command:
./zellij --layout layout_server.kdlFor a detailed study of the termination conditions and theoretical message complexity of the synchronization algorithms implemented in this project, please refer to the EXPLANATION.md.
-
This work is inspired by content from the Multi-player Fully Distributed Game Lab – IRIT, as well as lectures and guidance provided by DA-COSTA Georges (IRIT).