Deadlock In Traffic

No, I'm not talking about deadlocks resulting from high traffic on an IIS server.  I'm talking about a real-world physical deadlock involving cars that I've been part of today.  I didn't even need Wait Chain Traversal - it was the perfect visualization, quotable for books and articles.

It was one of the most amusing things I've ever seen.  Consider the two-way (right-hand driving) street depicted in the diagram.  Car A has just emerged from a parking lot on the right hand side, and is waiting for the left lane of cars to clear.  Car B has simultaneously emerged from a parking lot on the left hand side, and is waiting for the right lane of cars to clear.

Analyzing the situation with standard wait-chain algorithms, we obtain the following sequence: The cars in the left lane can't make any progress until car B moves; car B can't move until the cars in the right lane move; the cars in the right lane can't move until car A moves; car A can't move until the cars in the left lane move - here's our deadlock.

I was in one of the cars in the right lane, and immediately realized this was a deadlock.  It took several minutes to resolve - the typical Israeli driver won't back out of a lane once he has managed to squeeze into it, and it takes a critical mass of yelling and horn-blowing until progress is made.  Note that behind cars A and B there was an additional row of cars trying to get out of the parking lots, so it wasn't really trivial to resolve the deadlock without multiple cars backing out of the way.

Considering that this scenario took place at 6:15PM on Ha-Barzel street in Tel-Aviv, an industrial area with a dense concentration of hi-tech companies, I wonder how many of the other drivers have realized this is a deadlock, and how many of them are recording this thought on their very own blog as we speak.  :-)