Seminar iz veštačke inteligencije, 27. april 2022.

Naredni sastanak Seminara biće održan onlajn u sredu, 27. aprila 2022, od 19-20 časova.

Predavači: Marijana Lazić, Chair for Foundations of Software Reliability and Theoretical Computer Science at TU Munich

Naslov predavanja: A REDUCTION THEOREM FOR RANDOMIZED DISTRIBUTED ALGORITHMS UNDER WEAK ADVERSARIE

Apstrakt:
Weak adversaries are a way to model the uncertainty due to asynchrony in randomized distributed algorithms. They are a standard notion in correctness proofs for distributed algorithms, and express the property that the adversary (scheduler), which has to decide which messages to deliver to which process, has no means of inferring the outcome of random choices, and the content of the messages.

In this talk, we introduce a model for randomized distributed algorithms that allows us to formalize the notion of weak adversaries. It applies to randomized distributed algorithms that proceed in rounds and are tolerant to process failures. For this wide class of algorithms, we prove that for verification purposes, the class of weak adversaries can be restricted to simple ones, so-called round-rigid adversaries, that keep the processes tightly synchronized. As recently a verification method for round-rigid adversaries has been introduced, our new reduction theorem paves the way to the parameterized verification of randomized distributed algorithms under the more realistic weak adversaries.

Napomena: Registraciona forma za učešće je dostupna na linku:
https://miteam.mi.sanu.ac.rs/asset/CW5nJWDSEZDj7p32p

Ukoliko želite samo da pratite predavanje bez mogućnosti aktivnog učešća, prenos je dostupan na linku:
https://miteam.mi.sanu.ac.rs/asset/4LNW8WtML7rLKojoz



Nažalost nije moguće ostaviti komentar.