Coordination and Agreement Flashcards
What is the idea behind network partition?
In any particular interval of time, communication between some processes may succeed while communication between others is delayed
What is a correct process?
A process that exhibits no failures at any point in the execution under consideration
What is a failure detector?
A service that processes queries about whether a particular process has failed
What do unreliable failure detectors do?
Produce one of two values of a process: unsuspected or suspected
What does the unsuspected value produced by an unreliable failure detector mean?
The detector has recently received evidence suggesting that the process has not failed
What does the suspected value produced by an unreliable failure detector mean?
The detector has some indication that the process may have failed
What is the difference between a reliable failure detector and an unreliable failure detector?
The reliable failure detector is always accurate in detecting a process’ failure. It only produces the unsuspected or failed values.
How is an unreliable failure detector implemented?
Each process sends an “I’m here” message to every other process every T seconds. Detector needs to receive message within T + D seconds or else it will report the process as suspected. D is a timeout value that reflect the observed network delay conditions.
How can an unreliable failure detector be made into a reliable one?
Choose D to be an absolute bound on message transmission times
What are the requirements for mutual exclusion?
Safety - one process is in critical section at a time; Liveness - requests to enter and exit the critical section eventually succeed; Ordering - First request for critical section should be the first granted entry to critical section
What is client delay (mutual exclusion)?
The time that a process incurred at each entry and exit operation
What is synchronization delay (mutual exclusion)?
The time between a processor leaving a critical section and before the next process enters critical section
What is the central server algorithm?
Server grants a unique token that allows the user to enter critical session. Request is queued if the token is being used.
What are the advantages of the central server algorithm?
3 messages per entry/exit
What are the disadvantages of the central server algorithm?
Central point of failure; central performance bottleneck; impossible to achieve in order fairness with an asynchronous network
What is Ricart and Agrawala’s algorithm?
When a process wants to enter critical section, it multicasts a request containing the process ID and Lamport timestamp to the other processes. The process can enter critical section once it receives N-1 replies. The process ID is used to break ties.
Can a ring based algorithm tolerate a crash failure of any single process?
No
When can the central server algorithm tolerate a crash?
When the process that fails is a client process that neither holds nor has requested the token
What are the election requirements?
Safety - the variable elected is nil or the process elected; Liveness - All processes participate and eventually set elected to the same process or crash
What is the bully algorithm?
The process with the highest id can elect itself by sending a coordinator message to the rest of the processes; a process with a lower id can begin an election by sending an election message to a higher id process and awaiting an answer. If process receives an election message, it sends answer message back and begins another election
What are the characteristics of reliable multicast?
Integrity - A process p delivers a message m at most once; Validity - if correct process multicasts message m, then it will eventually deliver m; Agreement - If a correct process delivers message m, then all other correct processes in group will eventually deliver m
What is the reliable multicast algorithm?
All correct processes receive all the multicast requests or none at all
What are the characteristics of the consensus problem?
Termination - eventually each process sets its decision; Agreement - the decision value of all correct processes is the same; Integrity - if the correct processes all proposed the same value, then any correct process in the decided state has chosen that value
What is the Byzantine generals problem?
Three or more generals are to agree to attack or retreat. Lieutenants must decide whether to attack or retreat.
