Disobedient John

Dated: 

early 1962

By early 1962, Edsger W. Dijkstra had presented an analogy of a classroom teacher calling upon one of her pupils. By doing so, he had conveyed some subtleties of what we today would call “dynamic memory management” and “concurrent process behavior”. I present the analogy in the following section by translating and paraphrasing part of EWD35 (pp. 3--4).

Dijkstra's Analogy

Information processing often relies on the identification of an object, based on the object's name. This is not unlike a teacher in a classroom who uses the names of her pupils to call upon them. The teacher can for example say “John, come to the blackboard”. This identification process works if the teacher's pupils are obedient and if there is exactly one “John” in the classroom. It moreover works for any classroom size; that is, for any number of pupils. In reality, however, not all pupils instantaneously go to the blackboard when the teacher asks them to. Grabbing John's ear may be necessary to persuade him.

In an old-fashioned school, each pupil has a fixed seat in the classroom. In this setting, the teacher can assign each pupil a unique identification number on the first day of school. Then, during the course of the year, John is not called by name, but by, say, the row and column of his seat in the classroom. Traditional automata work in this à-priori defined sense.

In a modern classroom, each pupil is allowed to choose his (or her) seat on a daily or weekly basis. Here an identification process based on an à-priori defined seating arrangement won't do. To make the teacher's life bearable, we assume that each pupil has his name tagged to his shirt. If, now, the teacher wants disobedient John to go to the blackboard, then she has to search for him. The teacher will work sequentially because she can only read one name tag at a time. The teacher will moreover work systematically: she will have arranged the seats in an orderly fashion, e.g. in terms of rows and columns. To find John, she will iterate through the rows and columns of seats and repeatedly ask herself the question “Are you John?”. On each negative answer, she will proceed to the next seat. This process of finding John works as long as we can guarantee that the pupils do not change their seats while the teacher is searching for John. The two processes “find_Pupil” and “change_Seats” are not allowed to take place simultaneously. For if they do, then this would open up the possibility of John changing seats with someone else right before the teacher passes by his seat.

One could argue that both processes are allowed to execute simultaneously on the condition that the “change_Seats” process is conducted at random moments, instead of at moments that are well chosen by John. In this random setting, the expected time for the teacher to find John remains finite (and, in fact, does not increase). But, those who have studied the “Theory of Computability” know that a potentially non-terminating process isn't very appealing.

Now, even if we may assume that the children solely permute their seats at random moments in time, then there still is a finite probability that the teacher does not find John after having passed by all seats (because John has swapped seats) and that all pupils are seated the way they originally were before the teacher conducted her search for John. This, in turn, opens the door for purely-periodic behavior (of the algorithm) which we of course want to avoid.

Finally, note that even if the teacher is able to find John, then it is still possible that John changes seats with somebody else right after the teacher has found him but right before she grabs his ear. This would result in the wrong person being dragged to the blackboard, a fiasco that we would like to avoid in information processing.

All in all, it is thus crucial that the two processes “find_Pupil” and “change_Seats” do not take place simultaneously. Hence, there is a need for synchronization primitives which is the topic of EWD35.

Final Remarks

The main message here is that Dijkstra was a man of insightful analogies. Other analogies have been documented in previous posts: 1953, 1961, 1972a, 1972b, 1972c.

As an aside, and in the context of my book, it is interesting to note that Dijkstra explicitly referred to “The Theory of Computability” and periodic (non-halting) behavior in particular.

Tags: