Наредни састанак Семинара биће одржан онлајн у среду, 27.априла 2022, од 19-20 часова.
Предавачи: Маријана Лазић, Chair for Foundations of Software Reliability and Theoretical Computer Science at TU Munich
Наслов предавања: A REDUCTION THEOREM FOR RANDOMIZED DISTRIBUTED ALGORITHMS UNDER WEAK ADVERSARIE
Апстракт: 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.
Напомена: Регистрациона форма за учешће је доступна на линку:
https://miteam.mi.sanu.ac.rs/asset/CW5nJWDSEZDj7p32p
Уколико желите само да пратите предавање без могућности активног учешћа, пренос је доступан на линку:
https://miteam.mi.sanu.ac.rs/asset/4LNW8WtML7rLKojoz