Complete the proof that the graph BGa (defined in the proof of Theorem 5. 13) is indeed a buffer graph, i. e., for each path P E P there exists a guaranteed path with image P. Show that, as claimed, fb and nb do indeed describe a path in BGa.
Project 5.5 Prove that there exists a deadlock-free controller, for packet switching on a hypercube, which uses only two buffers in each node and allows packets to be routed via minimum-hop paths.
Is it possible to obtain the collection of used paths by means of the interval routing algorithm (Subsection 4.4. 2)? Is it possible to use a linear interval labeling scheme?
Text Book: Introduction to Distributed Algorithms By Gerard Tel.