2 Replies - 693 Views - Last Post: 27 March 2018 - 03:43 AM

#1 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7056
  • View blog
  • Posts: 23,986
  • Joined: 05-May 12

Black-White Bakery Algorithm

Posted 23 March 2018 - 11:14 AM

I stumbled across this while I was reviewing my understanding of Lamport's Bakery Algorithm:
Black-White Bakery Algorithm

Here's the text of the abstract which makes this interesting (at least to me):

Quote

A mutual exclusion algorithm is presented that has four desired properties: (1) it satisfies FIFO fairness, (2) it satisfies localspinning, (3) it is adaptive, and (4) it uses finite number of bounded size atomic registers. No previously published algorithm satisfies all these properties. In fact, it is the first algorithm (using only atomic registers) which satisfies both FIFO and local-spinning, and it is the first bounded space algorithm which satisfies both FIFO and adaptivity.

All the algorithms presented are based on Lamportís famous Bakery algorithm [27], which satisfies FIFO, but uses unbounded size registers (and does not satisfy local-spinning and is not adaptive). Using only one additional shared bit, we bound the amount of space required by the Bakery algorithm by coloring the tickets taken in the Bakery algorithm. The resulting Black-White Bakery algorithm preserves the simplicity and elegance of the original algorithm, satisfies FIFO and uses finite number of bounded size registers. Then, in a sequence of steps (which preserve simplicity and elegance) we modify the new algorithm so that it is also
adaptive to point contention and satisfies local-spinning.


Is This A Good Question/Topic? 3
  • +

Replies To: Black-White Bakery Algorithm

#2 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7056
  • View blog
  • Posts: 23,986
  • Joined: 05-May 12

Re: Black-White Bakery Algorithm

Posted 25 March 2018 - 09:46 AM

I'm still working my way through the paper and trying to convince myself that the local spinning variant is actually safe. In the back of my mind, I'm feeling like there is some kind of hand waving that is happening, but it maybe simple that I've not yet grokked the local spinning variant. Admittedly, I've just skimmed over his theorems. Those maybe my starting point.
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7056
  • View blog
  • Posts: 23,986
  • Joined: 05-May 12

Re: Black-White Bakery Algorithm

Posted 27 March 2018 - 03:43 AM

I put my finger on what was confusing me: I needed to be convinced that claim that only some of the variables had to be initialized and everything else could be left uninitialized was true.

I also figured out what was I felt like was a lot of hand-waving: The arrays spin.ch[i,j] and spin.nu[i,j]. The claim is that processes spin locally on these arrays, but somehow process j can remotely update the those arrays on process i.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1