Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, November 02, 2017, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Dan Alistarh

Computing with Soup: New Results and Techniques in Population Protocols

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login