In our modern economy, a problem that often comes up is getting computers to agree to something, whether that be all the computers in your bank's branches agreeing that you did in fact make that deposit, or the food delivery app on your phone agreeing with the one in the restaurant’s that you have placed an order and they should start preparing it. You might think, well that’s an easy problem- you phone should send an order to the restaurant, then the restaurant sends back a confirmation that they have received the order. Then you’ll know that the restaurant has received your order. But how does the restaurant know that you have received the confirmation? If the restaurant’s confirmation gets lost, you might think the restaurant never got the order, so you place another order. Now what does the restaurant do with this second order? Is this another order for the same item, or a duplicate of the first that it should ignore? Aha- you think, I’ll send a confirmation of the confirmation back to the restaurant. But how do you know that the restaurant got the confirmation of the confirmation? It turns out that with this approach- sending confirmations of confirmations, you will never be able to come up with a fail proof method of getting your app and the restaurant’s to agree on your order.

It turns out that this exact situation has a much older analog:

The Byzantine Generals Agreement Problem

Classically, the problem goes like this: the Byzantine army is about to invade a city the next morning. They have the city surrounded on all sides by their army units. This city is tough though- surrounded by a big wall and with good defenses. The units all need to coordinate and plan to attack all at once or else they will be defeated. The problem is this: how can the commander message all the units so they are all either in agreement to attack or to fall back? The messengers will need to go through tough terrain and enemies, and some may not make it. He cannot risk attacking without being sure that everyone else will. How does he does he do it?

How can Unit 1 be sure that Units 2 and 3 will attack?

Tom Scott also has an excellent explanation of this problem here. Ignore his explanation of the idempotency token for now- we’ll talk through the solution in detail.

To make the problem harder, the army knows there are enemy spies around, even within their own commanders and messengers who will try and thwart his attack. These spies will want to convince some units to attack while convincing others to stay back.

Unit 2 is getting mixed messages. Unit 3 could be lying about what the commander said. He can’t be certain who to trust.

Or maybe Unit 1 is lying to Unit 2 and Unit 3. Unit 2 is not able to tell from the 2 above scenarios.

To add one more thing to consider, we are going to give each unit a weight representing how much each unit can be trusted. We’ll give more weight to units who we know are more trustworthy, and less to units who we can be more skeptical of. We’ll normalize the weights so they sum to 1.0.

Looking back at our problem of ordering food through a delivery app, that problem is just a case of the Byzantine Generals with 2 units that must agree to attack (or deliver our food).

The Paxos Algorithm

Before going into a full solution for the problem, we need to first understand the Paxos algorithm to solve the problem we first discussed: getting computers (or army units) to agree to something when messages(and even computers) can be lost. It will work like this: one of the computers will act as a proposer, propose a value (like attack or fall back), then the other units will accept the values, and after a finite number of messages, the computers will have agreed to the value.

This algorithm in detail is best described by Leslie Lamport in his 2001 paper “Paxos Made Simple” that I’ve linked here so I’ll briefly skim through the algorithm here. The Computerphile channel on Youtube also has a good explanation available here.

Proposers, Acceptors, and Learners

In the Paxos algorithm, computers can take 3 roles:

Proposers- propose a value by sending a promise to the Acceptor(s) during Phase 1 of the algorithm. If that is successful, during Phase 2, Proposers send commits to the algorithms. If that is successful, after phase 2, the value is chosen and computer have agreed on the value.
Acceptors- receive promises and commits from the Proposers and either accept or reject them. If a consensus of promises are accepted, the value can be committed by the proposer. If the commit is accepted by a consensus of proposers, then the value is chosen and the computers agree to the value. For this algorithm, a consensus is a majority of servers.
Learners- computer can go down or fail to receive messages. Computers become Learners when coming back up after a failure, and learn of chosen values from the other Acceptors.

Proposers send a Promise during Phase 1, and a commit during Phase 2. Afterwards the value is agreed to. For brevity, learners are not shown.

