Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulti-hop Byzantine Reliable Broadcast with Honest Dealer Made Practical
98
0
0.0
(
0
)
Added by
Giovanni Farina
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We revisit Byzantine tolerant reliable broadcast with honest dealer algorithms in multi-hop networks. To tolerate Byzantine faulty nodes arbitrarily spread over the network, previous solutions require a factorial number of messages to be sent over the network if the messages are not authenticated (e.g. digital signatures are not available). We propose modifications that preserve the safety and liveness properties of the original unauthenticated protocols, while highly decreasing their observed message complexity when simulated on several classes of graph topologies, potentially opening to their employment.
rate research
Read More
In this paper, we consider the Byzantine reliable broadcast problem on authenticated and partially connected networks. The state-of-the-art method to solve this problem consists in combining two algorithms from the literature. Handling asynchrony and faulty senders is typically done thanks to Gabriel Brachas authenticated double-echo broadcast protocol, which assumes an asynchronous fully connected network. Danny Dolevs algorithm can then be used to provide reliable communications between processes in the global fault model, where up to f processes among N can be faulty in a communication network that is at least 2f+1-connected. Following recent works that showed that Dolevs protocol can be made more practical thanks to several optimizations, we show that the state-of-the-art methods to solve our problem can be optimized thanks to layer-specific and cross-layer optimizations. Our simulations with the Omnet++ network simulator show that these optimizations can be efficiently combined to decrease the total amount of information transmitted or the protocols latency (e.g., respectively, -25% and -50% with a 16B payload, N=31 and f=4) compared to the state-of-the-art combination of Brachas and Dolevs protocols.
Ensuring reliable communication despite possibly malicious participants is a primary objective in any distributed system or network. In this paper, we investigate the possibility of reliable broadcast in a dynamic network whose topology may evolve while the broadcast is in progress. In particular, we adapt the Certified Propagation Algorithm (CPA) to make it work on dynamic networks and we present conditions (on the underlying dynamic graph) to enable safety and liveness properties of the reliable broadcast. We furthermore explore the complexity of assessing these conditions for various classes of dynamic networks.
In this note, we observe a safety violation in Zyzzyva and a liveness violation in FaB. To demonstrate these issues, we require relatively simple scenarios, involving only four replicas, and one or two view changes. In all of them, the problem is manifested already in the first log slot.
This paper explores the problem good-case latency of Byzantine fault-tolerant broadcast, motivated by the real-world latency and performance of practical state machine replication protocols. The good-case latency measures the time it takes for all non-faulty parties to commit when the designated broadcaster is non-faulty. We provide a complete characterization of tight bounds on good-case latency, in the authenticated setting under synchrony, partial synchrony and asynchrony. Some of our new results may be surprising, e.g., 2-round PBFT-style partially synchronous Byzantine broadcast is possible if and only if $ngeq 5f-1$, and a tight bound for good-case latency under $n/3<f<n/2$ under synchrony is not an integer multiple of the delay bound.
The Reliable Broadcast concept allows an honest party to send a message to all other parties and to make sure that all honest parties receive this message. In addition, it allows an honest party that received a message to know that all other honest parties would also receive the same message. This technique is important to ensure distributed consistency when facing failures. In the current paper, we study the ability to use RR to consistently transmit a sequence of input values in an asynchronous environment with a designated sender. The task can be easily achieved using counters, but cannot be achieved with a bounded memory facing failures. We weaken the problem and ask whether the receivers can at least share a common suffix. We prove that in a standard (lossless) asynchronous system no bounded memory protocol can guarantee a common suffix at all receivers for every input sequence if a single party might crash. We further study the problem facing transient faults and prove that when limiting the problem to transmitting a stream of a single value being sent repeatedly we show a bounded memory self-stabilizing protocol that can ensure a common suffix even in the presence of transient faults and an arbitrary number of crash faults. We further prove that this last problem is not solvable in the presence of a single Byzantine fault. Thus, this problem {bf separates} Byzantine behavior from crash faults in an asynchronous environment.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
