What is the expected behaviour for collisions? If k2 wants to engage k1 to update (k1_machine, k1_idx) while k0 is also engaged with k1 in updating (k1_machine, k1_idx) the system responds by ... what? Rejecting both transactions? Allowing a dirty commit? Allowing one commit and rejecting the other?
I rewrote the question based on your feedback. Is this clearer ?
This notion of "which machine is doing which update" -- I think we get best throughput with "optimistic concurrency", which in my limited understanding is: everyone tries to write, and if we get collision: rollback / resolve.
It's not clear to me what are your requirements and things you can rely on, but looks like Byzantine fault - Wikipedia . Fundamentally there is no way to to have atomic updates between multiple networked nodes in the presence of possibility of connectivity failures, etc. without some pre-arranged scheme.
Generally you need to do some quorum/leader election like Raft (if machines are known beforehand), or probabilistic PoW-blockchain-like elections.
In the physical world, transactions are not atomic. Alice gets to eat her meal before paying. The office store cashier could grab the product off the checkout counter after Bob has paid.
The consistency in these cases comes not from atomicity but observation over time: each party literally walking away from a transaction takes some time to do that and has the ability to go back and discuss revising it, and as seconds pass and they don't do that, both parties become increasingly confident that they are both satisfied with the transaction. And if there is actually not satisfaction but one party leaves (/refuses to interact further) then it becomes a separate refund, a matter for the courts, or a write-off.
There’s been a lot of thinking about this kind of failure mode in finance/business circles, especially regarding larger contracts. If you want to dive into the literature, the search term is counterparty risk.
In this case, for a large transaction, Cindy and Dan would usually use a trusted escrow agent to perform the exchange:
Cindy sends BTC to escrow
Dan sends ETH to Cindy
Escrow sends BTC to Dan
If (2) doesn’t happen, escrow returns Cindy her BTC and nobody is left hanging.
There’s always the possibility that the escrow agent will run off with the BTC, which is why you need a reputable escrow agent: You want the loss of that reputation (in future fees) to greatly exceed the gain from stealing this one transaction.
What about the internet? We have billions of people, interacting with millions of websites; and there is no notion of physical proximity / walking away. And people can run transactions, despite there not being a centralized leader that approves every transaction.
You wrote “If we look at the physical world…”. I claim that, in those cases, atomicity is not the means by which we accomplish transactions — so they are not relevant examples to the problem of atomicity in distributed database transactions.