Byzantine Consensus Randomized - Monte Carlo Implementation with matrix for value sending

Question

In order to achieve the Bizantine Consensus, these 3 rules must apply: during every round each process must send a bit (with value either 0 or 1) to the others n-1 processes; before the start of a new round each process must have received a bit from every other process; in each round every process has sent his bit to all the other processes.

I need to implement the following Rabin-based, Monte Carlo Byzantine Consensus randomized protocol for 661 non-traitor processes out of 991 total processes:

Variables:
b(i) = value to send to all other processes, initially = input value
p = global random number which can be either 1 and 0, picked after every run
maj(i) = majority value
tally(i) = number of times majority appears in b(i)

Implementation:
loop = TRUE
while (loop)
   1. send b(i) to the other n−1 processes
   2. receive the values sent by the other n−1 processes
   3. set maj(i) = majority value in b(i)
   4. set tally(i) = number of times the majority value appears  
   5. if tally(i) ≥ 2t + 1 
          then b(i) = maj(i) 
      else if (p=1) then b(i) = 1 
      else b(i) ← 0

My question would be: how can I implement the data structure which stores for every process the bits they have sent and received, not to mention how to implement the sending mechanism itself? I was thinking about implementing an array A.i[j] for each process, where j ranges over all process ids. I have heard it is possible to make processes read the values of the other n-1 processes from such a table instead of implemeneting a sending mechanism; how could I implement this?

Answer 1

I solved this problem by creating a class Process with a Type and vote attribute and a getVote() method,

• Type: reliable, unreliable
• Vote: the vote (v0 at the beginning, it will converge to v following the protocol)
• setVote(): sets the vote.
• getVote(): if type is reliable then return the bit else return random number between 0 and 1.

To simulate a distributed algo, you can run the protocol in separate threads, each one containing a process class and communicate with a shared common array which you can update each round.

An example here

You can also simulate everything starting from an array of these objects, without the need of separate threads.

I believe that should be enough to handle the model.

something like this:

        export class Process {

      constructor(public pid: number, public vote: number, public type: ProcessType ) {  }

      set(bit: number) {
        this.vote = this.send(bit);
      }

      send(b) {
        if (this.type === ProcessType.unreliable) {
          return Math.round(Math.random());
        }
        return b;
      }

      get() {
        return { pid: this.pid, vote: this.vote, type: this.type};
      }

      getVote() {
        return this.send(this.vote);
      }
    }

Good luck!