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?
Aucun commentaire:
Enregistrer un commentaire