This is an idea that solved a seemingly intractable problem with mesh-based multi-computers. In the late 80’s and early 90’s folks were experimenting with ways to build large multi-processors using a physical grid as the interconnect – Intel supercomputers use this approach. The idea was that the connection was like city streets laid out on a grid and that the messages would zig-zag around the streets like taxi’s. Many approaches were tried and under heavy traffic they got deadlocked. It was just like in a big city when traffic backs up and blocks an intersection and that that traffic is also blocked by other traffic – we call it “gridlock” when applied to traffic. Many people tried to figure out how to solve this with really complex approaches to the deadlock problem. It was very difficult and very hard to prove that many of these approaches were deadlock-free.