Coordination and Agreement

Question 1

Why are most failure detectors unreliable?

Answer 1

• Return suspected /unsuspected given the identity of a process
• The response from a local failure detector is only as good as the information available at that process

Question 2

Why is distributed mutual exclusion required

Answer 2

Mutual exclusion is required to prevent interference and ensure consistency when accessing shared resources

Question 3

How does distributed mutual exclusion differ from the

critical section problem in the OS domain?

Answer 3

Neither shared variables nor single-kernel facilities are available.

Distributed mutual exclusion is solely based on message passing.

Question 4

State the problem of using a server for distributed mutual exclusion.

Answer 4

susceptible to single point of failure

Question 5

What is the essential requirement ME1 for mutual exclusion?

Answer 5

ME1: (safety)

At most one process may execute in the critical section (CS) at a time

Question 6

What is the essential requirement ME2 for mutual exclusion?

Answer 6

ME2: (liveness)

Requests to enter and exit the critical section eventually succeed

Question 7

What is the essential requirement ME3 for mutual exclusion?

Answer 7

ME3: (→ ordering)

If one request to enter the CS happened-before another, then entry to the CS is granted in that order

Question 8

What is the implication of ME2?

Answer 8

ME2 implies freedom from both deadlock and starvation. Absence of starvation is one fairness condition

Question 9

As a stronger fairness condition why does ME3 require logical clocks?

Answer 9

If all requests related by happened-before, then it is not possible for a process to enter the CS more than once while another process waits to enter