Византийский консенсус рандомизированный - Монте-Карло Реализация с матрицей для отправки значения - PullRequest
Новая
       72

Византийский консенсус рандомизированный - Монте-Карло Реализация с матрицей для отправки значения

0 голосов
/ 04 мая 2020

Для достижения византийского консенсуса должны применяться эти 3 правила: во время каждого раунда каждый процесс должен посылать бит (со значением 0 или 1) другим n-1 процессам; перед началом нового раунда каждый процесс должен получить немного от каждого другого процесса; в каждом раунде каждый процесс отправлял свой бит всем остальным процессам.

Мне нужно реализовать следующий рандомизированный протокол Монте-Карло по византийскому консенсусу на основе Рабина для 661 не-предательских процессов из общего числа 991 процессов: 

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

Мой вопрос будет таким: как я могу реализовать структуру данных, которая хранит для каждого процесса отправленные и полученные биты, не говоря уже о том, как реализовать сам механизм отправки? Я думал о реализации массива Ai [j] для каждого процесса, где j охватывает все идентификаторы процессов. Я слышал, что можно заставить процессы читать значения других n-1 процессов из такой таблицы вместо реализации механизма отправки; как я мог реализовать это?

1 Ответ

1 голос
/ 10 мая 2020

Я решил эту проблему, создав класс Process с атрибутом типа и голосования и методом getVote(),

  • Тип: надежный, ненадежный
  • Голосование: голосование ( v0 в начале будет сходиться к v по протоколу)
  • setVote(): установить голосование.
  • getVote(): если тип является надежным, вернуть бит иначе возвращает случайное число от 0 до 1.

Для имитации распределенного алгоритма go вы можете запустить протокол в отдельных потоках, каждый из которых содержит класс процесса, и взаимодействовать с общий общий массив, который вы можете обновлять каждый раунд.

Пример здесь

Вы также можете моделировать все, начиная с массива этих объектов, без необходимости использования отдельных потоков ,

Полагаю, этого должно хватить для управления моделью.

примерно так: 

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

Удачи!

...