Two parties who can communicate only by unreliable messages must agree that a transaction (such as an...
logic/two.armies New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Two parties who can communicate only by unreliable messages must agree that a transaction (such as an electronic fund transfer) took place; how can this be done? Somewhere early in the discussion of the 2 Armies problem someone pointed out that Electronic Fund Transfer operations pose a similar problem. The sender and receiver both have to agree that the "message was sent" before the sender's account is debited and the receiver's account is credited. Does anyone know how it is done? -- Shlomo Sanders <sms@alerts.co.il> [ Editor: in the Two Armies (two generals) problem, two armies must attack together but can coordinate only by messengers who may be captured; no finite exchange of messages makes both certain of the agreement. The original statement of the problem in the thread was not in the collected material. ]
Show solution
Well, I don't know how they do it, but I know how I would do it. While the bare protocol cannot guarantee that both parties classify an attempted transaction into "failed" or "succeeded", it can guarantee that either both classify it the same way or one is uncertain. For example, consider the following exchange of messages. The columns on the left show what A and B record as the status of the transaction before each message. A B Message fail fail A -> B prepare to perform transaction X fail fail A <- B ready to perform X fail fail A -> B do it ? ok A <- B done ok ok A -> B confirmed ok ok The only possible problem arises when A sends the "do it" message. If there is no response, A cannot tell whether the transaction was performed. However A does know that the status is uncertain. So how does this relate to a banking transaction. Well, for example, suppose that B is a smartcard and A is the bank sending money to the card. If the status is questionable, the bank can simply mark the account as requiring updating. The next time smartcard B talks to the bank computers it will be asked about the transaction and the uncertainty goes away. Alternatively, if the customer calls the bank he can be told that the card needs to be checked. And if the customer is never heard from again, the status of the transaction is irrelevant anyway. By changing the meaning of the messages, a communications failure can be made to appear at either end. So, for example, a bank may prefer to make smartcards display an error message, forcing the customer to call again and resolve the problem, rather than leave the uncertainty at their end. Of course they can also decide whether a failure temporarily leaves the customer with twice as much money as they should have or with less then they should have. Most people probably agree on which way a bank is likely to decide. -- Charles Bryant <ch@chch.demon.co.uk>