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)