Coordination and Agreement

Question 1

What is the idea behind network partition?

Answer 1

In any particular interval of time, communication between some processes may succeed while communication between others is delayed

Question 2

What is a correct process?

Answer 2

A process that exhibits no failures at any point in the execution under consideration

Question 3

What is a failure detector?

Answer 3

A service that processes queries about whether a particular process has failed

Question 4

What do unreliable failure detectors do?

Answer 4

Produce one of two values of a process: unsuspected or suspected

Question 5

What does the unsuspected value produced by an unreliable failure detector mean?

Answer 5

The detector has recently received evidence suggesting that the process has not failed

Question 6

What does the suspected value produced by an unreliable failure detector mean?

Answer 6

The detector has some indication that the process may have failed

Question 7

What is the difference between a reliable failure detector and an unreliable failure detector?

Answer 7

The reliable failure detector is always accurate in detecting a process’ failure. It only produces the unsuspected or failed values.

Question 8

How is an unreliable failure detector implemented?

Answer 8

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.

Question 9

How can an unreliable failure detector be made into a reliable one?

Answer 9

Choose D to be an absolute bound on message transmission times

Question 10

What are the requirements for mutual exclusion?

Answer 10

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

Question 11

What is client delay (mutual exclusion)?

Answer 11

The time that a process incurred at each entry and exit operation

Question 12

What is synchronization delay (mutual exclusion)?

Answer 12

The time between a processor leaving a critical section and before the next process enters critical section

Question 13

What is the central server algorithm?

Answer 13

Server grants a unique token that allows the user to enter critical session. Request is queued if the token is being used.

Question 14

What are the advantages of the central server algorithm?

Answer 14

3 messages per entry/exit

Question 15

What are the disadvantages of the central server algorithm?

Answer 15

Central point of failure; central performance bottleneck; impossible to achieve in order fairness with an asynchronous network

Question 16

What is Ricart and Agrawala’s algorithm?

Answer 16

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.

Question 17

Can a ring based algorithm tolerate a crash failure of any single process?

Answer 17

No

Question 18

When can the central server algorithm tolerate a crash?

Answer 18

When the process that fails is a client process that neither holds nor has requested the token

Question 19

What are the election requirements?

Answer 19

Safety - the variable elected is nil or the process elected; Liveness - All processes participate and eventually set elected to the same process or crash

Question 20

What is the bully algorithm?

Answer 20

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

Question 21

What are the characteristics of reliable multicast?

Answer 21

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

Question 22

What is the reliable multicast algorithm?

Answer 22

All correct processes receive all the multicast requests or none at all

Question 23

What are the characteristics of the consensus problem?

Answer 23

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

Question 24

What is the Byzantine generals problem?

Answer 24

Three or more generals are to agree to attack or retreat. Lieutenants must decide whether to attack or retreat.

Question 25

Is there an algorithm that can guarantee consensus in an asynchronous system?

Answer 25

Nope, because a crashed process is indistinguishable from a slow one

Question 26

What can you do to make consensus possible in an asynchronous system?

Answer 26

Mask any process failures that occur; failure detectors; randomization