Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 02, 2017, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Dan Alistarh
Population protocols are a model of distributed computing, in which n agents with limited local state interact randomly, cooperating to collectively compute global predicates. An extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model, while applied work has shown that these algorithms can be actually implemented using synthetic DNA molecules.
This talk will serve as a brief survey of recent results in this area, focusing on the use of probabilistic and combinatorial techniques, in the context of a fundamental task called majority. Majority (consensus) requires agents to collectively reach a decision as to which one of two states initial states A or B had a higher initial count. Two complexity metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires. We will discuss recent results which almost tightly characterize the space-time trade-offs when solving majority in population protocols.
Based in part on joint work with James Aspnes and Rati Gelashvili, to appear in SODA18.
Automatic MiSe System Software Version 1.4803M | admin login