Overview:
- The Chandy-Lamport algorithm is designed to capture a consistent global state in a distributed system using control messages called markers.
- This algorithm works in systems with FIFO (First-In-First-Out) communication channels.
Marker Sending Rule for Process
- Process
$( p_i )$ records its local state. - For each outgoing channel
$( C )$ that hasn't received a marker yet,$( p_i )$ sends a marker along$( C )$ before sending any further messages on$( C )$ . Marker Receiving Rule for Process$( p_j )$ :
- Upon receiving a marker along channel
$( C )$ :- If
$( p_j )$ has not yet recorded its state:-
$( p_j )$ records the state of$( C )$ as empty. -
$( p_j )$ then records its own state and follows the Marker Sending Rule.
-
- If
$( p_j )$ has already recorded its state:-
$( p_j )$ records the state of$( C )$ as the set of messages received after$( p_j )$ recorded its state and before receiving the marker.
-
- If
- Overview: Utilizes permission-based approach and timestamps for mutual exclusion in distributed systems.
- Complexity: Requires 3(N-1) messages per critical section execution.
- Overview: Proposed by Ricart and Agrawala, it's a mutual exclusion algorithm for distributed systems, building upon Lamport's Algorithm.
- Algorithm: Uses REQUEST and REPLY messages for permission-based mutual exclusion. Requests are timestamped.
- Message Complexity: Requires 2(N – 1) messages per critical section execution, including (N – 1) request messages and (N – 1) reply messages.
- Overview: Quorum-based mutual exclusion algorithm, distinct from permission-based approaches like Lamport’s and Ricart-Agrawala.
- Quorum Concept: Sites request permission from a subset called quorum, not every site.
- Messages: Utilizes REQUEST, REPLY, and RELEASE messages.
- Low message complexity: O(sqrt(N)) messages per invocation.
- Overview: Token-based mutual exclusion algorithm, derived from Ricart–Agrawala, utilizing REQUEST and REPLY messages.
- Token-Based Approach: Access to critical section granted via possession of a unique token, unlike non-token algorithms.
- Data Structures:
- RN[1…N]: Array to track largest sequence numbers received from each site.
- LN[1…N]: Array used by the token, with LN[j] representing the recently executed request's sequence number from site Sj.
- Queue Q: Maintains IDs of sites waiting for the token.
- Message Complexity: Requires either 0 or a maximum of N messages per critical section execution, depending on token ownership.
Lamport’s Bakery Algorithm is a classic algorithm for achieving mutual exclusion in a system of ( n ) processes that share memory. The algorithm is designed to ensure that no two processes are in the critical section simultaneously.A unique lexicographic order is defined on the tuple <token, pid> maintained for resolving conflict
- The algorithm uses a combination of timestamps and process IDs to ensure a unique ordering of processes.
- The timestamps are chosen in a way that mimics the behavior of customers taking a number in a bakery, thus the name "Bakery Algorithm".