Hacker News Reader

Comment by lordnacho | Hacker News Reader

Having looked for a few minutes, it really reminds me of the routing protocols used for distributing routes in networks. (Also Layer 2 stuff IIRC). There you also find heartbeats, elections, etc.

Is there a connection?

Also, does it have anything to do with the Byzantine Generals Problem?

View on HN

Heartbeats (is this system up?) and leader election (which server should I talk to?) are common components of any distributed system. Byzantine generals is a much different problem. Whereas Paxos gets the majority of nodes (a quorum) to agree on a certain value, Byzantine Generals deals with unanimous agreement in a system with network link failures. Furthermore, in Byzantine Generals, some of the generals can be traitors actively working against the others. Unanimous agreement isn't all that useful or interesting, but production distributed systems should handle Byzantine failures. This covers innocent events such as corrupted data/messages and software bugs all the way up to hackers trying to take over your system through a compromised node. Variants of paxos exist which handle or mitigate Byzantine failures.

> production distributed systems should handle Byzantine failures

I don't think this is true, at least not as stated. You should certainly be thinking about more than crash-stop failures, but full-blown Byzantine fault tolerance is rarely warranted in practice. Empirically, the number of systems that use non-Byzantine vs. Byzantine agreement is probably on the order of 100:1.

Good point. Depends on your threat model. Most systems can get away without full-blown Byzantine fault tolerance. You're probably right about the 100:1 ratio for production systems.

Well for one, both Paxos and "Byzantine Generals" were authored by Leslie Lamport (latest Turing award winner IIRC).

But Paxos has gentler assumptions about adversaries than in the Byzantine Generals problem.

Reply on news.ycombinator.com