Stone Age Distributed Computing
Abstract: The discipline of distributed computing --- studying the power and limitations of computation in networks --- is strongly motivated by the thriving Internet age. As such, the traditional models of distributed computing focus mainly on computer-like devices that can exchange large messages with their network neighbors and perform arbitrary local computations.
Recently, there is a trend to apply distributed computing methods to sub-microprocessor networks, e.g., biological cellular networks or man-made nano-networks. However, the suitability of the traditional distributed computing models to these types of networks is questionable: do tiny bio/nano devices ``compute'' and/or ``communicate'' essentially the same as a computer?
In this talk, we introduce a new model that depicts a network of randomized finite state machines operating in an asynchronous environment. Although the computation and communication capabilities of each individual device in the new model are, by design, much weaker than those of a modern computer, we show that some of the most important and extensively studied distributed computing problems can still be solved efficiently.
The talk will be self-contained.