Charilaos Efthymiou

Title: On sampling two spin models using the local connective constant

Abstract: This work establishes novel, optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models . These bounds are expressed in terms of the local connective constant of the underlying graph G. This is a notion of "effective degree" of G on a local scale. Our results have some interesting consequences for bounded degree graphs: include the max-degree bounds as a special case, improve on the running time of the FPTAS considered in [Sinclair, Srivastava, Stefankonvic and Yin: PTRF 2017], allow us to obtain mixing bounds in terms of the spectral radius of the adjacency matrix and improve on results in [Hayes: FOCS 2006], We obtain our mixing bounds by utilising the k-non-backtracking matrix H(G,k). This is a very interesting, alas technically intricate, object to work with. We upper bound the spectral radius of the pairwise influence matrix I_G by means of the 2-norm of H(G,k). To our knowledge, obtaining mixing bound using H(G,k) has not been considered before in the literature.

Friedhelm Meyer auf der Heide

Title:  Unifying Gathering Protocols for Swarms of Mobile Robots

Abstract: We survey recent results regarding the Gathering problem in the research area of distributed computing by mobile robots. We assume a simple, standard model of robots: they are point-shaped, live in a d-dimensional Euclidean space, are disoriented (do not agree on common directions or orientations) and have a limited visibility (can only observe other robots up to a constant distance).

The goal of Gathering is to gather all robots at a single, not predefined point. Our focus lies on unifying and extending existing work on gathering in the above model. For this, we derive core properties of protocols that guarantee Gathering and prove runtime bounds that improve upon previous work. We study such strategies for the continuous time model, as well as for the discrete, round-based time model.

Christian Scheideler

Title:  Blockchain Made Lightweight: A Median Rule for State Machine Replication

Abstract: I will present a lightweight solution for state machine replication. Specifically, I show how a simple median rule for the stabilizing consensus problem can be adapted to obtain a low-latency solution for state machine replication. In that solution, the servers only need to maintain the part of the state machine pertaining to uncommitted commands, and clients hold certificates for each committed command. The protocol guarantees liveness as long as DoS attacks on the servers remain below a certain threshold, even if performed by an attacker who is just one round late concerning the latest state of the system, but has the ability to quickly recover after a massive DoS attack.