Finding best paths in difficult conditions

Add to your list(s) Download to your calendar using vCal

• Alex Gurney
• Monday 01 November 2010, 12:45-14:00
• Room FW26, Computer Laboratory, William Gates Building.

If you have a question about this talk, please contact Peter Sewell.

(Change of speaker - this replaces Eric's talk)

We know and love shortest-path algorithms. But these only represent the most well-behaved corner of a wide class of methods for finding “good” paths. The current and future Internet gives examples of the remainder of this class, but at the same time, shows that correct solutions can sometimes be obtained even in these adverse conditions.

This talk will present work on the correctness of a best-path algorithm that has the following characteristics:

• Asynchronously safe; tolerant of fair message loss and reordering, but always converging to a unique fixed point.
• Can find multiple best paths for each source-destination pair.
• Allows arbitrary filtering of disallowed paths.
• Allows neighbours to have incompatible preferences (so the fixed point is a Nash equilibrium rather than a global optimum).
• Allows per-adjacency refinements to path preferences.

On the down side, there is no a priori upper bound on execution time without making additional restrictions.

This talk is part of the Semantics Lunch (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Room FW26, Computer Laboratory, William Gates Building
• School of Technology
• Semantics Lunch (Computer Laboratory)
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.