Distributed Elections using Logical Clocks (hints and tips)

I need to implement one of the logical clock algorithms (described here), to allow me to coordinate an election protocol for a distributed system. I'm struggling to work out how I might go about using the clock to enforce a total ordering on a sequence of events in practice. i.e. I don't see a problem in implementing the data structures in practice, but I can't work out how to ensure that my election is not being duplicated elsewhere in the network.

For example, if my 'master' machine goes down, I expect several machines to notice at round about the same time. There will be contention for the 'master' position as several machines try to take it over. My plan is for each machine to broadcast a 'grab the master position' message. Using a logical clock, I should be able to decide what was the globally first machine that sent the message. It will then be acclaimed the master. What I can't work out is how (and where) I will be able to create that ordering over the network messages.

Has anyone out there implemented this sort of algorithm and can offer me some guidance on how I should go about solving the problem?

• Usually, a logical clock does not necessarily give you a total order on the events, only a partial order. In your example, a logical clock algorithm will tell you that the event "master goes down" happened before the event "machine 1 grabs the master position", but the events "machine 1 grabs the master position" and "machine 2 grabs the master position" may be independent of each other and they may have happened in parallel. – Jukka Suomela Sep 16 '10 at 7:58
• Do you really need to implement a logical clock, or is the question, "How can I run a leader election protocol in the presence of failures of type F?" The rephrased question can be attacked a lot of ways. – Aaron Sterling Sep 16 '10 at 16:44
• You're right, perhaps I'm starting with a solution in mind, but that's solely because the referred book claims that one area of applications for logical clocks was in the distributed election, and in providing that ordering of distributed events. – Andrew Matthews Sep 16 '10 at 22:54
• I think googling for fault-tolerant leader election algorithms would be a good starting point. – Jukka Suomela Sep 16 '10 at 23:21
• A randomized consensus algorithm seems like a straightforward solution to code. There's one discussed in section 14.3 of the Attiya and Welch book. If you have $n$ processors and allow for $f$ failures, it will work as long as $n \geq 2f+1$. Not sure if this answers your main question, though. (It does if I understand your question correctly.) – Aaron Sterling Sep 16 '10 at 23:31

Your example mostly needs the machines to agree on a "consensus" for which machine should be the leader. There are a lot of consensus protocols (proven to be correct). On top of consensus (with a proper failure detector) you can construct a "total ordering broadcast". I am no expert in this field so I can't recommend a particular paper but you can pick up one from this google search result http://scholar.google.com/scholar?hl=en&q=total+ordering+broadcast+consensus&btnG=Search&as_sdt=2000&as_ylo=&as_vis=0

• Hi Mohammad, Thanks for your answer, which hopefully is now leading me in the right direction. I've been looking at the Paxos alg (en.wikipedia.org/wiki/Paxos_algorithm), and it also uses a Lamport logical clock, so perhaps we are talking about the same or similar thing? – Andrew Matthews Sep 17 '10 at 0:29
• Paxos is a commit protocol, which is even a stronger tool than consensus, which you don't need for leader election. Your task could be done with a simple version of the consensus based on the failure detector Omega (which is a leader-based failure detector). – Mohammad Alaggan Sep 17 '10 at 1:38

Some answers on the theory that might be useful for you in implementing the problem. A logical clock in general refers to some means of capturing a "happens-before" relation among events in a distributed system. There are specific ways of implementing it-scalar clocks or Lamport clocks as they are known, which is just monotonically increasing counter maintained by each process. But as already pointed out, it only gives us an irreflexive partial ordering. In your case, what you might actually need is a vector clock. A vector clock in essence is each process also maintaining information of timestamps of other processes in the network- a vector of timestamps whose dimension is the number of processes in the system. While it still does not guarantee a total ordering among events, it provides you causal relationships between events clearly which Lamport clocks cannot since 2 events that occur simultaneously get the same timestamp. But you can obtain a total ordering even with lamport clocks by resolving these simultaneous events arbitarily. Some papers that might be useful