Contrasting Peterson’s and Dekker’s algorithms

Question

I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries.

I tried to formulate the algorithms in informal language like follows:

Peterson's: "I want to enter."                 flag[0]=true;
            "You can enter next."              turn=1;
            "If you want to enter and          while(flag[1]==true&&turn==1){
            it's your turn I'll wait."         }
            Else: Enter CS!                    // CS
            "I don't want to enter any more."  flag[0]=false;

Dekker's:   "I want to enter."                 flag[0]=true;
            "If you want to enter              while(flag[1]==true){
             and if it's your turn               if(turn!=0){
             I don't want to enter any more."      flag[0]=false;
            "If it's your turn                     while(turn!=0){
             I'll wait."                           }
            "I want to enter."                     flag[0]=true;
                                                 }
                                               }
            Enter CS!                          // CS
            "You can enter next."              turn=1;
            "I don't want to enter any more."  flag[0]=false;

The difference seems to be the point where "You can enter next." occurs and the fact that "if it's your turn I don't want to enter any more." occurs in Dekker's.

In Peterson's algorithm, the two processes seem to be dominant. A process seems to force his way in into the critical section unless it's the other one's turn.

Conversely, in Dekker's algorithm, the two processes seem to be submissive and polite. If both processes want to enter the critical section, and it's the other one's turn, the process decides to no longer want to enter. (Is this needed for starvation-freedom? Why?)

How exactly do these algorithms differ? I imagine that when both processes try to enter the critical section, in Peterson's, the process says "I enter", while in Dekker's the process says "You may enter". Can someone clear up the way the processes behave in each algorithm? Is my way of putting it in informal terms correct?

Answer 1

Your informal descriptions of the algorithms is wonderful.

I think in both cases the author was trying to come up with the simplest solution they could think of that guaranteed both mutual exclusion and deadlock freedom. Neither algorithm is starvation free or fair.[ed: as pointed out in the comments, both algorithms are starvation free, and Peterson's algorithm is also fair]. Dekker's solution was the first mutual exclusion algorithm using just load and store instructions. It was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., Programming Languages: NATO Advanced Study Institute, pp. 43-112, Academic Press, 1968. If you read through the paper you see Dijkstra work through a number of attempts, recognizing the problem with each, and then adding a little bit more for the next version. Part of the inefficiency of his algorithm comes from the fact that he starts with a turn-taking algorithm and then tries to modify it to allow the processes to progress in any order. (Not just 0,1,0,1,...)

Peterson's algorithm was published in 1981, after more than a decade of experience and hindsight about Dekker's algorithm. Peterson wanted a much simpler algorithm than Dekker so that the proof of correctness is much easier. You can see that he was feeling some frustration with the community from the title of his paper. Peterson, G.L.; "Myths about the mutual exclusion problem," Inf. Proc. Lett., 12(3): 115-116, 1981. Very quick read and very well written. (And the snide remarks about formal methods are priceless.) Peterson's paper also discusses the process by which he built his solution from simpler attempts. (Since his solution is simpler, it required fewer intermediate steps.) Note that the main difference (what you call "dominance" rather than "submissiveness") is that because Peterson started out fresh (not from the turn-taking algorithm Dijkstra started with) his wait loop is simpler and more efficient. He realizes that he can just get away with simple looped testing while Dijkstra had to backoff and retry each time.

I feel I must also mention Lamport's classic Bakery algorithm paper: Lamport, Leslie; "A New Solution of Dijkstra's Concurrent Programming Problem", Comm ACM 17(8):453-455, 1974. The Bakery algorithm is arguably simpler than Dekker's algorithm (and certainly simpler in the case of more than 2 processors), and is specifically designed to be fault tolerant. I specifically mention it for two reasons. First, because it gives a little bit of history about the definition of the mutual exclusion problem and attempts to solve it up to 1974. Second because the Bakery algorithm demonstrates that no hardware atomicity is required to solve the mutual exclusion problem. Reads that overlap writes to the same location can return any value and the algorithm still works.

Finally, a particular favorite of mine is Lamport, Leslie; "A Fast Mutual Exclusion Algorithm," ACM Trans. Comp. Sys., 5(1):1-11, 1987. In this paper Lamport was trying to optimize a solution to the mutual exclusion problem in the (common) case that there is little contention for the critical section. Again, it guarantees mutual exclusion and deadlock freedom, but not fairness. It is (I believe) the first mutual exclusion algorithm using only normal reads and writes that can synchronize N processors in O(1) time when there is no contention. (When there is contention, it falls back on an O(N) test.) He gives an informal demonstration that the best you can do in the contention free case is seven memory accesses. (Dekker and Peterson both do it with 4, but they can only handle 2 processors, when you extend their algorithms to N they have to add an extra O(N) accesses.)

In all: I'd say Dekker's algorithm itself is interesting mainly from a historical perspective. Dijkstra's paper explained the importance of the mutual exclusion problem, and demonstrated that it could be solved. But with many years of hindsight simpler (and more efficient) solutions than Dekker's have been found.

Answer 2

In the following paper we give formal models for Peterson’s and Dekker’s algorithms (and some others) and we used model checker to prove their properties. Please, find our results in the table below (columns "Deadlock" and "Divergent" refer to our models, "ME" = TRUE means that the algorithm is correct, "Overtaking" = TRUE means that it is fair).

R. Meolic, T. Kapus, Z. Brezočnik. ACTLW - An Action-based Computation Tree Logic With Unless Operator. Information Sciences, 178(6), pp. 1542-1557, 2008.

https://doi.org/10.1016/j.ins.2007.10.023

Answer 3

Peterson algorithm has a more strict pressure on entering the critical section, where as dekker's algorithm is relatively softer and less aggressive. To make it more clear, let's check out an example about iranian culture. Before getting into this example, it's good to know that iranian people have a real soft behavior to each other while entering somewhere! Guess two iranian men are going to enter a house, and that house has only one door to enter.

Now imagine two men from another culture(Zombian Culture) which they don't actually care too much about each other while entering somewhere(It's a matter of respect to ask someone whether he wants to enter or not).

To clarify the information about the problem we can say that:

• Two Iranians = Two processes using the Dekker algorithm
• Two Zombians = Two processes using the Peterson algorithm

So let's find out what's done in each algorithm(culture). The following comments are for the first Iranian man who is going to enter the house while using the Dekker algorithm:

p0:
   wants_to_enter[0] ← true // Goes through the house entrance
   while wants_to_enter[1] { // If the other man wants to enter too
      if turn ≠ 0 { // Then see if it is your turn or not
         wants_to_enter[0] ← false // If it is not your turn don't go furthur
         while turn ≠ 0 { // and wait until it is your turn
           // busy wait
         }
         wants_to_enter[0] ← true // when it is your turn go through the door
      }
   }

   // critical section
   ...
   turn ← 1
   wants_to_enter[0] ← false // Set the turn for the other man
   // remainder section

We have also two Zombians which are going to enter the house using the Peterson algorithm. This one goes as follows:

P0:     
  flag[0] = true; // Goes through the house entrance
  turn = 1; // Set the turn for himself
  while (flag[1] && turn == 1) // Wait until the other one is going in
  {
   // busy wait
  }
   // critical section
      ...
   // end of critical section
  flag[0] = false; // Done going inside

It's important to mention that both of them are not going inside while the other one is doing so(Mutual Exlusion) but, Iranian people are much more softer.