In this post we will introduce a series of idempotent semirings that I have created which capture the behaviors of delay tolerant networks. These semirings allow us to use the framework of the algebraic path problem (See the prior post for an introduction to idempotent semirings and the algebraic path problem) to analyze and create routing algorithms for deep space networks and other delay tolerant networks.
Many problems are a hidden instance of what is called the Algebraic Path Problem, a method of turning combinatorial problems into solving linear equations over different “number systems”. In this post we give motivating examples of the algebraic path problem, how to solve it, what an idempotent semiring is, and why we would want to talk about idempotent semirings.