Contrasting Peterson’s and Dekker’s algorithms

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 pr

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.

StackExchange Computer Science Q#12621, answer score: 30