IITDのSanjiva Prasad教授が2018年7月1日より10日間日本に滞在され、本学にて Formal Foundations of Routing in Networks について貴重な講義をしていただきました。また各WPにてmeetingも行われ、とても有意義なものとなりました。
Title: Formal Foundations of Routing in Networks (3 lectures)
Algebraic structures such as semirings have long provided the mathematical basis for framing path-related questions such as connectivity and least-cost paths in communication networks. The presentation will be self-contained in giving a gentle introduction to the necessary algebraic concepts, and the generalisation of simple algorithms.
A long series of work starting from Berge and Carre’ up to recent work by Hoefner & Moeller show that algorithmic solutions to these problems, such as those given by Dijkstra and by Roy/Floyd/Warshall, can be algebraically derived within a framework of cost semirings.
Packet-switching networks additionally require being able to define filters and describe complex sets of paths. The theory of Kleene Algebras with Tests, specialised for networks yields a domain-specific algebraic language (NetKAT of Foster, Kozen, Silva et al.) in which reachability properties of packet switching networks can be expressed and proved (using co-algebraic techniques).
Short movie for lecture by Prof.Prasad