11.Coordination & Agreement Flashcards
2 Different algorithms to implement mutual exclusion?
- ring-based election
2. bully algorithm
Which process is elected (with respect to it’s identifier?)
The process with the largest identifier
Who can initiate an election?
Any process
Do the processed need to know the result of the election?
YA
In ring-based election algorithm, what should a receiver do If the identifier in the message is larger than it’s own?
Forward it unchanged
Become participant
In ring-based election algorithm, what should a receiver do If the identifier in the message is smaller than it’s own?
Forward message but with it’s own identifier
Become participant
What should the receiver in the ring-based election algorithm do if it’s already a participant upon receiving the message?
discard the message
become participant
When does election happen in the ring based election algorithm?
When the identifier in the message is equal to the receiver id
What should the receiver do once it has been elected?
Tell all processes
What do the other processes do upon finding out election has happened?
Pass on result
Become non-participating
Which system is synchronous and which asynchronous out of bully and ring?
Bully -> synchronous (timeouts)
Ring -> asynchronous
What are the three types of message in the Bully algorithM?
initiate Election
answer (Election)
coordinator (Announce election result)
What are the two timeouts in the bully algorithM?
If election result isn’t announced in T+T
If answer isn’t receiver in T
Describe process of bully election
- start election by sending it to each process with larger id
- f no answer consider itself elected and send coordinator message to all lower processes
