God's imitator

Chapter 313 Byzantine Fault-Tolerant Algorithm

Cai Zhiyuan continued to explain:

"For example, there are five generals in total. Two of them think we should attack, while the other two think we should retreat."

"At this point, the fifth general was a traitor. He told the attacking general, 'I will also attack,' and the retreating general, 'I will also retreat.'"

"Therefore, the general who wanted to attack believed that now three armies agreed to attack, which was more than half, so the attack should be launched tomorrow."

"The general who wanted to retreat believed that they should retreat tomorrow."

"The final result was that two generals attacked and two generals retreated, leading to the defeat of the war."

"This is the problem brought about by 'decentralization'. Because these five generals are all of equal rank, none of them are commanders with absolute authority. So, this kind of problem arises when they discuss strategies with each other."

Zheng Jie nodded in sudden realization: "I see! So how do we solve this problem? There's no way to verify which general is lying, is there?"

Cai Zhiyuan explained, "Actually, the solution to this problem is very simple: just ask it a few more times."

"Suppose I am one of the generals, A, and General B tells me that he will attack with me."

“If I believe him, I might be deceived, because General B might be a traitor. He might have only told me to attack, but told others to retreat.”

"So, at this point I should ask General C again, 'Did General B tell you to attack or retreat?'"

"Then I went and asked all the other generals one by one, and compiled all the information that General B had given them."

"The information that other generals told me about 'General B gave them' may not be true either, because there may be traitors among the other generals. There may be situations where 'General B told them to attack, but they told me that General B told them to retreat.'"

"So, I asked each of them, 'What did General B say to you?' If there were more 'attacks,' then I would record General B's opinion as 'attacks.'"
"Then I would ask each of you, 'What did General C say to you?' If 'retreat' was the most common answer, I would record General C's opinion as 'retreat'."

"In this way, by repeatedly eliminating minority answers through nested dolls, I finally arrived at the more accurate 'majority answer'."

"Under the premise of satisfying the 'Byzantine fault tolerance,' we mandate that all generals adhere to this strategy and resolutely implement the final conclusions."

"Then we can ensure that everyone attacks or retreats together."

Zheng Jie was somewhat confused: "Under the condition of satisfying the 'Byzantine fault tolerance'? That is, what you said before, Brother Cai, the number of traitors must be less than one-third?"

Cai Zhiyuan nodded: "Yes."

"Let's take the case of three generals as an example:"
"Suppose that among the three generals, General C is a traitor who deliberately transmits false information."

General A will first tell Generals B and C to "attack".

"However, after receiving the order, General B could not confirm whether General A was a traitor, so he had to ask General C first, 'What were the orders General A gave you?' And since General C was a traitor, he would deliberately say, 'General A gave me the order to retreat.'"

"Because there are only three generals, General B cannot determine whether General A or General C is the traitor, because the orders to 'attack' and 'retreat' each have one vote, so a majority cannot be formed."

Similarly, when General B is implementing this strategy, he cannot determine whether General A or General C is the traitor.

"This is the simplest case. If the number of generals increases, for example, if there are 7 generals at the same time, and 2 of them are traitors, the situation will become much more complicated. It will take many nested steps to finally reach a conclusion."

"That's why I said that you don't need to actually calculate these kinds of problems yourself, just remember the conclusion."

"The conclusion is that when the number of traitors reaches one-third or more, the problem becomes unsolvable."

"Conversely, to make this problem solvable, the number of traitors must be kept to less than one-third."

"By comparing the number of people in the three rooms, it becomes clear. "In a '4-person room,' 3 people are answering the questions, so if there is even one malicious free agent, the problem is unsolvable."

"In an '8-person room,' with 7 people answering questions, and 3 malicious free agents in the room, the answer is unsolvable."

"The '13-person room' requires 12 people to answer questions. It cannot be solved if there are 4 malicious free agents in the room."

Zheng Jie suddenly realized: "So that's how it is!"
"So, Brother Cai, you applied this formula and immediately realized that the '8-person room' is actually the safest, because we only need one of our own free agents to enter and occupy a position, and the problem can definitely be solved."

Qin Yao still didn't understand: "Wait a minute, although I still don't quite understand, I've memorized this formula."

"My question now is, how exactly does this Byzantine problem fit into the rules of the game?"

Zheng Jie volunteered, "Let me explain!"

"After entering the room in the second stage, it is actually a game between the 'answerer' and the 'question setter'."

"For example, if we open a black market in an '8-person room,' we play the role of the 'answerer,' while players from other communities who join the room later play the role of the 'question setter.'"

"Our goal as 'respondents' is to reach a consensus so we can get extra rewards and earn visa time from the 'question setter'."

"On the other hand, the goal of the 'question setter' is to prevent us from reaching a consensus on the options."

"A relatively simple method is for the ordinary players on the 'question setter' side to deliberately choose different options from us."

"That's why we need to set room rules to force these players to submit the majority option."

"The 'Submit Suggestion' function is actually simulating the operation process of the 'Byzantine Fault Tolerance Algorithm'. Each player must force the submission of the current majority suggestion, but there will be a certain time interval."

"So after sending it over and over again, all the suggestions from ordinary respondents, except for freelancers, will become the same option."

"After that, the game rules will force these players to submit this option, thus achieving the goal of 'unanimity'."

"But as Brother Cai said, the simulation process of 'submitting suggestions' can only be valid after 'a majority of suggestions reach a certain number'."

"The 'free agent' players actually act as 'malicious nodes' and 'traitors,' constantly sending minority suggestions to disrupt the computation."

"If there are many of these malicious 'free agents,' the following situation may occur:"
"At this point, option A was the most popular suggestion, but suddenly many option B suggestions appeared and took over, causing some players to switch to option B. Then suddenly some option A suggestions appeared again..."

"This will cause the suggestions submitted by players to keep changing and never become fixed. So when the 'submit suggestion' function closes, some players will have submitted A, and some players will have submitted B, and everyone will not be able to reach a consensus."

"If the 'respondent' cannot reliably force the 'question setter' to win consecutively and cannot reliably obtain profits, then it's equivalent to the black market being dismantled."

Cai Zhiyuan nodded: "Yes, so as long as we determine the conditions for the 'Byzantine fault tolerance' to be valid through the formula, and then compare the number of free people who can enter each room, we can determine the strategy for entering the room."

"The '8-person room' allows 3 'free agents' to enter. This problem becomes unsolvable when there are 3 traitors. Therefore, we only need to ensure that one of our own 'free agents' occupies a spot in the room to be safe."

"Of course, this 'free agent' on our side must be benevolent, meaning he will proactively implement the strategy of 'sending majority suggestions'."

"The '13-person room' allows 6 free agents to enter. This problem becomes unsolvable when there are 4 traitors. Therefore, Wang Weidong must ensure that the number of malicious free agents entering the '13-person room' in the end is less than 4."

"Therefore, they need more 'benevolent free agents' to reserve positions."

“If they don’t realize this, we can choose to take the initiative to attack. But since Wang Weidong has realized it and has taken a defensive stance, there’s not much point in forcing an attack.”

"So I changed my approach, which is to use the game's 'punishment for going against one's conscience' to ask Wang Weidong some questions that might ruin his reputation in the community, thereby forcing him to cancel the room rules."

　Asking for a monthly ticket~
　　
　
(End of this chapter)