There are lot more details of the Paxos algorithm in order to implement it, so please go through Lamport’s paper. The paper also provides explanation of how the algorithm is fault tolerant to messages being lost and/or Acceptors going down.

Byzantine Paxos

Now that we’re able to get our units (or servers) to agree to a value, let’s reintroduce the spies back into the problem. How can we modify the Paxos algorithm to handle cases were Acceptors, and even Proposers will try to deceive others (the academic term for this is a Byzantine fault) ?

It turns out that this can be handled with 2 major modifications:

Acceptors will broadcast promises and commits received to the other Acceptors, and accept the request only if a consensus of the Acceptors agree on the value from the promise or commit.
Proposers will send an additional message to Acceptors after Phase 1. The message will mark a value as safe. Acceptors will also broadcast this message to each other. The Proposer does not need to wait for a response back from Acceptors to this message before moving onto the commit.

Again, Leslie Lamport developed this algorithm in this 2011 paper linked here. Read through it for full implementation details. Most importantly, pay attention to the proof that solving the problem is impossible when 1/4 or more of the servers are Byzantine faulty. There is also a good Youtube video on the subject from Microsoft Research available here.

Acceptors broadcast messages to each other to handle Byzantine faults

Weighted Byzantine Paxos

The final detail to add is adding weights to the agents. We’ll need to assign normalized weights to each server that acceptors and proposers will utilize to accept requests or move onto the next phases. Very similarly to the Byzantine Paxos algorithm, it turns out that agreement is impossible if more a weight of 1/4 or more is Byzantine faulty.

For a detailed explanation of the algorithm, please go through this presentation and this paper that my classmate Matt Molter and I wrote for our Distributed Systems course, as well as our implementation of the algorithm available at https://github.com/JavierPalomares90/Distributed_Agreement/

Demo

In the implementation, we added Byzantine Acceptor classes that will intentionally flip the value in the broadcasts to try to confuse the other acceptors. We’ll see how our implementation handles this and proceeds to agree on the value.

We’ll run the algorithm with 3 servers with weights 0.4,0.2, and 0.4. I’ll have server 2 be Byzantine faulty- it will always broadcast the wrong value. It has weight 0.2 so we can still reach a consensus. I’ll have server 1 propose the values, and servers 2 and 3 act as the acceptors.

Server 1

2020-04-04 17:57:23,117 DEBUG distributed.DistributedAgreement.main() distributed.DistributedAgreement - Starting serverId: 1
2020-04-04 17:57:23,121 DEBUG distributed.DistributedAgreement.main() distributed.utils.Utils - Getting hosts from hosts.yaml
2020-04-04 17:57:23,184 DEBUG Thread-2 distributed.server.threads.ServerThread - Starting server thread with ip: 127.0.0.1 port: 8080
2020-04-04 17:57:31,985 DEBUG Thread-2 distributed.server.threads.ServerThread - Accepted client connection from 127.0.0.1:52418
2020-04-04 17:57:31,986 DEBUG Thread-2 distributed.utils.Utils - 127.0.0.1 52418 [Server(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2), Server(ipAddress=127.0.0.1, port=8082, serverId=3, weight=0.4)]
2020-04-04 17:57:31,996 DEBUG Thread-3 distributed.server.threads.MessageThread - Processing message: PROPOSE 0
2020-04-04 17:57:31,998 DEBUG Thread-3 distributed.server.threads.MessageThread - Proposing value using paxos: 0
2020-04-04 17:57:32,000 DEBUG Thread-3 distributed.server.byzantine.ByzPaxos - Proposing value 0 with id 1
2020-04-04 17:57:32,005 DEBUG Thread-3 distributed.server.paxos.propose.Proposer - Proposing value 0
2020-04-04 17:57:32,006 DEBUG Thread-3 distributed.server.paxos.propose.Proposer - Sending prepare request to acceptors
2020-04-04 17:57:32,006 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - sending prepare request
2020-04-04 17:57:32,006 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Executing send request pool: PREPARE_REQUEST 1 0 1
 waitForResponse: true
