Unit IV

1
 UNIT - IV
Coordination: Clock Synchronization - Logical Fault Tolerance: Introduction to fault tolerance -
clocks - Mutual Exclusion: Centralized Concepts - Failure models - Failure masking by
algorithm - Distributed Algorithm - Token-ring redundancy - Reliable client server
algorithm - Decentralized Algorithm - Election communication: Point to point communication -
Algorithms: Bully algorithm - Ring algorithm - RPC semantics in the presence of failures - Reliable
Elections in wireless environment and large Group Communication: Atomic multicast -
scale systems Distributed commit - Recovery

2
MUTUAL EXCLUSION

3
MUTUAL EXCLUSION
• When a process is accessing a shared variable, the process is
said to be in Critical Section.

• No two process can be in the same critical section at the

same time.

4
Introduction
• To grant mutual exclusive access to resources by processes
• To prevent inconsistency , corruption of data due to simultaneous
access
Algorithm Categories :
1. Token-based
2. Permission-based

5
 Token-based
• Special message called token passed between processes
• Token holding process allowed to access shared resource
• After usage token given to next process
• If process not interested in resource access, pass it to next process

Properties:
1. Avoid starvation
2. Avoid deadlock

process should be organized in a manner that all of them

should get the token

6
Permission-based
• Process wants to access resource requires permission of other
processes

7
Algorithms
1. Centralized
2. Distributed
3. Token ring
4. Decentralized

8
Centralized algorithm
• Permission-based
• Process wants to enter critical section, sends
“request” msg to coordinator
• Coordinator checks critical section
- Already used by another process , blocks requesting process or sends
“permission denied” msg
- Not used by another process, sends “grant” msg

9
a) Process 1 asks the coordinator for permission to enter a
critical region. Permission is granted

b) Process 2 then asks permission to enter the same

critical region. The coordinator does not reply.

c) When process 1 exits the critical region, it tells the

coordinator, which then replies to 2 10
Advantage:
• Ensures presence of only one process in critical section
• Request granted in order in which they are received
• Easy to implement – only 3 messages
(request, grant, release)
Disadvantage:
• Coordinator crash – entire system down

11
 Distributed algorithm
• Permission based
• Process wants to enter CS - sends message to all other processes
Msg(name of CS, process id, current time)
• Receiving process
- Not using CS, don’t want CS , send “OK”
- Already in CS, don’t reply, queues request
- Wants to enter CS, compare with its timestamp
Timestamp of receiver < sender
- Queues request, don’t reply
- Timestamp of receiver > sender
- Sends “OK” msg

12
Distributed Algorithm

a) Two processes want to enter the same critical region at the

same moment.
b) Process 0 has the lowest timestamp, so it wins.
c) When process 0 is done, it sends an OK to p2, so that 2 can
now enter the critical region.
13
Advantage :
• No single point of failure

Disadvantage:
• Need permission from all process – if anyone crash, no
response

• Each process must maintain group members list

14
Token ring algorithm
• Token based
• Processes – connected as logical ring
• Each process knows who is next?
• Token circulates around ring
• Initially token given to process0 and passed to next
process
• Token holder is allowed to enter CS
• If any process don’t want to enter CS, just passes the token
to next process

15
Token Ring Algorithm

a) An unordered group of processes on a

network.
b) A logical ring is constructed in software.
16
Disadvantage:
1. Token lost
2. Process crash

17
 Decentralized Algorithm
• Permission based

• More fault-tolerant than the centralized approach.

• Based on the Distributed Hash Table (DHT) system structure

• Object names are hashed to find the node where they are stored

• n replicas of each object are placed on n successive nodes

• Hash object name to get addresses

• Every replica has a coordinator for controlling the access by

concurrent processes 18
Decentralized Algorithm
• Coordinators respond to requests at once: Yes or No

• For a process to use the resource it must receive permission

from m > n/2 coordinators.
• If the requester gets fewer than m votes it will wait for a random
time and then ask again.

• If a request is denied, or when the CS is completed, notify

the coordinators who have sent OK messages, so they can
respond again to another request.

19
Analysis
• More robust than the central coordinator approach.

• If one coordinator goes down others are available.

• If a coordinator fails and resets then it will not remember having

granted access to one requestor, and may then give access to
another.
• According to the authors, it is highly unlikely that this will lead to a
violation of mutual exclusion.

20
Analysis
• If a resource is in high demand, multiple requests will be
generated by different processes.
• High level of contention
• Processes may wait a long time to get permission
• Resource usage drops.

21
22
Election algorithms

23
 Need for leader
• Many distributed algorithms require one process to act as coordinator
• If all processes are same with no distinguishing characteristics, highest
numbered process will be selected as leader
• Goal of election algorithm:
To ensure that when an election starts, it concludes with all
processes agreeing on who the new coordinator is to be.
Assumption:
- Every process know process number of other processes
- Do not know which one are currently up/down
Algorithms
• Traditional election algorithm
1. Bully algorithm
2. Ring algorithm
• Election in wireless environment
• Election in large-scale systems
 Bully algorithm
