[Nets-seminars] Talk tomorrow (29th May) 4:00pm GS/302 Damon Wischik
Richard G. Clegg
richard at richardclegg.org
Thu May 28 17:14:53 BST 2009
Tomorrow's talk will be by Damon Wischik from CS.
Complexity theory for distributed algorithms on crummy networks
If "the network is the computer", as John Gage said, then what is the
nature of network computation? It is distributed algorithms, overwhelmingly
made up of short messages, organized into elaborate transactions. For
example, to view your gmail inbox your web browser has to retrieve 66
separate items each of which might take several round trip times; the
arrangement of these 66 items within the web page determines how much the
overall transaction can be sped up by parallelization. The trend is that
messages are becoming ever shorter (compared to processing power and
network bandwidth), and we want ever more complex transactions, but
networks remain limited by the speed of light and by packet drops.
I will propose a new way to analyse the complexity of distributed
algorithms, a "little-o notation" which describes how the performance of an
algorithm depends on latency and packet drop probability and retransmit
timers, asymptotically as packet drop probability decreases to zero. I will
illustrate it by analysing web page downloads, leader election, and
time-synchronization in a sensor network.
--
Richard G. Clegg,
Dept of Elec. Eng.,
University College London
http://www.richardclegg.org/
More information about the Nets-seminars
mailing list