2025-08-31

Byzantine Fault Tolerance, My Bachelor's Thesis, and My First Conference

When I looked at the list of offered topics by my Department, one topic caught my attention. It was "Fault-tolerant Web Services using Blockchain". It was because I like web development a lot and I was planning to learn blockchains anyways, so I get to do the things I like and learn about blockchains as a side knowledge.

It's probably a simple web development with some blockchains like Ethereum added on top, right?

Wrong. One thing I overlooked was the fault-tolerant part in the topic. Blockchain networks are a subset of distributed systems and fault tolerance is one of the core property within distributed systems. So instead of a simple integration project, I fell headfirst into the distributed systems rabbit hole. What followed was months of being surrounded by Leslie Lamport’s foundational papers, the complex logic of quorum math, and the intricate dance of consensus algorithms.

Faults in Distributed Systems

First of all, let's start on the categorization of distributed systems.

In Software Engineering, faults are the main cause of an error in computation, which in turn causes a software failure. In Distributed Systems, they are categorized in two, Crash Faults and Byzantine Faults, the former being a subset of the latter.

  • Crash Faults are pretty simple. It's basically when nodes crash or stop working, just like the name suggests. Think of it as a person abstaining from a vote in the real world. In the real world case, we can ignore their votes when the majority already wins a vote, because their votes wouldnt matter anyways. Similarly in the theory, we need to have 2f + 1 total nodes to tolerate f failures. If f nodes fails, there's still a majority f + 1 (from 2f + 1 - f) which still outvotes the crashed nodes f (because f + 1 > f duh).

  • Byzantine Faults are (a lot) more complex than Crash Faults. It covers faults from nodes acting maliciously like sending contradictory informations, misinformations, or lies to the other nodes, causing confusion and desynchronization in the network.

The properties of being resilient of those two respective fault categories are Crash Fault Tolerance (CFT) and Byzantine Fault Tolerance (BFT).

Byzantine Fault Tolerance

Byzantine faults are named based on the narrative story chosen to represent a problem on Leslie Lamport's paper in 1982, "The Byzantine Generals Problem". The word "byzantine" was also a functioning English adjective meaning convoluted, scheming, full of intrigue, from the reputation of the Eastern Roman court. The problem presented in the paper focused on nodes being malicious in a network, spreading lies and misinformation to its peers, and causing confusion and desynchronization within a distributed system. Lamport illustrated this problem in a story of Byzantine generals besieging an enemy city, needing to reach the same decision as a whole, either to fully attack or to fully retreat. If the army partially attacks and partially retreats, they will not succeed.

Ensuring every generals to reach the same decision doesn't seem to hard, isn't it? Well, yes, assuming all of them are honest and not trying to sabotage the Byzantine army. However, distributed systems are notoriously difficult because they assume that things that can go wrong will go wrong. And so we assume some of the generals are traitors and intentionally tries to break the synchrony of the army. With that alone, this problem becomes much more complex than before. Now, let's see the situation of these Byzantine Generals.

In the situation, there are different levels of these generals, commanders and lieutenants. Commanders initiate commands, while lieutenants receive them and they can cross-check the comand with other lieutenants. For this situation, let's define the "correct agreement" with these conditions:

  • All loyal generals decide on the same agreement.
  • If the commander is loyal, all honest generals follow the command.

Why these specific conditions? Well, with only the first condition, the problem is easily solvable by putting an absolute rule of before the siege, "Everyone attack no matter what, ignore any messages! We suspect a mole among us trying to break our strategy.". This makes the problem not require any communication and information exchange at all, just follow that rule they agreed upon before the war. To be fair, at a time where communication is not as easy as today, this might work for their problem, a very efficient one at it. Minus their ability to adapt and retreat when they know their enemy overpowers them I guess, as they follow the absolute rule with no exception. As for our audiences of the future, that's a boring problem with zero takeaways. Therefore, we add the second condition as a means to force communication and adaptability within the army, giving us a more insightful problem.

With those conditions set, let's see some cases on the following figures. Picture yourself as Lieutenant 1, what would you do? You're between a rock and a hard place there, buddy. In both cases, there's no way for you to know who's lying. Was it your Boss, the Commander? Or your colleague, Lieutenant 2?

