IITDのSanjiva Prasad教授が本学にてFormal Foundations of Routing in Networksの講義をされました。
Title: Formal Foundations of Routing in Networks (3 lectures)
Title :Formal Foundations of Routing in Networks 2018 Lectures 4-9 July 2018
Title :Formal Foundations of Routing in Networks Kyushu University Lectures 4-10 July 2018
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