2020-04-04 17:57:32,010 DEBUG pool-2-thread-1 distributed.server.threads.WeightedRequestThread - Sending request PREPARE_REQUEST 1 0 1
 to acceptorServer(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)
2020-04-04 17:57:32,010 DEBUG pool-2-thread-2 distributed.server.threads.WeightedRequestThread - Sending request PREPARE_REQUEST 1 0 1
 to acceptorServer(ipAddress=127.0.0.1, port=8082, serverId=3, weight=0.4)
2020-04-04 17:57:32,073 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Response from acceptor REJECT_PREPARE 1 null
2020-04-04 17:57:32,073 DEBUG Thread-3 distributed.server.threads.ServerThread - No Byzquorum possible.
2020-04-04 17:57:32,074 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Promise rejected weight: 0.2
2020-04-04 17:57:32,074 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Response from acceptor PROMISE 1 0
2020-04-04 17:57:32,075 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Promised weight: 0.8
2020-04-04 17:57:32,075 DEBUG Thread-3 distributed.server.byzantine.ByzPaxos - Sending safe request
2020-04-04 17:57:32,075 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Sending safe for value 0
2020-04-04 17:57:32,076 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Sending safe request
2020-04-04 17:57:32,076 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Executing send request pool: SAFE_REQUEST 1 0 1
 waitForResponse: false
2020-04-04 17:57:32,078 DEBUG pool-3-thread-2 distributed.server.threads.WeightedRequestThread - Sending request SAFE_REQUEST 1 0 1
 to acceptorServer(ipAddress=127.0.0.1, port=8082, serverId=3, weight=0.4)
2020-04-04 17:57:32,078 DEBUG pool-3-thread-1 distributed.server.threads.WeightedRequestThread - Sending request SAFE_REQUEST 1 0 1
 to acceptorServer(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)
2020-04-04 17:57:32,084 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Response from acceptor 
2020-04-04 17:57:32,084 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Response from acceptor 
2020-04-04 17:57:32,085 DEBUG Thread-3 distributed.server.byzantine.ByzPaxos - Starting phase 2
2020-04-04 17:57:32,085 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - sending accept request
2020-04-04 17:57:32,086 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Executing send request pool: ACCEPT_REQUEST 1 0
 waitForResponse: true
2020-04-04 17:57:32,087 DEBUG pool-4-thread-1 distributed.server.threads.WeightedRequestThread - Sending request ACCEPT_REQUEST 1 0
 to acceptorServer(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)
2020-04-04 17:57:32,094 DEBUG pool-4-thread-2 distributed.server.threads.WeightedRequestThread - Sending request ACCEPT_REQUEST 1 0
 to acceptorServer(ipAddress=127.0.0.1, port=8082, serverId=3, weight=0.4)
2020-04-04 17:57:32,136 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Response from acceptor REJECT_ACCEPT 1 0
2020-04-04 17:57:32,136 DEBUG Thread-3 distributed.server.threads.ServerThread - No Byzquorum possible.
2020-04-04 17:57:32,136 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Rejected weight: 0.2
2020-04-04 17:57:32,136 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Response from acceptor ACCEPT 1 0
2020-04-04 17:57:32,137 DEBUG Thread-3 distributed.server.byzantine.propose.ByzProposer - Accepted weight: 0.8
2020-04-04 17:57:32,137 DEBUG Thread-3 distributed.server.byzantine.ByzPaxos - Waiting for value agreement
2020-04-04 17:57:32,137 DEBUG Thread-3 distributed.server.byzantine.ByzPaxos - Agreed to value

Server 3

