Question 6: Conferencing researchers
There are 10 researchers attending a conference. At the conference, the researchers either eat or think. To eat they need a bowl, a fork, and a knife. To think, they need a notepad and a pen.
The conference has only 1 bowl, fork, knife, notepad, and pen because the conference organizers were not able to get sponsors. Clearly, at any point in time, a maximum of 1 researcher can eat and a maximum of 1 researcher can think.
The organizers want to ensure that at any point in time, at least 1 researcher is eating and 1 researcher is thinking. For example, they want to avoid a situation wherein researcher 1 has the bowl, researcher 2 has the fork, researcher 3 has the knife, researcher 4 has the notepad, researcher 5 has the pen, and researchers 6-10 have nothing.
Can you suggest a mechanism to ensure this?
Solution coming up in the next post!
Solution for fault tolerant locks:
John should use leases, which are expiring locks. Processes acquire locks with a time limit and keep refreshing the lock (if they are still alive and using the database). If the database server does not receive a refresh request from a process and the lease has expired, it can grant the lease to another process. If the process that had originally held the lease comes back and tries to access the database, the database server can deny that request. (This is typically implemented by having the process present its lease for every access, so that the database can verify the lease holder).
This is the canonical reference paper for leases. Although similar ideas were explored in other concurrent research as well. This blog post from AWS on how to implement leases is a more recent (and maybe easier to digest) explanation of how leases work.