Time-space trade-offs in population protocols for the majority problem.

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners.

Identifying uniformly mutated segments within repeats.

Given a long string of characters from a constant size alphabet we present an algorithm to determine whether its characters have been generated by a single i.i.d.