The Byzantine Generals Problem and What Happened at Github

You just fixed a bug where two honest users conflicted(my last article named Escaping the Loop - A Systematic Approach to Debugging State and Dependency Cycles). Do check it out if not have already. Now let me show you what happens when the system itself stops being honest - when a node doesn’t crash, but lies. The math changes. The fixes get uglier. And sometimes, you can’t fix it at all. You can only contain the damage.

It’s AI Generated

The Example: A Flight Booking System Where Customers Get Double-Charged

A travel booking site.

The bug: Sometimes, customers get charged twice for the same flight. Not often. Maybe 1 in 10,000 bookings. But when it happens, it’s a massive charge. Customers notice. They call support. Support refunds. Company eats the loss.

The setup: You have 3 microservices:

• Booking Service: Creates the reservation
• Payment Service: Charges the card
• Notification Service: Sends confirmation email

Each service has its own database. They communicate via Kafka (event queue).

The bug appears after 6 months of perfect operation. Your team has tried everything: added retries, idempotency keys, distributed transactions. Nothing fixes it completely. It just happens less often.

What Your Code Might Looks Like

// BookingService.java
public class BookingService {
    @EventListener
    public void handleBookingRequest(BookingRequest request) {
        // Create booking record
        Booking booking = new Booking(request);
        booking.save();  // status = PENDING
        
        // Publish event for payment
        kafka.send("payment-requests", new PaymentRequestEvent(booking.getId(), request.getAmount()));
        
        // Wait for payment confirmation
        waitForPaymentConfirmation(booking.getId(), 30000);
    }
    
    @KafkaListener(topics = "payment-confirmations")
    public void onPaymentConfirmed(PaymentConfirmationEvent event) {
        Booking booking = Booking.findById(event.getBookingId());
        booking.setStatus("CONFIRMED");
        booking.save();
        
        // Publish event for notification
        kafka.send("notification-requests", new NotificationRequestEvent(booking.getId()));
    }
}

// PaymentService.java
public class PaymentService {
    @KafkaListener(topics = "payment-requests")
    public void handlePaymentRequest(PaymentRequestEvent event) {
        // Check if already processed (idempotency)
        if (processedIds.contains(event.getId())) {
            return;
        }
        
        // Charge the card
        boolean success = paymentGateway.charge(event.getAmount());
        
        if (success) {
            processedIds.add(event.getId());
            kafka.send("payment-confirmations", new PaymentConfirmationEvent(event.getBookingId()));
        } else {
            kafka.send("payment-failures", new PaymentFailureEvent(event.getBookingId()));
        }
    }
}

What’s wrong? On paper, nothing. Idempotency keys prevent double charges. Kafka guarantees at-least-once delivery. But double charges still happen.

What “Byzantine Failure” Actually Means (No Jargon)

In 1982, Leslie Lamport published a paper called “The Byzantine Generals Problem.” The title came from a thought experiment:

Imagine several generals surround a city. They must all attack at the same time or all retreat. They can only communicate by messenger. Some generals might be traitors - they’ll send false messages to break coordination. How do the loyal generals still agree?

The kicker: Lamport later admitted he chose “Byzantine” because it sounded exotic. He wanted to avoid offending anyone by naming it after a real country. The problem he described wasn’t new - it’s the same problem that breaks voting systems, blockchain, and your microservices.

The mathematical result (important): To tolerate f traitors (or faulty nodes), you need at least 3f + 1 total nodes.

• To survive 1 traitor -> 4 nodes minimum
• To survive 2 traitors -> 7 nodes minimum
• To survive 3 traitors -> 10 nodes minimum

Why 3f+1? Here’s the actual proof in simple terms:

With 3 nodes and 1 traitor:

• Node A (loyal) hears “attack” from commander
• Node B (loyal) hears “retreat” from commander
• A tells B: “commander said attack”
• B tells A: “commander said retreat”
• A thinks: “Commander told me attack, but B says commander said retreat. Is B lying or is commander lying?”
• A cannot know. Agreement impossible.

With 4 nodes and 1 traitor:

• Nodes A, B, C (loyal) hear various things
• After two rounds of messaging, each loyal node has 3 reports
• The traitor’s lies are outvoted 2-to-1 (or 3-to-0)
• Loyal nodes can agree on the majority

How This Applies To Your Double-Charge Bug

Your system has 3 services (Booking, Payment, Notification). That’s exactly the 3-generals case. If one service has a bug (acts like a traitor), Byzantine agreement is mathematically impossible.

The actual bug in your system (discovered after 3 weeks of debugging):

The Payment Service has a bug: sometimes it processes the same payment-requests event twice. The idempotency check-processedIds.contains(event.getId()) should prevent this, but processedIds is an in-memory HashSet. When the service restarts (which happens during deployments), the set is empty.

Get Ayush Gupta’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The sequence that causes double charge:

