Token-Based Distributed Group Mutual Exclusion Algorithm with Quorums (TQGmx) Implementation This repository contains a Python-based implementation of the "A Token-Based Distributed Group Mutual Exclusion Algorithm with Quorums" (TQGmx) as described in the paper by Hirotsugu Kakugawa, Sayaka Kamei, and Toshimitsu Masuzawa. This implementation is designed to run across multiple physical systems using socket programming to simulate an asynchronous message-passing distributed system.
About the Algorithm The TQGmx algorithm addresses the group mutual exclusion problem, a generalization of traditional mutual exclusion where processes within the same group can simultaneously enter a critical section (CS), but processes from different groups cannot.
Key features of the algorithm include:
Token-Based: The algorithm operates using a unique "main token" and dynamically generated "subtokens" to control access to the critical section. A process obtaining a token can enter a critical section.
Coteries and Quorums: To optimize message complexity, the algorithm utilizes coteries as a communication structure. When a process requests to enter a CS, it sends messages to processes within a selected quorum, and these requests are then forwarded to the main token holder.
Asynchronous Message Passing: The system is modeled as an asynchronous distributed system where processes communicate via message passing over channels, with messages delivered within a finite but unbounded time, and an assumption of an error-free environment.
Concurrency Control: The main token holder aggregates requests in a queue and controls the order of granting access, implementing a priority scheme to manage concurrency and waiting times.
Message Complexity: The algorithm boasts an O(|Q|) message complexity in the worst case, where |Q| is the size of the quorum adopted.
Implementation Details This implementation adheres to the core principles of the TQGmx algorithm, simulating the distributed environment across physical machines:
Python: The entire system is implemented in Python, leveraging its networking capabilities.
Socket Programming: Inter-process communication across different physical systems is handled using Python's socket module. Each process (node) will run as a separate Python script, listening for incoming messages and sending messages to other nodes as per the algorithm's requirements.
Distributed Processes: The design allows for running n processes (P_0,P_1,...,P_n−1) on separate physical machines, connected via a network.
Configuration: A configuration file (e.g., config.json) will define the network addresses (IP addresses and ports) of each process, enabling them to discover and communicate with each other. This configuration will also define the coterie structure and group assignments.
Message Handling: Each process will implement handlers for different message types (e.g., request, token, subtoken, acquired, release, leave, ack) to manage the state, queues, and token transfers as described in the paper's formal description (e.g., Section 3.4, Figures 3, 4, 5).
Initial Token Distribution: Process P0 will play a special role in system startup, initializing and holding the main token as per the algorithm.
Getting Started Prerequisites Python 3.x installed on all physical machines.
Network connectivity between all machines where processes will be run.
Setup Clone the repository:
Bash
git clone https://github.com/Akshay-4141/DistributedComputing.git cd DistributedComputing Configure config.json: Create a config.json file (if not already present) that defines the n processes, their IP addresses, and port numbers. Ensure these IP addresses are reachable from other machines and the ports are open.
Example config.json:
JSON
{ "processes": [ {"id": 0, "ip": "192.168.1.101", "port": 5000}, {"id": 1, "ip": "192.168.1.102", "port": 5001}, {"id": 2, "ip": "192.168.1.103", "port": 5002} ], "coterie_type": "majority", "groups": { "group_A": [0, 1], "group_B": [2] } }
(Note: You might need to implement logic to generate coteries based on the chosen type, as described in Section 2.3 of the paper.)
Run the processes: On each physical machine, run the main process script, specifying its own process ID. For instance, if process.py is your main script:
On Machine 1 (for P0):
Bash
python process.py --id 0 On Machine 2 (for P1):
Bash
python process.py --id 1 And so on for all n processes.
Files Structure process.py: Main script for each distributed process, handling incoming messages and executing the TQGmx algorithm logic.
messages.py: Defines the message structures and types used for inter-process communication.
quorum.py: Contains logic for coterie and quorum management (e.g., selection and verification as per Definition 2 ).
config.json: Configuration file for processes, their addresses, and group assignments.
generate_config.py: (Optional) A utility script to generate the config.json based on desired parameters.
log_node_X.log: Log files for each node to track events, messages, and critical section entries/exits.
Running the Simulation Once all processes are running on their respective machines, they will start communicating and attempting to enter the critical section based on the TQGmx algorithm. You can observe the behavior and performance through the console output and log files of each process.
References
A Token-Based Distributed Group Mutual Exclusion Algorithm with Quorums