Randomized agreement protocols have been a … Randomized agreement protocols have been around for more than two
decades. Often assumed to be inefficient due to their high expected communication and time complexities, they have remained largely overlooked
by the community-at-large as a valid solution for the deployment of fault tolerant distributed systems. This thesis aims to demonstrate that randomization can be a very competitive approach even in hostile environments
where arbitrary faults can occur. The implementation of a stack of
randomized intrusion-tolerant protocols is described, and its performance
evaluated under different fault loads. The stack provides a set of relevant
services ranging from basic communication primitives up to atomic broadcast.
The protocols share a set of important structural properties, namely
they tolerate arbitrary faults, have an optimal resilience, are time-free,
completely decentralized, and signature-free. The experimental evaluation
shows that the protocols are efficient and no performance reduction
is observed under certain Byzantine faults. s observed under certain Byzantine faults.