An Introduction to Population Protocols

The Paper

An Introduction to Population Protocols (http://www.cs.yale.edu/homes/aspnes/papers/minema-survey.pdf)

Format

We start at 6:10, don't be late!

The discussion lasts for about 1 to 1.5 hours, depending upon the paper.

• Read the paper (done before you arrive)

• Introductions (name, and background)

• First impressions (1-2 minutes this is what I thought)

• Structured review (we move through the paper in order, everyone gets a chance to ask questions, offer comments, and raise concerns)

• Free form discussion

• Nominate and vote on the next paper

• Adjourn for food and/or drink at Campagnollo Upstairs (https://www.facebook.com/CampUpstairs)

Abstract

Population protocols are used as a theoretical model for a collection (or population) of tiny mobile agents that interact with one another to carry out a computation. The agents are identically programmed finite state machines.Input values are initially distributed to the agents, and pairs of agents can exchange state information with other agents when they are close together. The movement pattern of the agents is unpredictable, but subject to some fairness constraints, and computations must eventually converge to the correct output value in any schedule that results from that movement. This framework can be used to model mobile ad hoc networks of tiny devices or collections of molecules undergoing chemical reactions. This chapter surveys results that describe what can be computed in various versions of the population protocol model.

Getting There

Demonware is right near the Main and Terminal Sky Train station, and there is usually street parking available. Enter into the lobby, if no one is there to take you up the elevator, look for a sign and it'll have a contact number you can text to ask to be let up.