God's Imitator-Chapter 312: Byzantine Fault Tolerance Algorithm
Cai Zhiyuan continued explaining, "For example, suppose there are now five generals total. Two generals think they should attack, while another two generals think they should retreat.
"At this time, the fifth general is a traitor. He tells the attacking generals, 'I will also attack', and tells the retreating generals, 'I will also retreat'.
"Thus, the generals who want to attack think that now three armies agree to attack, exceeding half, so they should attack tomorrow.
"While the generals who want to retreat think they should retreat tomorrow.
"The final result is that two generals attack and two generals retreat, leading to the war's failure.
"This is the problem brought about by 'decentralization'. Because these five generals are all at the same level with no commander possessing absolute authority, this kind of problem arises during the process of mutually discussing strategy."
Zheng Jie nodded in realization, "I see! So how do we solve this? There's no way to verify which general specifically is lying, right?"
Cai Zhiyuan explained, "Actually solving this problem is very simple: just ask a few more times.
"Suppose I'm one of the generals, General A, and General B tells me he wants to attack together with me.
"If I believe him, then I might be deceived, because General B might be a traitor. He might have only told me to attack while telling others to retreat.
"So at this time, I should go ask General C. I ask him, 'Did General B tell you to attack or retreat?'
"Then I go ask all the other generals one by one, summarizing all the information General B told them.
"The information other generals tell me about 'what General B told them' may not necessarily be true either, because there might also be traitors among the other generals. There might be situations like 'General B told them to attack, but they tell me General B said to retreat'.
"So I ask each one, 'What did General B tell you?' If 'attack' is more common, then I'll record General B's opinion as 'attack'.
"Then I ask each one again, 'What did General C tell you?' If 'retreat' is more common, then I'll record General C's opinion as 'retreat'.
"Just like this, through this repeated nesting method, I continuously eliminate minority answers. The conclusion I finally reach is the more accurate 'majority answer'.
"Under conditions satisfying 'Byzantine Fault Tolerance', we forcibly require all generals to follow this set of strategies and must resolutely execute the final conclusion.
"Then we can ensure everyone attacks together or retreats together."
Zheng Jie was somewhat confused, "Under conditions satisfying 'Byzantine Fault Tolerance'? Meaning what Brother Cai said before, the number of traitors must be less than one-third?"
Cai Zhiyuan nodded, "Yes.
"Let's use the case of 3 generals as an example:
"Suppose among 3 generals, General C is a traitor who deliberately transmits wrong information.
"General A will first tell Generals B and C 'attack'.
"But after General B receives the order, he cannot confirm whether General A is a traitor, so he has to first ask General C, 'What order did General A give you?' General C is a traitor, so he will deliberately say, 'General A's order to me was retreat'.
"Because there are only three generals, General B cannot determine which of General A and General C is the traitor, because the 'attack' and 'retreat' orders each have one vote and cannot form a majority.
"Similarly, when General B executes this strategy, he also can't determine which of General A and General C is the traitor.
"This is the simplest situation. If the number of generals increases, for example if there are 7 generals simultaneously with 2 traitors, the situation becomes much more complex. You have to nest many times to finally reach a conclusion.
"That's why I said this kind of problem doesn't need you to actually calculate it yourself. Just remember the conclusion.
"The conclusion is, when the number of traitors reaches one-third or more, this problem becomes unsolvable.
"Conversely, to make this problem solvable, you need to control the number of traitors to less than one-third.
"Apply this to the number of people in the three rooms and it becomes clear at a glance.
"'4-person room', 3 people answering. So as long as there's 1 malicious free agent, this problem becomes unsolvable.
"'8-person room', 7 people answering. With 3 malicious free agents in the room, it's unsolvable.
"'13-person room', 12 people answering. With 4 malicious free agents in the room, it's unsolvable."
Zheng Jie suddenly understood, "I see!
"So Brother Cai, you applied this formula and immediately knew the '8-person room' was actually the safest, because we only needed to send in 1 friendly free agent to occupy a position, and this problem would definitely be solvable."
Qin Yao still didn't understand, "Wait, although I still don't quite get it, I've memorized this formula.
"My question now is, how exactly does this Byzantine problem apply to the game rules?"
Zheng Jie volunteered, "Let me explain!
"After entering rooms in the second stage, it's actually a game between 'answerers' and 'questioners'.
"For example, if we set up a rigged operation in the '8-person room', then we play the role of 'answerers', while players from other communities who enter the room later play the role of 'questioners'.
"Our 'answerers' side's goal is to achieve a unanimous option so we can get the extra reward and earn visa time from the 'questioner'.
"Conversely, the 'questioner' side's goal is to prevent us from achieving a unanimous option.
"A relatively simple method is for ordinary players on the 'questioner' side to deliberately choose different options from us.
"That's why we need to set room rules to force these players to submit majority options.
"The 'submit suggestion' function actually simulates the calculation process of the 'Byzantine Fault Tolerance Algorithm'. Each player must forcibly send the current majority suggestion, but with certain time intervals.
"So after sending repeatedly, except for free agents, all ordinary answerers' suggestions become the same option.
"After that, the game rules will force these players to submit this option, achieving the goal of 'unanimous agreement'.
"But as Brother Cai said, the simulation process of 'submitting suggestions' itself needs 'majority suggestions to reach a certain quantity' before it can be established.
"'Free agent' players actually play the role of 'malicious nodes' and 'traitors'. They continuously send minority suggestions to disrupt the calculation.
"If there are relatively many of these malicious 'free agents', this situation might occur:
"Right now option A suggestions are more numerous, but suddenly many option B suggestions appear and overtake, causing some players to change to option B suggestions, then suddenly some option A suggestions appear again...
"This causes the suggestions players submit to keep changing, never able to stabilize. So when the 'submit suggestion' function deadline arrives, some players submitted A while some submitted B, and everyone can't reach agreement.
"If the 'answerer' side cannot stably force the 'questioner' to stay in power and cannot stably obtain earnings, then that's equivalent to the rigged operation being dismantled."
Cai Zhiyuan nodded, "Yes, so as long as we determine the conditions for 'Byzantine Fault Tolerance' to be established through the formula, then compare the number of free agents that can enter each room, we can determine the strategy for entering rooms.
"'8-person room' allows 3 'free agents' to enter. This problem becomes unsolvable when 3 traitors appear. So we only need to ensure there's 1 friendly 'free agent' in the room occupying a position, and it's safe.
"Of course, this friendly 'free agent' must be benevolent, meaning they will actively execute the 'send majority suggestion' strategy.
"'13-person room' allows 6 free agents to enter. This problem becomes unsolvable when 4 traitors appear, so Wang Weidong must ensure the malicious free agents who finally enter the '13-person room' are fewer than 4.
"So they need more 'benevolent free agents' to occupy positions.
"If they don't realize this, we can also choose to actively attack. But since Wang Weidong realized it and set up defenses, forcing an attack wouldn't mean much.
"So I changed my approach, which was to use this game's 'against-conscience penalty' to pose questions targeting Wang Weidong's characteristics that might cause him to be completely disgraced within the community, thereby forcing him to cancel the room rules."
Chapter 312: Byzantine Fault Tolerance Algorithm
Comments