Περίληψη:
Interactive consistency is the problem in which n nodes, where up to t
may be byzantine, each with its own private value, run an algorithm that
allows all non-faulty nodes to infer the values of each other node. This
problem is relevant to critical applications that rely on the
combination of the opinions of multiple peers to provide a service.
Examples include monitoring a content source to prevent equivocation or
to track variability in the content provided, and resolving divergent
state amongst the nodes of a distributed system.
Previous works assume a fully synchronous system, where one can make
strong assumptions such as negligible message delivery delays and/or
detection of absent messages. However, practical, real-world systems are
mostly asynchronous, i.e., they exhibit only some periods of synchrony
during which message delivery is timely, thus requiring a different
approach. In this paper, we present a thorough study on practical
interactive consistency. We leverage the vast prior work on broadcast
and byzantine consensus algorithms to design, implement and evaluate a
set of algorithms, with varying timing assumptions and message
complexity, that can be used to achieve interactive consistency in
real-world distributed systems.
We provide a complete, open-source implementation of each proposed
interactive consistency algorithm by building a multilayered stack of
protocols that include several broadcast protocols, as well as a binary
and a multi-valued consensus protocol. Most of these protocols have
never been implemented and evaluated in a real system before. We analyze
the performance of our suite of algorithms experimentally by engaging in
both single instance and multiple parallel instances of each
alternative.
Συγγραφείς:
Diamantopoulos, Panos
Maneas, Stathis
Patsonakis, Christos and
Chondros, Nikos
Roussopoulos, Mema
