IITDのSanjiva Prasad教授が2018年7月1日より10日間日本に滞在され、本学にて Formal Foundations of Routing in Networks について貴重な講義をしていただきました。また各WPにてmeetingも行われ、とても有意義なものとなりました。

 

Prof.Sanjiva Prasad

Title: Formal Foundations of Routing in Networks (3 lectures)
7月4日、9日 九州大学WEST2-725、826
7月10日 九州大学WEST2-826
講演者:Sanjiva Prasad教授、インド工科大学

Abstracts:
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