Distributed algorithms and computational algorithm design

Title

Distributed algorithms and computational algorithm design

 

Abstract

We discuss how to use computational techniques to develop novel distributed algorithms. That is, how to use computers to find (a) provably correct algorithms or (b) a proof non-existence for certain types of algorithms. This work showcases the use of modern-day SAT solvers which can solve many hard combinatorial problems in practice.

 

As a recent example, we focus on new fault-tolerant algorithms for a certain consensus-like problem. Given a synchronous network of n processors, the processors must all agree which of the communication rounds are even and which are odd. However, we impose two modes of fault-tolerance: the algorithms must be self-stabilising and tolerate Byzantine failures. 

 

We will briefly explore how similar techniques have been applied in the context of deterministic and randomized local algorithms. 

 

The talk should be accessible without any familiarity of SAT solving or distributed algorithms. 

 

About the presenter

Joel Rybicki is a doctoral student in the Local Computation team in the Department of Computer Science, University of Helsinki. The team is part of the New Paradigms in Computing research group at HIIT.