Stanford Lecture: "Aha" Sessions  Problem 4  Distributed stability Part 3  Summary and Q&A
TL;DR
Dijkstra's construction proves that in certain cases, at least one processor must be able to move in every configuration, with implications for the use of twostate processors.
Questions & Answers
Q: What is the key requirement for every configuration based on Dijkstra's analysis?
In every configuration, at least one processor must be able to move.
Q: How does Dijkstra prove that in some cases, there can be infinite cycles of bad moves?
Dijkstra presents an example where only one processor can move based on the states of its neighbors, leading to a situation where there are infinite cycles of bad moves.
Q: What is the tradeoff mentioned by Dijkstra when defining moves?
The tradeoff is between restricting moves and defining enough moves to ensure there is always a way to move. Giving up the restriction may allow for finding configurations with no infinite cycles, but it also makes it harder to define moves in every situation.
Q: What is the significance of the example presented by Dijkstra?
The example demonstrates the need to always have at least one processor that can move in every configuration, as without it, there can be infinite cycles of bad moves.
Summary & Key Takeaways

Dijkstra highlights the need to emphasize the requirement that at least one processor can always move in every configuration.

He discusses the tradeoff between restricting moves and defining enough moves to ensure there is always a way to move.

He presents an example where the first processor can move based on the states of its neighbors, proving that in some cases, it is possible to have infinite cycles of bad moves.