Читать книгу Distributed Computing Pearls - Gadi Taubenfeld - Страница 13

CHAPTER 3

A Tale of Two Lovers

In many distributed systems, sometimes there is a need to ensure that two things happen together or not at all. The two lovers problem, which again involves two-person interactions, demonstrates the difficulty of reaching such an agreement when communication is restricted to sending and receiving messages which can get lost.

3.1 THE TWO LOVERS PROBLEM

The problem is for two lovers to decide on the exact time for a meeting. The problem is described as follows.

Two lovers have to coordinate a time for meeting at a romantic restaurant for dinner. If they simultaneously arrive at the restaurant, they are assured to end up marrying and live happily ever after. If only one arrives, their relationship will come to an end. As a result, neither lover will arrive without a guarantee that the other will arrive at the same time. In particular, neither lover will arrive without communicating first with the other.

The lovers can communicate only by sending messages. However, every time a message is sent it stands some chance of getting lost.

The problem is to find an algorithm that allows the lovers to coordinate a time for a meeting even though some messages may get lost.

To prevent a situation where both lovers, fearing that their relationship will come to an end, simply refrain from arriving, it is required that if everything goes smoothly and no message is lost, the lovers must be able to coordinate a time for a meeting. If enough messages are lost, however, the lovers may refrain from arriving, but both must do so.

3.2 APPLICATIONS

To see the corresponding synchronization problem for computing systems, consider two computers (the two lovers) that are trying to perform a database transaction over an unreliable communication line, and need to decide whether to commit or abort the transaction.

A specific example would be the problem of transferring $100 between two bank accounts which reside in different banks. Two clerks (the lovers), who are responsible for the accounts, need to update that balance in the two accounts simultaneously. They should do it, even though their computers are connected by an unreliable communication channel.