0 Replies - 997 Views - Last Post: 23 August 2013 - 09:00 PM

#1 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3534
  • View blog
  • Posts: 10,940
  • Joined: 05-May 12

Lamport's Bakery Algorithm on a distributed system

Posted 23 August 2013 - 09:00 PM

I've spent of the day considering how to implement Lamport's Bakery Algorithm on a distributed system, but I'm stuck because of some of the constraints I'm dealing with. The primary constraint is that I have no locking primitives available to me. The secondary one is that I don't know how many "processes" will be participating ahead of time and the "processes" may terminate at any given time. A tertiary constraint is that I can only use the storage medium for communication between "processes".

My objective is to maintain a durable priority queue in a storage medium that has no locking mechanism. (Although the storage medium itself is actually backed by a database, I'm not allowed to interact with the database directly. Yes, asinine, I know. If I could I wouldn't be trying to implement my own mutex.) I may have one or more "producers" that can write into the queue, and one or more "consumers" trying to perform an operation based on the item at the head of the queue. Once the operation completes will the item be removed from the queue. No other "consumer" must do the same operation in parallel. Should the operation not be completed, due to "process" crashes or user initiated terminations, the operation should be retried the next time a "consumer" comes back online. I figured I'd tackle issue of retrying later by using the same strategy used by databases to by replaying its logs.)

Some of the things I've already considered:
- Lamport's Distributed Mutual Exclusion Algorithm. Again I don't know how many "nodes" there are to send the requests to, and I can be left hanging with "nodes" just terminating effectively randomly.
- Lock free queues. On the plus side, I don't have to know how many producers/consumers. On the downside, all the literature I've run across requires atomic primitives like compare&swap.
- Use Windows Workflow Foundation, implement my own persistent service, and assume that WWF's calls to my custom persistence services knows how to handle potentially colliding writes into the common durable storage medium.

It's possible, I maybe too fixated on using Lamport's Bakery Algorithm because of the little jewel floating before my eyes by Lamport's reflections about his algorithm:

Quote

What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion.


Is This A Good Question/Topic? 1
  • +

Page 1 of 1