Advances in Distributed Computing and Governance

The field of distributed computing is moving towards incorporating predictions and probabilistic advice to improve the efficiency and robustness of consensus protocols and resource allocation algorithms. Recent research has shown that leveraging predictions can help optimize the time complexity of Byzantine Agreement protocols, while also improving the fairness and governance of decentralized digital communities. Additionally, there is a growing interest in applying epistemic tests to decentralized governance methods to evaluate their ability to reach correct outcomes. Noteworthy papers in this area include:

  • Byzantine Agreement with Predictions, which presents new algorithms that leverage predictions to yield better time complexity.
  • Single-Sample and Robust Online Resource Allocation, which introduces an Exponential Pricing algorithm that requires only a single sample from each request distribution to achieve a near-optimal solution.
  • With a Little Help From My Friends, which demonstrates the usefulness of distributional advice in algorithm design for online problems.

Sources

Byzantine Agreement with Predictions

Grassroots Democratic Federation: Fair Governance of Large-Scale, Decentralized, Sovereign Digital Communities

Model Checking and Synthesis for Optimal Use of Knowledge in Consensus Protocols

Adaptive Bidding Policies for First-Price Auctions with Budget Constraints under Non-stationarity

Single-Sample and Robust Online Resource Allocation

Delegation and Participation in Decentralized Governance: An Epistemic View

With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design

Built with on top of