Understanding consensus and Paxos in distributed systems
ifeanyi.co
ifeanyi.co
As well as : "Ice cream & distributed systems" : https://brooker.co.za/blog/2014/10/25/ice-cream.html
The author also published an excellent paper on the subject called "Paxos Made Moderately Complex" (http://www.cs.cornell.edu/courses/cs7412/2011sp/paxos.pdf)
You may want to try 6.824: Distributed Systems https://pdos.csail.mit.edu/6.824/ I learned a lot from working through the online coursework.
Alternatively, download the labs and see the wide variety of unit tests. There are a few devilishly difficult ones.
Algorithms based on synchronous systems are much simpler but theyre also unrealistic both in theory and usually in practice as well (without clever hacks handling edge cases). For example its difficult to set time limit on how long a node on the internet will take to respond. One may reasonably say 10 seconds max, but what happens on the day it takes 10.1 seconds? The system collapses. Asynchronous systems do not consider time at all so they don't suffer from those classes of problems but algorithms based on them are more complex.
If you mean "block waiting for all replicas to respond", then the failure mode is quite different from Paxos. I don't know of one such system that can tolerate two simultaneous failures or network partitions, unlike Paxos.
Second, most systems don't need atomic write operations to succeed across network partitions, when network partition is even a concern (for general operations), which it isn't usually. If your network is partitioned, you can't really "decide" anything until it un-partitions, at which point you don't need to come to consensus if you have simpler methods of solving discrepancy - like using a higher level decision process than block-level or database-level. Even after the discrepancy is solved, network-wide changes may have invalidated the initial partitioned operations. Paxos tries to over-simplify a complex operation.
When it is a concern, application design often trumps system design in terms of reliable operation. It completely depends on your network, system, platform and application design. In general, you won't need Paxos to reap the benefits of distributed systems, and synchronous systems will give you more benefits and less headaches.
There seems to be a flaw in your second point.
When the network partitions in a synchronous network, a node in any partition is not able to tell if a partition has actually occured or if the unreachable nodes are dead. The article points this out as one of the main problems Paxos tries to solve. Your given scenario actually puts the nodes in all in a vulnerable state where they are likely to make wrong decisions and become inconsistent
I don't buy the rest of your post for two reasons. First, partitions are not only problematic for writes. Externally consistent systems also cannot generally serve reads during a partition either. Furthermore, it is not true that partitions are not a realistic worry - i know of at least one large system that encounters partitions on a weekly basis.
Second, you seem to be arguing that for some reason it is easier to solve consensus at the application level. This is simply not true, otherwise we wouldn't have consistent databases.
Consistency is [sometimes] a lie. What are you gonna do, read from the database directly every single time a web server wants to use a user's session cookie? You cache it, you have cache controls, you try to invalidate caches or update them if a new operation changes the session, but there's totally a possible race condition that will be resolved if someone tries a write on an invalid session. There's plenty of valid harmless operations on stale data due to network partition, it's not the end of the world.
Of course some designs are more vulnerable to network partition than others (some designs only work on one network, some require multiple networks) so there are of course cases where you need something like Paxos. I'm saying it's less common than people want to believe.
I find higher level consensus easier because you have more context of what's going on. Session-based operations, for example; if the same operation at the same time is done by two different sessions, you can compare the timing of the operation, when each session was last created/updated, or simply kick back the operation to the sessions and inform them of the conflict and ask them to resolve. In any of these cases the application caught the conflict before it had to do a network communication hokey-pokey, and it can be programmed to make these decisions automatically, too. Letting Paxos decide might result in an immediate fix, but the users might not ever be informed of the consensus decision and one might be confused as to what the actual resulting operation was.
draft thesis from Ethan Buchman: https://github.com/ebuchman/thesis/blob/master/Buchman_Ethan...
"Note that it is possible for several bids to win an auction round. In fact, every active bidder must get a bid chosen in order to decide which candidate won the round. The goal is not agreement on which bidder/bid wins the round (they all do at some point), rather which candidate wins."
from a guy, who, based on his profile is maybe 20 or 21, which is a little depressing.