2020-04-04 17:57:20,545 DEBUG distributed.DistributedAgreement.main() distributed.DistributedAgreement - Starting serverId: 3
2020-04-04 17:57:20,551 DEBUG distributed.DistributedAgreement.main() distributed.utils.Utils - Getting hosts from hosts.yaml
2020-04-04 17:57:20,596 DEBUG Thread-2 distributed.server.threads.ServerThread - Starting server thread with ip: 127.0.0.1 port: 8082
2020-04-04 17:57:32,017 DEBUG Thread-2 distributed.server.threads.ServerThread - Accepted client connection from 127.0.0.1:43352
2020-04-04 17:57:32,017 DEBUG Thread-2 distributed.utils.Utils - 127.0.0.1 43352 [Server(ipAddress=127.0.0.1, port=8080, serverId=1, weight=0.4), Server(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)]
2020-04-04 17:57:32,025 DEBUG Thread-3 distributed.server.threads.MessageThread - Processing message: PREPARE_REQUEST 1 0 1
2020-04-04 17:57:32,036 DEBUG Thread-3 distributed.server.byzantine.accept.ByzAcceptor - Receiving prepare request with id 1 value 0 from senderID: 1
2020-04-04 17:57:32,037 DEBUG Thread-3 distributed.server.byzantine.accept.ByzAcceptor - Broadcasting prepare request
2020-04-04 17:57:32,038 DEBUG Thread-3 distributed.server.byzantine.accept.ByzAcceptor - Broadcasting command PREPARE_BROADCAST 1 0
  to [Server(ipAddress=127.0.0.1, port=8080, serverId=1, weight=0.4), Server(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)]
2020-04-04 17:57:32,038 DEBUG Thread-3 distributed.server.byzantine.accept.ByzAcceptor - Quorum weight : 0.75
2020-04-04 17:57:32,042 DEBUG pool-2-thread-1 distributed.server.threads.WeightedBroadcastThread - Sending request PREPARE_BROADCAST 1 0
 to acceptorServer(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)
2020-04-04 17:57:32,051 DEBUG Thread-3 distributed.server.byzantine.accept.ByzAcceptor - Received reject with weight 0.2. Rejected weight 0.20000000298023224
2020-04-04 17:57:32,052 DEBUG Thread-3 distributed.server.byzantine.accept.ByzAcceptor - Accepts reached quorum. Accepting
2020-04-04 17:57:32,062 DEBUG Thread-2 distributed.server.threads.ServerThread - Accepted client connection from 127.0.0.1:43356
2020-04-04 17:57:32,063 DEBUG Thread-2 distributed.utils.Utils - 127.0.0.1 43356 [Server(ipAddress=127.0.0.1, port=8080, serverId=1, weight=0.4), Server(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)]
2020-04-04 17:57:32,066 DEBUG Thread-4 distributed.server.threads.MessageThread - Processing message: PREPARE_BROADCAST 1 1
2020-04-04 17:57:32,067 DEBUG Thread-4 distributed.server.byzantine.accept.ByzAcceptor - Received prepare broadcast with id: 1 value 1
2020-04-04 17:57:32,068 DEBUG Thread-4 distributed.server.byzantine.accept.ByzAcceptor - We have not received this proposed value. Rejecting
2020-04-04 17:57:32,080 DEBUG Thread-2 distributed.server.threads.ServerThread - Accepted client connection from 127.0.0.1:43358
2020-04-04 17:57:32,080 DEBUG Thread-2 distributed.utils.Utils - 127.0.0.1 43358 [Server(ipAddress=127.0.0.1, port=8080, serverId=1, weight=0.4), Server(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)]
2020-04-04 17:57:32,090 DEBUG Thread-5 distributed.server.threads.MessageThread - Processing message: SAFE_REQUEST 1 0 1
2020-04-04 17:57:32,091 DEBUG Thread-5 distributed.server.byzantine.accept.ByzAcceptor - Received safe request with id: 1 value: 0 from serverID 1
2020-04-04 17:57:32,093 DEBUG Thread-5 distributed.server.byzantine.accept.ByzAcceptor - Adding value to map with isSafe=false
2020-04-04 17:57:32,095 DEBUG Thread-2 distributed.server.threads.ServerThread - Accepted client connection from 127.0.0.1:43364
2020-04-04 17:57:32,095 DEBUG Thread-2 distributed.utils.Utils - 127.0.0.1 43364 [Server(ipAddress=127.0.0.1, port=8080, serverId=1, weight=0.4), Server(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)]
2020-04-04 17:57:32,096 DEBUG Thread-6 distributed.server.threads.MessageThread - Processing message: ACCEPT_REQUEST 1 0
2020-04-04 17:57:32,097 DEBUG Thread-6 distributed.server.byzantine.accept.ByzAcceptor - Received accept request with id: 1 value: 0
2020-04-04 17:57:32,104 DEBUG Thread-6 distributed.server.byzantine.accept.ByzAcceptor - Waiting for safe broadcast to finish before proceeding
2020-04-04 17:57:32,105 DEBUG Thread-7 distributed.server.byzantine.accept.ByzAcceptor - Broadcasting safe request to other acceptors.
2020-04-04 17:57:32,106 DEBUG Thread-7 distributed.server.byzantine.accept.ByzAcceptor - Broadcasting command SAFE_BROADCAST 1 0
  to [Server(ipAddress=127.0.0.1, port=8080, serverId=1, weight=0.4), Server(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)]