Based on the previously set up conditions, it's impossible for you to fulfill both. You're loyal, so if you assume your commander is loyal, you'd follow his command to fulfill the second condition. But he could be lying, while Lieutenant 2 is loyal. If he is, you can only fulfill the first condition if both you and him follow the same command. With our setup, both situations are impossible. Not because the algorithm is lacking, there's just not enough information for Lieutenant 1 to know who lied.

This has been worked by humanity, by the way. Two people cannot resolve a "he-said-she-said" problem.

Now, let's check the following case with 4 generals, 1 of them a traitor.

In figure 3, the honest Commander sends value v to all commanders. In Lieutenant 2's Perspective, he receives values:

  • v from the Commander
  • v from Lieutenant 1
  • x from the traitor, Lieutenant 3

The majority of what he receives is v, the correct value from the honest commander, and thus he decides on v. Both conditions specified in our problem setup is satisfied. Condition 2 is fulfilled, the Commander is loyal so all honest generals (Lieutenant 1 and Lieutenant 2) must follow his command, which is v. Condition 1 is also fulfilled, because all generals decides on the same value v.

Now, when the traitor is the commander itself, depicted in figure 4. The general sends different messages to all three lieutenants, x, y, and z respectively. For each of the lieutenants, they receive the same set of messages, {x,y,z}. There is no majority in that set, and we can set a fallback command if they see no majority, for example to retreat or do nothing. Any action works by the way, as all generals see the same set in the first place (as long as you don't make the fallback a free pick from the set, of course). This satisfies the First Condition, all honest generals decide on the same action. As for the Second Condition, it is not required as the commander is the traitor.

Now it is shown that for a single traitor, three generals cannot solve the problem, but four generals can. This corresponds to the required total of nodes for Byzantine Fault Tolerance, which is 3f + 1 for f faults. If f = 1, then the total number of nodes required is 3f + 1 = 3(1) + 1 = 4, so 4 is the minimum. I'm not gonna go into the details for an exhaustive or mathematical proof for that in this story though, that's gonna be too long. (Or maybe I will if I have the time to update this 😅)

My Research

What a long theory. So what's the research about?

My thesis research is basically trying to create a network of web services that has the Byzantine Fault-Tolerant property. That was the initial idea of the research.

But after reading other papers and literatures about that idea, we found out that another research has done the exact same research idea so we needed to pivot. It was named DeWS. We saw that DeWS still has problems regarding latency due to the extra consensus process for BFT. As the number of nodes grows, the BFT property becomes stronger, but it also increases the latency of the web services due to more message exchanges. Generally, the increase in latency is acceptable for lower number of nodes. But it gets extreme for 20 nodes and above, reaching nearly 1 second. One second doesn't seem too long, but the average web services could have processed it for only about 16ms. So my focus changed to fixing this latency problem.

My approach used a request batching mechanism and deferred consensus when it is actually needed, and it did pretty well albeit limited in some scenarios. For more details you will need to read my paper, I ain't writing allat 😅.

Thesis Defense

On July 2, 2025, I officially (and successfully) defended my thesis at the Department of Electrical Engineering and Information Engineering, Universitas Gadjah Mada.

I'm tired of explaining BFT to the average person, man. There's just too much background context and knowledge needed to be explained first. Hell, there's a reason why this blog is so long. I even omitted consensus algorithms from that!

What makes me most proud of this work isn't just passing the defense. It's the fact that I chose a path less traveled. Distributed Systems, BFT, and consensus algorithms aren't common topics of conversation, even among IT students and professors. It’s a niche, rigorous field that requires a bridge between theoretical computer science and practical software engineering.

This research eventually became the foundation for my publication at IEEE MetaCom 2025, proving that the rabbit hole of distributed systems was worth the dive.

My First Conference

In August 2025, I had the incredible honor of attending my first-ever international academic conference: the 3rd Annual IEEE International Conference on Metaverse Computing, Networking, and Applications (IEEE MetaCom 2025).

The event was held at Sejong University in Seoul, Republic of Korea, bringing together researchers from across the globe to discuss the future of the Metaverse, AI, and decentralized infrastructure.

Of course, I didn't let the opportunity to explore South Korea go to waste! Between sessions on consensus decoupling and metaverse networking, I managed to experience the vibrant culture and food of Seoul. It was the perfect way to celebrate the culmination of months of intense research.

Resources