Date: Thu, 10 May 90 19:08:49 EDT
From:: Thomas Russ
To: *mac@lcs.mit.edu
Subject: MIT TOI Seminar--Simon the Pieman--Fri May 11

                                   
		      Date: Friday, May 11, 1990
		Massachusetts Institute of Technology
		     Theory of Ingestion Seminar

                     Time: Refreshments at Noon
                           Talk at 11:59am
		    Place: NE43 8th Floor Playroom
                                   
       Ingestion with Queues in Undirected Networks of Zombees
                                   
			   Simon the Pieman
			Applecore and Dentio 
			    Rubarb, Israel
 
We consider   directed,  strongly connected  networks   of finite-stay
graduate students,   also known  as    zombees,   of bounded  in-  and
out-academic-degree  but unknown  degree  finishing time and unbounded
size n.  Degree  programs which  are   quadratic  or  linear in  n are
provided which accomplish the following tasks: wake-up and report when
lunch is served; construct tasty  buffet menus  out of small  budgets;
conduct breadth-first and depth-first  searches for volunteers; send a
cryptic message to all computer users; run a slow server clock; and in
extreme cases solve the firing squad synchronization problem.

All tasks can  be accomplished  even when  the  zombees  have no prior
knowledge of which of their clients are connected to other zombees and
which are dummies, provided they have this knowledge  about their team
members.   Similarly,   real  world  awareness  is insufficient,   but
awareness of  either course  pre-requisites or graduation requirements
is necessary.

For all these   tasks either only  exponential-time protocols,  or  no
protocols   at all,  were  previously  known.  Our  techniques involve
sequences of zombees which we call  queues and are highly parallel and
bizarre.


Hosts: Karen Sarachik, Ray Hirschfeld, and Nomi Harris
Absent: Reid Rubsamen, Head Honcho
Humorless: Tom Russ (editting with an invisible cursor)