Implentation,validation and experimental evaluation of a distributed randomized common coin algorithm

View/ Open
Date
2022-07-28Author
Kousiappas, MichalisPublisher
Πανεπιστήμιο Κύπρου, Σχολή Θετικών και Εφαρμοσμένων Επιστημών / University of Cyprus, Faculty of Pure and Applied SciencesPlace of publication
CyprusGoogle Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
A crucial problem found in distributed system is to achieve trustworthyness. If we know who
to trust then we can try and reach consensus which is to decide a common value for everyone.
This becomes significantly more difficult when some of the nodes in the network are
malicious and conspire against the well-behaving nodes that want to reach consensus.
Consider a synchronous distributed system with nodes that communicate using messages over
a network and some of the nodes missbehave with no knowledge on how or why. Could the
well-behaved nodes reach consensus? Feldman and Micali present such an algorithm, known
as a common coin algorithm, in their paper and how to construct it. The common coin
algorithm will output 0 or 1 at the end and all well-behaving nodes will agree on that value,
thus reaching binary consensus. The protocol is optimally resilient meaning that if up to t <
n/3 number of nodes are faulty, the non-faulty nodes can still reach consencus. The purpose
of this thesis is to implement this algorithm. With this implementation we validate the
algorithm’s correctness in the absence and pressence of faults and measure its execution time.