7 ms·
The Byzantine Generals Problem (1982) [pdf]
- arberavdullahu 7y agoTaken from [0]: There is a problem in distributed computing that is sometimes called the Chinese Generals Problem, in which two generals have to come to a common agreement on whether to attack or retreat, but can communicate only by sending messengers who might never arrive. I stole the idea of the generals and posed the problem in terms of a group of generals, some of whom may be traitors, who have to reach a common decision. I wanted to assign the generals a nationality that would not offend any readers. At the time, Albania was a completely closed society, and I felt it unlikely that there would be any Albanians around to object, so the original title of this paper was The Albanian Generals Problem. Jack Goldberg was smart enough to realize that there were Albanians in the world outside Albania, and Albania might not always be a black hole, so he suggested that I find another name. The obviously more appropriate Byzantine generals then occurred to me. [0] https://www.microsoft.com/en-us/research/publication/byzantine-generals-problem/ https://www.microsoft.com/en-us/research/publication/byzanti...
- mikorym 7y agoThe original is a well known problem in logic which my lecturer touched on. If you have each general on a mountain and a valley between the two, then you have no way to know whether the other received the message. If you send back a confirmation, then you have no confirmation confirmation... etc. In my (at the time occasional) drunken state I may have thought every now and a again, after 13 confirmations of confirmations surely you can just attack! But alas, it all falls flat: You have no way of knowing the final confirmation, the one before that, etc. until you are back where you started. By the way, this only applies to lossy communication without feedback. A Whatsapp text syncronises via a server. As long as the server is up and confirms both sides, you can be quite sure the other side received the message. This is manifested these days in the form of the infamous blue ticks.
- hprotagonist 7y agowell, now you trust the server. Who might betray you :)
- peheje 7y agoHow does a server fix the problem? The server still doesn't know whether the sender knows that the server received and acknowledged your message, so you might want an ack from server, but again, the server doesn't know if you received the ack, so you ack the ack, but again ...
- zaarn 7y agoBasically, the server assumes that if the client has ACK'd the message, it can continue sending data. The client assumes that the server has received their ACK if it continues sending data. If no data is being sent, the connection is closed via timeout eventually.
- celticninja 7y agoYou are just back to the same problem, you need to trust a server. The server is the valley between the generals, you can't be sure what happens there. Do they get the message, or do they het an altered message, both of which will send blue ticks to indicate it has been read.
- zzbzq 7y agoThe server is also a general on a mountain
- peheje 7y agoI am talking about the Two General's problem which I thought original commentator was referring to as the original problem. In this situation you are describing a server that wants to send a client a message, and both parties need to be sure that they are in agreement when to attack a common enemy they can't deal with alone because the message contains the attack plans and timestamp for attacks. Wikipedia has a good explanation: "The first general may start by sending a message "Attack at 0900 on August 4." However, once dispatched, the first general has no idea whether or not the messenger got through. This uncertainty may lead the first general to hesitate to attack due to the risk of being the sole attacker. To be sure, the second general may send a confirmation back to the first: "I received your message and will attack at 0900 on August 4." However, the messenger carrying the confirmation could face capture and the second general may hesitate, knowing that the first might hold back without the confirmation. Further confirmations may seem like a solution—let the first general send a second confirmation: "I received your confirmation of the planned attack at 0900 on August 4." However, this new messenger from the first general is liable to be captured, too. Thus it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general be sure the other has agreed to the attack plan. Both generals will always be left wondering whether their last messenger got through. " There is no solution, only a decreasingly smaller change of disagreement e.g. by sending many messages or keep acking each other x amount of rounds (there are other strategies). No timeouts, only death.
- SilasX 7y agoScott Adams created Elbobia as a fictional country, with both Eastern European and middle eastern traits, so he could make fun of a backward country without offending anyone. Interestingly, it feels like a cross of Estonia and Albania.
- gitgud 7y agoI'm reluctant to broach the subject, but is a "Blockchain" based system a solution to the "The Byzantine Generals Problem"? > A. All loyal generals decide upon the same plan of action. All actors arrive at an immutable consensus (the current transaction group in the blockchain). > B. A small number of traitors cannot cause the loyal generals to adopt a bad plan It has protection against a small number of bad-actors as they require proof of work/stake which prevents against bad-transactions up until 51% attacks. I don't have much knowledge in the area though, any thoughts?
- riffraff 7y agoI am quite sure Satoshi Nakamoto suggested it as a probabilistic solution, yes, but not a full one[0] [0] https://ethereum.stackexchange.com/questions/40213/how-is-the-two-generals-problem-solved-with-proof-of-work https://ethereum.stackexchange.com/questions/40213/how-is-th...
- zzzcpan 7y agoThe problem doesn't have a "full solution", like any fault tolerance in general, only probabilistic one.
- exdsq 7y agoYes. There are several BFT compliant conensus algorithms for both Proof of Work and Proof of Stake. Some of them, such as Bitcoin, are BFT compliant because it's economically infeasible to complete an attack. Ouroboros is BFT compliant up to n/2-1 bad actors https://eprint.iacr.org/2018/1049.pdf https://eprint.iacr.org/2018/1049.pdf Edit: This goes back a comment I made the other day about 'Blockchain == Down votes' on HN. Why would you down-vote OPs question?
- dooglius 7y agoYes, you can read it from the horse's mouth: https://www.metzdowd.com/pipermail/cryptography/2008-November/014849.html https://www.metzdowd.com/pipermail/cryptography/2008-Novembe...
- celticninja 7y ago
- vinniejames 7y agoBitcoin fixes this
- ilammy 7y agoBy the way, one of the paper authors – Leslie Lamport – is the Leslie Lamport, creator of LaTeX. He is probably one of the reasons behind beautiful typesetting of this and other papers.
- inviromentalist 7y agoMy most frustrating thing about the crypto movement was how uneducated people were. People had no idea that POW isn't scalable, yet would insist that a Bitcoin copy-paste would solve the problem. Or that a centralized coin was the future. Or that proof of stake was a working solution. I still hear people wrong today. I only imagine that if people understood, there would be less altcoin mania.
- lukifer 7y agoI view the PoW problem as being a subset of a broader problem with otherwise-efficient markets: there are often game-theoretic incentives to be intentionally inefficient. An example from nature is a peacock's tail, wasting resources to signal genetic fitness [0]; an example from consumer products is the Veblen Good [1] (aka conspicuous consumption), where wealth is wasted to signal status. At minimum, I think we need a carbon tax (ideally paired with a revenue-neutral dividend), which might alter the incentives for crypto mining. But I don't think it would be unreasonable for industrialized nations to ban useless PoW operations outright. While I've read cogent explanations of PoS having game-theoretic shortcomings relative to PoW, given the growth of bespoke ASICs and the capital requirements of modern mining operations, PoW seems to me to be indistinguishable from PoS with extra steps, while also being an ecological nightmare. [0] https://en.wikipedia.org/wiki/Signalling_theory#Sexual_selection https://en.wikipedia.org/wiki/Signalling_theory#Sexual_selec... [1] https://en.wikipedia.org/wiki/Veblen_good https://en.wikipedia.org/wiki/Veblen_good
- dang 7y agoA thread from 2018: https://news.ycombinator.com/item?id=17702640 https://news.ycombinator.com/item?id=17702640 2014: https://news.ycombinator.com/item?id=8697029 https://news.ycombinator.com/item?id=8697029 Others? (These links are just for curious readers; reposts are ok after a year or so—see https://news.ycombinator.com/newsfaq.html https://news.ycombinator.com/newsfaq.html)
- mlazos 7y agoThis brings back memories, I worked on a system that had to be fault-tolerant during an internship and this paper gave me a lot of insight into why some design choices (ie the number of processors) were made.
- professionalguy 7y agoCan someone ELI5?