1. Payment Service receives event evt_123.
2. Processes it, charges card, adds evt_123 to processedIds.
3. Before sending payment-confirmations, the service crashes (out of memory, network blip, whatever).
4. Kafka hasn’t received acknowledgment yet, so it redelivers evt_123.
5. Service restarts, processedIds is empty.
6. Service processes evt_123 again, charges card again.
7. Booking Service receives TWO payment-confirmations for the same booking.
8. Booking Service updates status to CONFIRMED twice (harmless).
9. Customer is charged twice. Refund process starts. Support gets angry call.

From the perspective of Booking Service: The Payment Service looks Byzantine. It sent two confirmations for the same request. Is it lying? Is it buggy? Is the network duplicating messages? Booking Service cannot know.

The Real Solution: Practical Byzantine Fault Tolerance (PBFT)

In 1999, Miguel Castro and Barbara Liskov (MIT) published PBFT - the first practical algorithm for Byzantine agreement. It works for your microservices too.

The key insight: Don’t trust a single service. Ask multiple services and compare answers.

For our booking system:

// Instead of 1 payment service, run 4 replicas (3f+1 where f=1)
// When Booking Service needs to charge a card, it asks all 4 replicas

public class ByzantineResilientBookingService {
    private static final int TOTAL_REPLICAS = 4;
    private static final int REQUIRED_AGREEMENT = 3;  // 2f+1
    
    public void chargeCustomer(String bookingId, BigDecimal amount) {
        // Phase 1: Request (send to all replicas)
        ChargeRequest request = new ChargeRequest(bookingId, amount, generateNonce());
        List<Future<ChargeResponse>> futures = new ArrayList<>();
        
        for (int i = 0; i < TOTAL_REPLICAS; i++) {
            futures.add(sendToReplica(i, request));
        }
        
        // Phase 2: Collect responses
        Map<String, List<ChargeResponse>> responsesByResult = new HashMap<>();
        for (Future<ChargeResponse> future : futures) {
            ChargeResponse resp = future.get(5, TimeUnit.SECONDS);
            String key = resp.isSuccess() + ":" + resp.getTransactionId();
            responsesByResult.computeIfAbsent(key, k -> new ArrayList<>()).add(resp);
        }
        
        // Phase 3: Find majority
        for (Map.Entry<String, List<ChargeResponse>> entry : responsesByResult.entrySet()) {
            if (entry.getValue().size() >= REQUIRED_AGREEMENT) {
                // We have consensus
                ChargeResponse consensus = entry.getValue().get(0);
                if (consensus.isSuccess()) {
                    booking.setStatus("CONFIRMED");
                    booking.setTransactionId(consensus.getTransactionId());
                } else {
                    booking.setStatus("FAILED");
                }
                booking.save();
                return;
            }
        }
        
        // No consensus - possible Byzantine failure
        throw new ByzantineFailureException("Payment replicas cannot agree: " + responsesByResult);
    }
}

How this prevents double charge: Even if one replica is buggy (or malicious) and sends two confirmations, the other three loyal replicas will send only one. The majority vote (3 out of 4) will be correct.

The cost: 4x the infrastructure. 4x the network messages. O(n²) message complexity. For each charge, you send 4 requests and receive 4 responses = 16 messages total. With 1 replica, you send 1 request and get 1 response = 2 messages. PBFT is 8x more chatty.

This is why most companies don’t run PBFT. They accept the occasional double charge and refund it. The math says you can’t have both low cost and Byzantine fault tolerance. You have to choose.

The GitHub Outage (June 10, 2026) - A Real-World Byzantine-Like Failure

What GitHub reported: “Erroneous 401 responses causing app integrations to trigger authentication flows.”

What actually happened (reconstructed from public post-mortems):

GitHub’s authentication system has a cache. The cache has multiple replicas for performance. On June 10, one replica started returning stale data. Specifically:

• Replica A: returns correct token status
• Replica B: returns stale “token invalid” for tokens that are actually valid
• Replica C: returns correct token status
• Replica D: returns correct token status

To a client that happens to talk to Replica B: The auth system is broken. It says my token is invalid but it’s not.
To a client that talks to Replica A: The auth system is fine.

This is not Byzantine. No one is malicious. But the effect is identical to Byzantine failure: different clients receive conflicting information from the same system.

The cascading failure:

1. Clients that hit Replica B get 401
2. They correctly re-authenticate (OAuth spec says: on 401, refresh token)
3. Thousands of clients simultaneously hit the auth endpoint
4. The auth endpoint, already under stress, gets overloaded
5. More timeouts, more retries, more 401s
6. The good replicas start timing out too
7. Eventually, all clients see failures

The fix GitHub applied (from their status page):

• Added circuit breakers to their client SDKs
• Implemented exponential backoff with jitter
• Added client-side caching of auth failures

The fix that would have prevented it (Byzantine-style):

• Run 4 auth replicas (instead of 2)
• Make clients query at least 3 replicas and take majority
• If 2 say “valid” and 1 says “invalid”, trust the majority

But GitHub didn’t do this. Why? Cost. 4 replicas vs 2 means double the infrastructure. Quorum reads mean 3x the network traffic. For a company GitHub’s size, that’s millions of dollars per year. They accepted the risk of a 80-minute outage every few years instead.

Now, If this resonated with you, share it with someone who might enjoy it too.