- 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 B
- t11 sends to t10, then t5 preempts
- t5 preempts work done for t1
- ⇒ adjust server priority to current client's priority

- example scenario B
- 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 C
- 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?

- intuition: run sensor querying at highest possible priority
- caveat: track communication is half-duplex
- sensor reports → track commands
- ordering track commands vs. next sensor query?

- repeat speed measurements as kernel testing method
- should see similar measurements

- test reliability of train commands
- speed variation and timing
- change direction and verify using sensors
- add lights on/off to increase command intensity

- 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 P(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)

- example taken from Slide 4-83 of Kurose/Ross textbook slides