• Highest numbered process serves as a coordinator

• Process (p) initiate election – if it notices that no longer responding coordinator

• Send election message to all processes with highest number

• If no one responds, (p) wins election and becomes coordinator

• If higher-one answers for election message, (p) becomes silent and the higher-ones
conduct election

• If previous coordinator up – conduct election

The Bully Algorithm (1)

The bully election algorithm

• Process 4 holds an election
• Process 5 and 6 respond, telling 4 to stop
• Now 5 and 6 each hold an election
The Bully Algorithm (2)

d) Process 6 tells 5 to stop

e) Process 6 wins and tells everyone
 Issues

Suppose crashed nodes comes back on line:

• Sends a new election message to higher numbered processes

• Repeat until only one process left standing
• Announces victory by sending message saying that it is
coordinator (if not already coordinator)
• Existing (lower numbered) coordinator yields

Hence the term 'bully'

Ring algorithm
• Process physically / logically ordered
• Each process knows it’s successor
• Process initiate election – if it notices that no longer response from
coordinator
• Sends election message to successor, with its process number (in a list)
• If successor down, message goes to next member in ring, each process add
its number to list
• Algorithm repeated until message reaches the initiated process
• Process with highest number in the list becomes coordinator
• Selected coordinator will be circulated to each process
2 and 5 start election message independently.
Both messages continue to circulate.
Eventually, both messages will go all the way around
2 and 5 will convert Election messages to COORDINATOR messages.
All processes recognize highest numbered process as new coordinator.
Issues
1. Does it matter if two processes initiate an election?
Just circulate extra messages and increase
network traffic ( not harmful )
2. What happens if a process crashes during the election?
 Election in Wireless networks
• Following assumptions not applicable
• Message passing is reliable
• Topology of network doesn’t change

Algorithm:

Goal:
Node with high capacity & battery lifetime elected as leader

• Any node(source) start election by sending “ELECTION”

message to its neighbors(within range)
• If a node receives election message for first time
- designate sender as parent
- forward election message to its neighbors except parent
- wait for acknowledge from its neighbors before acknowledging its parent
• If a node receives election message other than its designated parent
- acknowledge the receipt
- also send report information(battery lifetime, resource capacity)
• While receiving acknowledgement from neighbors
- compare and select high capacity neighbor
- pass this information to parent along with ack
• In this way source will decide that which node can be selected as leader
and broadcast this information to all other nodes
(a) – initial network
(b) - node ‘a’ send election message to its neighbors
(c) – node ‘b’ send election message to its neighbors
(d) – node ‘c’ and ‘g’ send election message to its neighbors
(e) – node ‘e’ and ‘h’ send election message to its neighbors
(f) – each node send acknowledgement along with report information
source node ‘a’ will elect ‘h’ as leader ( since h has high capacity i.e 8 )
and broadcast this information to all
 Issues
1. What happens if more than one process initiates
election?
- Each source tag its election message with unique identifier
- Other processes will participate only in the election with
highest identifier
2. What happens when network get partitioned?
3. What happens when nodes join/leave?
 Elections in large-scale systems
• Small systems – single coordinator
• Large systems - several nodes should actually be selected. Eg. Super peers in peer to peer network

The following requirements need to be met for super-peer selection:

1. Normal nodes should have low-latency access to super peers.
2. Super peers should be evenly distributed across the overlay network.
3. There should be a predefined portion of super peers relative to the total number of nodes in the overlay network.
4. Each super peer should not need to serve more than a fixed number of normal nodes.

Realized in overlay network

• either structured (as in DHT-based systems),
• or randomly unstructured (as, for example, can be realized with gossip-based solutions).

43
DHT-based systems
• Reserve a fraction of the identifier space for super peers
• Each node receives a random and uniformly assigned m-bit identifier

Eg.
• reserve the first (i.e., leftmost) k bits to identify super peers.
• N superpeers, then the first ceil(log2(N)) bits of any key can be used to identify these nodes
• m = 8 and k = 3.
• Process with identifier ID can check whether it is a super peer by looking up ID ∧ 11100000 to see if
this request is routed to itself.

44
Gossip-based solutions
• need to place N super peers evenly throughout the overlay.

The basic idea is simple:

• A total of N tokens are spread across N randomly chosen nodes.
• No node can hold more than one token.
• Each token represents a repelling force by which another token is inclined to move away.
• The net effect is that if all tokens exert the same repulsion force, they will move away from each other and
spread themselves evenly in the geometric space.
• This approach requires that nodes holding a token learn about other tokens.
• To this end, we can use a gossiping protocol by which a token’s force is disseminated throughout the
network.
• If a node discovers that the total forces that are acting on it exceed a threshold, it will move the token in the
direction of the combined forces
• When a token is held by a node for a given amount of time, that node will promote itself to superpeer.

45
Gossip-based solutions

46