The Byzantine Generals Problem (1982) [pdf] | Hacker News Reader

The Byzantine Generals Problem (1982) [pdf]

lamport.azurewebsites.net

127 pointsxkgt21 comments

An ancient Byzantine general was once involved in a plot to overthrow the king. His plot included a number of followers in the upper ranks of the army. However, his plot was uncovered, and the king threw him in jail. The king sentenced him to death without a trial.

However, from the jail he was able to secretly contact his followers to arrange to escape, meet his followers, and attack the king's palace at night. So the night before his scheduled execution, the general managed to escape from prison. He fled to a ziggurat several kilometers away, where his followers would meet him. However, the ziggurat was one of several in the area, and he wasn't sure if his cohorts would find the right ziggurat. By this time it was twilight, so he lit a small fire and sent smoke signals to indicate in which structure he was hiding.

However, the king's loyal soldiers saw the smoke coming from the ziggurat, and came to arrest him before he could meet his followers. He was executed later that day.

The moral of the story? WARNING: The searching general has determined that smoking ziggurats can be extremely hazardous to your stealth.

I did not see that coming. Also, your username checks out. Also, I realize that I am not on reddit. =))

/r/unexpectedreddit

James Mickens wrote an interesting and very funny essay on this problem: https://scholar.harvard.edu/files/mickens/files/thesaddestmo...

It doesn't matter what the topic is, anything James Mickens has to say on it will be entertaining.

They are as scrutable as Solomonic proverbs, and just as bloodthirsty, but at the end of the day I feel like I read something that maybe made me a better programmer.

I have a professor who is interested in the Byzantine Generals Problem and worked with Lamport at Microsoft Research. She claimed that Leslie told her that no one was interested in the problem/it didn't matter. Here[1] is a clever algorithm for leader election that she presented to us.

[1]https://youtu.be/UVzCZqNngaU?t=1364

Why does the following strategy not counter this approach?

If you are the bad guy you sort all candidates according to their current trust, as defined by being part of the trusted group in previous voting rounds. And then you put your marker into the most trusted bucket that isn't yours. Thereby nobody should get ahead.

The PBFT algorithm, or any Byzantine fault tolerant algorithms are deliberate on what's the message-passing scheme and election protocol would look like.

However, in recent ICO craze, a lot of algorithms (with the exception of Bitcoin, and maybe others I didn't read) don't go very long way other than "we will broadcast to everyone". These under-specified message passing scheme can be troublesome, especially for these algorithms without Proof-of-work.

Which protocols have you read?

Will try not to reply here since it can be inflammatory (any cryptocurrency topic here HN). That's been said, can you find any mention of "messages" in this article: https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm... which directly referenced as their DPoS algorithm here: https://github.com/EOSIO/Documentation/blob/master/Technical... (I am not saying these are wrong, just under-specified scheme will essentially become implementation-specified and doesn't help anyone here).

Check out Hashgraph. It is asynchronous Byzantine.

Hashgraphs currently require a permissioned environment (eg. a node needs to know how many others there are and trust them to reach consensus) - so why not just use SQL Databases? They are even faster.

SQL database, operated by different vendors, would allow double spending.

Pretty much all of BFT consensus protocols (like Paxos or Honey Badger) are like this, except SCP (Stellar). They are used e.g. in aviation, so they are very practical.

I think that 95% of the ICO craze people meet at least one of these:

1.Don't have an algorithm concept in the paper 2.Don't know what an algorithm is 3.Have a concept, don't know what it means' 4.Don't know what the Byzantine Generals Problem is 5.Don't know what blockchain is

Worth mentioning, Bitcoin and Satoshi style Proof-of-Work doesn't actually solve the Byzantine General's Problem, it merely creates a lottery system that allows anyone with a large amount of excess capital to take control of adding entries to the database.

Discussed in 2014: https://news.ycombinator.com/item?id=8697029

I agree with what James Mickens has to say about this area of expertise. Usually the thinking is to expect that things mostly work (which is wrong) and that in case of an inconsistency sending another message could fix it (which more often than not is also wrong). In an unreliable environment a new message might not arrive and even if it does it might not contain any meaningful information for the receiver as he can't trust it, or can't put it into the context he already possesses. So in real life even in failure states it might sometimes be better to not send a message.

Therefore I wonder if there is another area of science, one that is not as optimistic, and for instance follows these system expectations:

- if you send a message, you cannot expect anybody to follow its content

- you cannot trust any messenger to begin with (but might gain trust over time)

- just because a messenger was there some time ago, doesn't mean the messenger is still there

- just because a message is signed by a messenger it doesn't necessarily already mean the message is from the messenger

- the messages contents might be a false interpretation of the system's state, or might not represent the current state of affairs, things might change between send and receive of a message

- errors are the architectural default case, success is a lucky coincidence (that of course must be exploited maximally)

- side note: leadership election might already need an amount of successful cooperation that is never achieved (i.e. multiple messages need to be exchanged and trusted successfully)

In some regards I feel TCP/IP is already thinking in the right direction. That's how the internet became so successful in the beginning. But it has the big fault (which also was a key factor in its growth) that it simply trusts stuff via default. Mistrust is an add-on.

So if anybody knows about people researching distributed system from that pessimistic but serenely-accepting perspective I would be really interested.

Its funny how these tenets map out to relationships to humans. Replace messenger with "friend" and it still retains a measure of truth.

This is not a coincidence. I'm a worker node in a distributed international corp, and we have a lot of communication errors and timeouts, protocol errors and interpreter bugs, as well as byzantine generals called managers. Our kafka is called email and instead of kubernetes we sometimes use cubicles.

In networking, Radia Perlman had some decent research done on this: http://www.vendian.org/mncharity/dir3/perlman_thesis/

In my opinion,that is what routing protocols should look like. Or at least they should adopt byzantine fault tolerance and modern crypto to authenticate route updates.

Reply on news.ycombinator.com