Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States

Dan Alistarh, Rati Gelashvili

Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules. Despite their extreme simplicity, these systems have b…