Bankers Dilemma

Bankers Dilemma.md

If we imagine the below diagram is an example of a bankers dilemma (two users Foo and Bar have access to a single bank account: Baz). What is the expected behaviour when following one of the paths shown?

Note: I'm assuming we're using a mutex (or some other form of synchronisation) on the Baz variable.

Example 1: Baz initially holds the value 10. If Foo writes a new value (which is the result of removing 5 from the current value) before Bar; then Bar will end up taking 10 from the new value 5, leaving a minus balance (i.e. the final value will be -5). Meaning more money has been taken than available.

Example 2: Baz initially holds the value 10. If Bar writes a new value (which is the result of removing 10 from the current value) before Foo; then Foo will end up taking 5 from the new value 0, leaving a minus balance (i.e. the final value will be -5). Meaning more money has been taken than available.

Both actions (Foo (-5) and Bar (-10)) are triggered at the same time. So how do we ensure that either Foo or Bar is alerted to the fact that their transaction cannot be completed (as there are not enough funds for it to succeed)?

It seems a potential solution is to ensure the caller executes a method that uses a mutex internally to lock the value first; then once the value is locked we can read the value; and then check if the action is valid. If the condition passes then we update the value and release the lock on the value. Meaning the next caller will be able to lock the value down and run through the same steps.

But how would this approach work with a distributed system? You could suggest using a global data store, but it would have to be one that guarantees consistency (e.g. a service such as AWS' Dynamo DB offers "eventual consistency" and so wouldn't work for a banking institution); but guaranteed consistency is generally considered to be very slow (depending on the number of distributed nodes I assume).

So how do we attempt to solve this design problem?

Based on discussions here: http://programmers.stackexchange.com/questions/259806/how-do-you-solve-issue-of-consistency-in-concurrent-and-distributed-application it would seems there are a few possible solutions depending on the scope of functionality required and also if we're concerned with CAP Theorem:

• Action the request, but verify first if the resulting value would be a negative numerical value and return an error instead, otherwise store/modify the resulting value.
• If we don't care about "partition tolerance" then we can utilise "locking" (e.g. a mutex or some other form of synchronisation) to acquire the value, lock and modify, and then release the value.

One of the commenters mentioned about transferring money across multiple accounts but has yet to mention about the distributed nature of the data store itself. I've since replied:

What type of data store would we be considering here? Is this a single/global data point that we are accessing to retrieve the balance from each account? If the data store wasn't distributed then what happens if our global point of access fails? i.e. all users would be affected as apposed to when the data is distributed.

Seems legit.

I would have expected the behaviour of do the action (with a couple of preconditions) even if it can't verify it.