On the Glitch Phenomenon

When I wrote [12], a colleague at Massachusetts Computer Associates pointed out that the concurrent reading and writing of a single register, assumed in the bakery algorithm, requires an arbiter–a device for making a binary decision based on inputs that may be changing. In the early 70s, computer designers rediscovered that it’s impossible to build an arbiter that is guaranteed to reach a decision in a bounded length of time. (This had been realized in the 50s but had been forgotten.) My colleague’s observation led to my interest in the arbiter problem–or “glitch” problem, as it was sometimes called.

The basic proof that an arbiter cannot have a bounded response time uses continuity to demonstrate that, if there are two inputs that can drive a flip-flop into two different states, then there must exist an input that makes the flip-flop hang. At the time, it was very difficult to convince someone that this argument was valid. They seemed to believe that, because a flip-flop has only discrete stable states, continuity doesn’t apply.

I described the arbiter problem to Palais, who had been my de jure thesis adviser and afterwards became a colleague and a friend. He recognized that the correct mathematical way to view what was going on is in terms of the compact-open topology on the space of flip-flop behaviors. So, we wrote this paper to explain why the apparently discontinuous behavior of an arbiter is actually continuous in the appropriate topology.

This paper was rejected by the IEEE Transactions on Computers because the engineers who reviewed it couldn’t understand the mathematics. Six years later, the journal apparently acquired more mathematically sophisticated reviewers, and it published a less general result with a more complicated proof. I believe someone has finally published a paper on the subject that does supersede ours.