BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic &\; Semantics for Dummies
SUMMARY:Finding our way around routing algebras - Matthew
Daggitt
DTSTART;TZID=Europe/London:20160226T110000
DTEND;TZID=Europe/London:20160226T120000
UID:TALK64867AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/64867
DESCRIPTION:Despite playing a crucial role in almost every par
t of modern technology\, we still do not fully und
erstand the behaviour of routing algorithms and pr
otocols. Typically the difficult questions are avo
ided at undergraduate level by teaching routing al
gorithms in the world of semirings which\, while h
aving nice properties\, don't possess the required
expressibility for useful real world protocols.\n
\nIn this talk I'll outline how any routing proble
m can be viewed from an algebraic perspective and
show how this allows us to better reason about the
ir behaviour. In particular I'll cover the difficu
lties of moving from distributive algebras\, where
everyone in the network agrees on the best paths\
, to non-distributive algebras\, where people disa
gree over which paths should be taken. Finally I'l
l provide a high-level overview of my new\, more g
eneral proof for the convergence of certain classe
s of non-distributive algebras.\n\nCovering:\n\n*
A recap of the Bellman-Ford algorithm (with distri
buted variants)\n* Its behaviour in an idealised w
orld of distributive algebras\n* Why distributive
algebras tend not to be used in practice\n* The co
nvergence properties we can salvage from non-distr
ibutive algebras\n\nPrerequisites:\n\n* Not much.
Basic familiarity with the Bellman-Ford/Dijkstra r
outing algorithms would be a plus\, but not necess
ary!\n
LOCATION:Rainbow Room (FS07)\, Computer Laboratory
CONTACT:Ian Orton
END:VEVENT
END:VCALENDAR