University of Cambridge > > Semantics Lunch (Computer Laboratory) > Finding best paths in difficult conditions

Finding best paths in difficult conditions

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity