[Nets-seminars] Talk 29th May 4:00pm GS/302

[Richard G. Clegg]

Next week's talk is by Damon Wischik from computer science.  The title is

"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/