patternMinor
Applications of Lamport's Distributed Mutual Exclusion algorithm
Viewed 0 times
lamportexclusionapplicationsalgorithmdistributedmutual
Problem
I'm trying to understand the relevance of the Lamport distributed mutual exclusion algorithm (or any of its variants), where a group of processes cooperate to gain exclusive access to a resource without relying on a centralized coordinator.
How can this be useful in practice? For instance, if the resource is something like a printer, or a shared file system, it can enforce mutual exclusion on its own, so there is no need for a distributed algorithm. I can't think of an example where this wouldn't be the case. What am I missing?
How can this be useful in practice? For instance, if the resource is something like a printer, or a shared file system, it can enforce mutual exclusion on its own, so there is no need for a distributed algorithm. I can't think of an example where this wouldn't be the case. What am I missing?
Solution
Lamport introduced his distributed mutual exclusion algorithm as an example in
Lamport, Leslie: Time, Clocks and the Ordering of Events in a Distributed System, Communications of the ACM, 21(7):558-565, 1978.
The link leads to Lamport's personal page, where he has an annotated bibliography of all his work, with PDFs of every paper that has an electronic version.
The paper in question is the one that introduced Lamport timestamps and Lamport clocks. Here's what Lamport has to say about the distributed mutual exclusion algorithm:
It didn't take me long to realize that an algorithm for totally ordering events could be used to implement any distributed system. A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system. So, I wrote this paper, which is about how to implement an arbitrary distributed state machine. As an illustration, I used the simplest example of a distributed system I could think of--a distributed mutual exclusion algorithm.
The relevance is not that you would use it to protect some kind of centralized resource. The relevance is rather to show that when you are implementing a distributed state machine, you can actually get all the participants to agree about something, so you don't need centralized resources.
Lamport, Leslie: Time, Clocks and the Ordering of Events in a Distributed System, Communications of the ACM, 21(7):558-565, 1978.
The link leads to Lamport's personal page, where he has an annotated bibliography of all his work, with PDFs of every paper that has an electronic version.
The paper in question is the one that introduced Lamport timestamps and Lamport clocks. Here's what Lamport has to say about the distributed mutual exclusion algorithm:
It didn't take me long to realize that an algorithm for totally ordering events could be used to implement any distributed system. A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system. So, I wrote this paper, which is about how to implement an arbitrary distributed state machine. As an illustration, I used the simplest example of a distributed system I could think of--a distributed mutual exclusion algorithm.
The relevance is not that you would use it to protect some kind of centralized resource. The relevance is rather to show that when you are implementing a distributed state machine, you can actually get all the participants to agree about something, so you don't need centralized resources.
Context
StackExchange Computer Science Q#39555, answer score: 5
Revisions (0)
No revisions yet.