Systèmes Répartis | 13 - Algorithme de Ricart & Agrawala [RA 81]

Algorithm of Ricard and Agrawal (1981)

Overview of the Algorithm

• The video discusses the Ricard and Agrawal algorithm proposed in 1981, which is designed to minimize the number of messages required for mutual exclusion in distributed systems.

• This algorithm is categorized under class C1 and aims to optimize message types used in mutual exclusion processes.

Message Types and Optimization

• The algorithm reduces the necessity for acknowledgment messages, focusing on two primary message types: requests and replies. It eliminates unnecessary acknowledgments to streamline communication.

• It operates under the assumption that a reliable transport network is available, where message transit times may vary but errors are not present.

Complexity Analysis

• The complexity of this algorithm is defined as requiring 2n - 1 messages for a process to enter its critical section, where n represents the number of processes involved. This includes sending a request message and receiving responses from other processes.

• A favorable response from other processes indicates permission to enter the critical section, with maximum complexity occurring when all responses are positive.

Request Handling Mechanism

• When a process wishes to enter its critical section, it generates a timestamped request message that is broadcasted to all other processes in the system. This mechanism ensures that all nodes are aware of pending requests.

• Upon receiving a request, each process can either respond immediately or defer their response based on their current state regarding access to their own critical sections. Immediate responses indicate readiness while deferred responses suggest ongoing operations within critical sections by those processes.

Response Management

• Processes maintain an order of requests based on timestamps; if a process receives a newer request than its own current operation, it will delay its response until it can safely grant access without conflict. This prioritization helps manage concurrent access effectively.

• The decision-making process involves comparing timestamps between incoming requests and existing ones; higher priority requests lead to delayed responses from lower priority processes until they can safely grant access without violating mutual exclusion principles.

Implementation of the RA Algorithm Protocol

Local Declarations in Processes

• The RA algorithm protocol requires local declarations for each process, specifically two declarations for processes P1 and Pn. Variables include OS1 (an integer), initialized to 0, plus infinity, and hs values.

• The expected number of responses is calculated as 1 minus 1 due to having one process involved, leading to a total of zero expected responses.

Response Handling and Sequence Numbers

• A deferred response array is defined with Boolean values. The variables oracen and hacen represent the sequence numbers chosen by PI for request stamping; oracen is the own sequence number while hacen tracks the highest sequence number seen by PI.

• The variable hacen is initialized to zero and updates the timestamp whenever a request is compared against existing requests.

Message Types and Protocol Components

• When a process receives a message of type "request," it delays its response accordingly. This delay updates the corresponding entry in the deferred response array.

• The protocol consists of two components: one directly related to exclusion requests from PI, and another that updates local variables based on messages received from other sites.

Critical Section Access Control

• Accessing shared variables must be protected by mutual exclusion, which has been intentionally omitted from this discussion for clarity.

• Each process sends out request messages while waiting for responses. If all expected responses are received (i.e., zero remaining), it can enter its critical section.

Prioritization Logic in Request Handling

• Upon receiving a request message, processes check their respective arrays to determine if they should defer their response based on priority rules established within the protocol.

• Responses are sent back only when necessary; if a process's request does not meet certain criteria or priorities, it will not respond immediately to minimize unnecessary messaging.

Updating Timestamps and Priority Calculations

• When processing incoming requests, timestamps are updated using maximum values between current timestamps and those received in requests.

• Priority calculations involve comparing sequence numbers; if conditions are met (e.g., K > A or K = A with I < J), then processes may defer their responses according to established rules.

This structured summary captures key insights into the implementation details of the RA algorithm protocol as discussed in the transcript.

Response Handling in Algorithms

Overview of Response Management

• The process involves deferring responses, indicating a different response mechanism compared to G. This suggests a prioritization in handling messages.

• Upon receiving a response, the variable for expected responses is decremented by one, which is part of the RA-81 algorithm developed by Rikara and Agawal in 1981. This algorithm addresses results management within the context of excuses in distributed systems.

Algorithm Classifications

• The discussion introduces the second algorithm from class 1, hinting at future exploration into class 2 algorithms that focus on game theory.

• There is an anticipation to cover another algorithm from RAA (1983), emphasizing simplicity and encouraging questions through social media platforms like Facebook, Twitter, and Instagram.