У меня проблемы с правильной инициализацией матрицы, содержащей сообщения, отправленные и полученные каждым генералом в проблеме Византийского консенсуса / соглашения. Вот псевдокод, который мне нужно реализовать:
Each processes i maintains an array prefi[j] where j ranges over all process ids.
There are also utility values majority and multiplicity.
Initially, prefi[i] = input and prefi[j] = 0 for j <> i.
After each round, a coin is tossed with 1/2 results probability of it being 1.
loop = TRUE
while(loop)
send prefi[i] to all other n-1 processes
set prefi[j] = vj where vj is the value received from process j.
set majority = majority value in prefi and multiplicity = # of times majority appears in prefi.
if multiplicity > 2t + 1 then
prefi[i] = majority
else if coin = 1
prefi[i] = 1
else
prefi[i] = 0
Вот моя реализация python, которая, к сожалению, не дает никаких полезных результатов; возможно, это могло быть из-за части инициализации:
from collections import Counter
from random import randint
moneta = randint(0,1)
class General:
def __init__(self, id, is_traitor=False):
self.id = id
self.altri = []
self.ordini = []
self.is_traitor = is_traitor
def __call__(self, m, order):
"""Args:
commander (General): A reference to the general
who issued the previous command.
m (int): The level of recursion .
order (str): The received order, such that
order ∈ {"1","0"}.
"""
if m < 0:
self.ordini.append(order)
elif m == 0:
for i, l in enumerate(self.altri):
l.__call__(
m=(m - 1),
order=self._next_order(self.is_traitor, order)
)
else:
for i, l in enumerate(self.altri):
if l is not self and i is not l:
l.__call__(m=(m - 1),order=self._next_order(self.is_traitor, order))
def majority(List):
counter = 0
num = List[0]
for i in List:
curr_frequency = List.count(i)
if(curr_frequency> counter):
counter = curr_frequency
num = i
return num
def tally(List):
return List.count(majority(List))
@property
def decision(self):
"""Returns a tally of the General's received commands.
"""
maj = majority(self.orders)
if tally >= (2*331+1):
order=maj
elif moneta == 1:
order=1
else:
order=0
return order
def _next_order(self, is_traitor, order):
"""A helper function to determine what each commander
should pass on as the next order.
Args:
is_traitor (bool): True for traitors.
order (str): The received order, such that
order ∈ {"1","0"}.
Returns:
str: The resulting order ("1" or "0").
"""
if is_traitor:
n = randint(0,1)
if n % 2 == 0:
return "ATTACK" if order == "RETREAT" else "RETREAT"
return order
def init_generals(v0):
"""Returns:
list: A list of initialized generals.
"""
processi = []
for i in range(991):
singolo = General(i)
if i <= 331:
singolo.is_traitor = True
else:
for j in range(len(singolo.ordini))
singolo.ordini.append(v0)
processi.append(singolo)
# Add list of other generals to each general.
for singolo in processi:
singolo.altri = processi
return processi
def print_decisions(processi):
for i, l in enumerate(processi):
print("General {} ha scelto {}".format(i, l.decision))
def main():
v0 = 0
processi = init_generals(v0)
print_decisions(processi)
if __name__ == "__main__":
main()
Я почти уверен, что могут быть некоторые ошибки Python -specifi c, так как это мой первый раз, когда я кодирую язык; неужели я тоже неверно истолковал псудокод?