- priority inversion
- lower-priority tasks indirectly keeps higher-priority task from running
- performance (latency) problem
- correctness problem (starvation), if system fully loaded
- examples: lower number = higher priority
- example scenario A
- t10 sends to t1, then t5 wants to run
- t1 runs on behalf of t10, so t5 should be able to preempt
- ⇒ adjust server priority to current client's priority

- example scenario B
- t10 runs on behalf of t8, t7 preempts, then t5 wants to send to t10
- t7 keeps t10 from completing its computation, t5 blocked
- ⇒ boost server priority to waiting client's priority

- also: priority-based Send queues?

- abstracted as path-finding to nodes in a graph
- shortest-path routing finds consistent paths without loops
- but is not necessarily
*efficient*, because parallel links might go unused

- but is not necessarily
- Floyd-Warshall Algorithm
- brute-force iteration of links with O(N
^{3}) complexity - ok for dense graphs

- brute-force iteration of links with O(N
- Dijkstra's Algorithm
- less computational overhead for sparse graphs
- notation:

`N`set of nodes `N'`set of 'visited' nodes `c(u,v)`link cost u→v, possibly ∞ `D(u,v)`path cost u→v `P(u,v)`2nd-last hop on path from u→v

- algorithm at Node
`u`N' = { u } D(u,v) = c(u,v) for all neighbours v of u loop: find w not in N' with minimum D(u,w) add w to N' for all v not in N' and adjacent to w: if (D(u,w) + c(w,v) < D(u,v)): D(u,v) = D(u,w) + c(w,v) P(u,v) = w until N' == N

- invariant at step k: N' contains nearest k destinations

→ i.e., the shortest paths to k destinations are known - result: trace previous hops D(u,v) backwards to obtain full path and next hop information
- complexity
- O(N) for 'find w', but heap-sort could reduce to O(log N)
- O(E) for 'for all v'
- O(N) for running the algorithm for all nodes
- worst-case O(N
^{3}), with heap O(N^{2}log N) - sparse graph: E << N (cf. Floyd-Warshall)

- Notes
- 'shortest' is common optimization objective to compute consistent paths without loops
- ... especially important in distributed computation (networking)
- compute routing information only for turnouts?
- build overlay data structure?
- add reversing by adding fake second edge to turnouts used as 'merge' (along with fake cost)
- can compute alternative paths, if marginal cost does not exceed distance of minimum loop
- example taken from Slide 4-83 of Kurose/Ross textbook slides