拜占庭共识随机化 - Monte Carlo 价值发送矩阵实现

Question

为了实现拜占庭共识，必须应用这 3 条规则：在每一轮中，每个进程必须向其他 n-1 个进程发送一个位（值为 0 或 1）；在新一轮开始之前，每个进程都必须从其他每个进程接收到一个位；在每一轮中，每个进程都将他的位发送给所有其他进程。

我需要为 991 个进程中的 661 个非叛徒进程实施以下基于 Rabin 的 Monte Carlo 拜占庭共识随机协议：

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

我的问题是：如何实现为每个进程存储它们发送和接收的位的数据结构，更不用说如何实现发送机制本身了？我正在考虑为每个进程实现一个数组 A.i[j] ，其中 j 涵盖所有进程 ID。我听说可以让进程从这样的 table 中读取其他 n-1 个进程的值，而不是实现发送机制；我怎么能实现这个？

Answer 1

我通过创建一个带有 Type 和 vote 属性和 getVote() 方法的 class 进程解决了这个问题，

类型：可靠、不可靠
投票：投票（v0开头，按照协议会收敛到v）
setVote(): 设置投票。
getVote()：如果类型可靠，则 return 0 和 1 之间的位 return 随机数。

要模拟分布式算法，您可以运行单独线程中的协议，每个线程包含一个进程 class 并与共享的公共数组通信，您可以在每一轮更新该数组。

一个例子here

您还可以从这些对象的数组开始模拟所有内容，而无需单独的线程。

我相信这应该足以处理模型。

像这样：

        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);
      }
    }

祝你好运！

拜占庭共识随机化 - Monte Carlo 价值发送矩阵实现

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

python

c++

random

distributed-system

consensus