The more latency you can tolerate, the easier HA becomes. At an extreme, if you can tolerate 1 minute latency than each request can come in and compute a most likely way to complete a request with the most authoritative set of actors. Few people though are willing to tolerate a commit taking 15 minutes, much less a couple of hours.
This was one of the most insightful things about NFS and the whole stateless design. By burdening the client with the state the server could be much simpler.
Once you get above a certain size the problems change becoming both easier and harder (easier in that you can disperse your data further, harder in that your confidence in agreement between copies takes longer to compute and thus increases latency). It would be interesting if Google shared their work on Spanner (they seemed to have tackled this problem at a large scale) and given Netflix's experience (Chaos Monkey's dad) it seems like Amazon still hasn't quite gotten the recipe right.
It is a deliciously thorny problem with subtle complexity and unexpected inter-dependencies.
It seems redundancy protocols end up grappling each other more often than not
Unfortunately, there is no easy answer, and I'm sure Github employs people with lots of experience.
This makes me wonder about after several people working on problems like this it's still a challenge