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

Abstract

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.