Robustness and Fault Tolerance in Distributed Systems

The field of distributed systems is moving towards developing more robust and fault-tolerant protocols and algorithms. Researchers are exploring new ways to make systems resilient to manipulation, faults, and adversarial behavior. One of the key directions is the design of protocols that can tolerate a certain level of manipulation or faults without compromising the overall performance of the system. This includes the development of robust tournament structures and Byzantine-resilient peer-to-peer networks. Another area of focus is the study of rumor spreading and information propagation in dynamic and evolving graphs. Improving the efficiency and scalability of Byzantine agreement protocols under adaptive adversaries is also an active area of research. Notable papers include:

  • A study on tournament robustness via redundancy, which demonstrates a polynomial blow-up in tournament size to tolerate up to a 1/3 fraction of manipulations.
  • A protocol for fully-distributed construction of Byzantine-resilient dynamic peer-to-peer networks, which guarantees the maintenance of a constant degree graph with high expansion under continuous churn and a large number of Byzantine nodes.
  • An improved Byzantine agreement protocol under an adaptive adversary, which runs in O(min{t^2 log n/n, t/log n}) rounds.

Sources

Tournament Robustness via Redundancy

Fully-Distributed Construction of Byzantine-Resilient Dynamic Peer-to-Peer Networks

Rumors on evolving graphs through stationary times

Improved Byzantine Agreement under an Adaptive Adversary

Built with on top of