2020-04-04 17:57:32,106 DEBUG Thread-7 distributed.server.byzantine.accept.ByzAcceptor - Quorum weight : 0.75
2020-04-04 17:57:32,109 DEBUG pool-3-thread-1 distributed.server.threads.WeightedBroadcastThread - Sending request SAFE_BROADCAST 1 0
 to acceptorServer(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)
2020-04-04 17:57:32,115 DEBUG Thread-7 distributed.server.byzantine.accept.ByzAcceptor - Received reject with weight 0.2. Rejected weight 0.20000000298023224
2020-04-04 17:57:32,116 DEBUG Thread-7 distributed.server.byzantine.accept.ByzAcceptor - Accepts reached quorum. Accepting
2020-04-04 17:57:32,118 DEBUG Thread-2 distributed.server.threads.ServerThread - Accepted client connection from 127.0.0.1:43368
2020-04-04 17:57:32,121 DEBUG Thread-2 distributed.utils.Utils - 127.0.0.1 43368 [Server(ipAddress=127.0.0.1, port=8080, serverId=1, weight=0.4), Server(ipAddress=127.0.0.1, port=8081, serverId=2, weight=0.2)]
2020-04-04 17:57:32,122 DEBUG Thread-7 distributed.server.byzantine.accept.ByzAcceptor - Is value safe?: true
2020-04-04 17:57:32,122 DEBUG Thread-7 distributed.server.byzantine.accept.ByzAcceptor - Getting lock
2020-04-04 17:57:32,122 DEBUG Thread-7 distributed.server.byzantine.accept.ByzAcceptor - Notifiying everyone that wait for safe is done
2020-04-04 17:57:32,122 DEBUG Thread-8 distributed.server.threads.MessageThread - Processing message: PREPARE_BROADCAST 1 1
2020-04-04 17:57:32,123 DEBUG Thread-8 distributed.server.byzantine.accept.ByzAcceptor - Received prepare broadcast with id: 1 value 1
2020-04-04 17:57:32,123 DEBUG Thread-8 distributed.server.byzantine.accept.ByzAcceptor - We have not received this proposed value. Rejecting
2020-04-04 17:57:32,135 DEBUG Thread-6 distributed.server.byzantine.accept.ByzAcceptor - Proceeding
2020-04-04 17:57:32,135 DEBUG Thread-6 distributed.server.byzantine.accept.ByzAcceptor - Checking that the value is safe
2020-04-04 17:57:32,135 DEBUG Thread-6 distributed.server.byzantine.accept.ByzAcceptor - Value is safe. Continuing with the paxos impl
2020-04-04 17:57:32,135 DEBUG Thread-6 distributed.server.paxos.accept.Acceptor - Received accept request
2020-04-04 17:57:32,135 DEBUG Thread-6 distributed.server.paxos.accept.Acceptor - Accepting accept request

We can see that Servers 1 and 3 are still able to come to a consensus and reach agreement.

The Weighted Byzantine Distributed Agreement Problem