Filed under: Uncategorized | Tags: distributed algorithms, golden ratio, security, theory
I’ll be giving two talks at the upcoming SIROCCO. The first is a keynote on how to ensure security in systems where nodes can come and leave at will, with no admission control. The second is a paper that won the best paper award; it is on robust, distributed search, and makes use of the golden ratio in an interesting way.
Anyone who registers can participate in the livestream of the talk, and the organizers of SIROCCO have made registration free this year. Below are links to talk times and registration information .
Talk abstracts are below:
Resource Burning for Permissionless Systems (Monday, June 29th, 6-7pm CEST)
Proof-of-work puzzles and CAPTCHAS consume enormous amounts of energy and time. These techniques are examples of resource burning: verifiable consumption of resources solely to convey information.
Can these costs be eliminated? It seems unlikely, since resource burning shares similarities with “money burning" and “costly signaling”, which are concepts foundational to game theory, biology, and economics. Can these costs be reduced? Yes, research shows we can significantly reduce asymptotic costs of resource burning in disparate domains.
In this talk, we survey the literature on resource burning; take positions based on predictions of how the technique is likely to evolve; and propose several open problems targeted at the theoretical distributed-computing research community.
ANTS on a Plane (Wednesday, July 1st, 7:00-7:30 pm CEST)
In the ANTS (Ants Nearby Treasure Search) problem, multiple searchers, starting from a central location, search for a target. The searchers cannot communicate and have few bits of initial knowledge, called advice, when they begin the search. In this paper, we initiate the study of ANTS in the geometric plane.
Our main result is an algorithm, GoldenFA, that tolerates arbitrarily many crash failures caused by an adaptive adversary, and requires no bits of advice. GoldenFA takes 
We complement our algorithm with a lower bound, showing that it is within logarithmic factors of optimal. Additionally, we empirically test GoldenFA and a related heuristic, and find that the heuristic is consistently faster than the state-of-the-art. Our algorithms and analysis make critical use of the golden ratio.
Leave a Comment so far
Leave a comment
Machinations 