<p>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
<a href="http://scholar.google.com/scholar?hl=en&amp;q=total+ordering+broadcast+consensus&amp;btnG=Search&amp;as_sdt=2000&amp;as_ylo=&amp;as_vis=0">http://scholar.google.com/scholar?hl=en&amp;q=total+ordering+broadcast+consensus&amp;btnG=Search&amp;as_sdt=2000&amp;as_ylo=&amp;as_vis=0</a></p>

CC BY-SA 2.5
2010-09-17T00:29:35.273Z
Hi Mohammad, Thanks for your answer, which hopefully is now leading me in the right direction. I've been looking at the Paxos alg (http://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
CC BY-SA 2.5
2010-09-17T01:38:27.323Z
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
CC BY-SA 2.5
2010-09-16T09:54:17.230Z
2010-09-16T09:54:17.230Z
Mohammad Alaggan
<p>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 </p>

<p><a href="http://www.springerlink.com/content/p2mm567706w10315/">http://www.springerlink.com/content/p2mm567706w10315/</a></p>

<p><a href="http://www.cs.washington.edu/homes/arvind/cs425/doc/mattern89virtual.pdf">http://www.cs.washington.edu/homes/arvind/cs425/doc/mattern89virtual.pdf</a></p>

CC BY-SA 2.5
2010-10-27T15:20:08.560Z
Just to clarify, for practical implementation of vector clocks, a partial view of processes in the system will suffice
kryptos
CC BY-SA 2.5
2010-10-27T14:44:40.983Z
2010-10-27T14:44:40.983Z
kryptos
<p>If you need a total message send/receive order, you may want to use a synchronous (time-triggered) protocol. This approach starts with a (fault-tolerant) clock synchronization protocol at the bottom layer, and then executes a message send/receive schedule on top of that. Using this infrastructure, it is trivial to implement consensus algorithms. The distributed time base can also be used to assign globally consistent time-stamps to events throughout the system to recover a global order of events, up to the chosen clock synchronization precision. The book of <a href="http://rads.stackoverflow.com/amzn/click/0792398947">Kopetz (1997)</a> is a good reference for the theoretical aspects. Practical implementations include protocols and industry standards such as FlexRay, TTP, ARINC 659, TTEthernet, ProfiNet IRT, IEEE1588 (PTP).</p>

CC BY-SA 2.5
2010-10-27T20:04:54.477Z
Total order broadcast is equivalent to consensus (if you have one of them, you can implement the other) http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=644722. Without consensus any clock synchronization fails to provide total order, only (consistent) partial order.
Mohammad Alaggan
CC BY-SA 2.5
2010-10-29T08:18:44.077Z
Yes, I agree. Clock synchronization alone cannot establish a total order of time-stamps on events that occur within 3 sync precision intervals. Note, however, that this limitation only applies to the ordering of events generated outside the system. For events generated within the system, according to the schedule with each event scheduled at least 4 precision intervals appart, the total event order can always be established without any higher-level consensus protocol. Chapter 3 of the Kopetz (1997) gives the detailed argument.
Martin Schwarz
CC BY-SA 2.5
2010-10-27T16:18:04.363Z
2010-10-27T16:18:04.363Z
Martin Schwarz
<p>You probably would have better luck with one of the many <a href="http://en.wikipedia.org/wiki/Paxos_algorithm" rel="nofollow">Paxos protocol</a> variants to ensure global progress given 2n+1 machines in the face of n system/link failures. No global clock necessary, just ballots.</p>

CC BY-SA 2.5
2010-10-29T21:25:59.517Z
2010-10-29T21:25:59.517Z
Edward Kmett
<p>I need to implement one of the logical clock algorithms (described <a href="https://rads.stackoverflow.com/amzn/click/com/0521876346" rel="nofollow noreferrer" rel="nofollow noreferrer">here</a>), 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.</p>
<p>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 '<em>grab the master position</em>' 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.</p>
<p>Has anyone out there implemented this sort of algorithm and can offer me some guidance on how I should go about solving the problem?</p>
<p>Thanks in Advance.</p>

CC BY-SA 2.5
2010-09-16T07:58:00.053Z
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
CC BY-SA 2.5
2010-09-16T16:44:08.200Z
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
CC BY-SA 2.5
2010-09-16T22:54:00.037Z
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
CC BY-SA 2.5
2010-09-16T22:54:56.323Z
Is the consensus protocol the preferred solution to this kind of issue?
Andrew Matthews
CC BY-SA 2.5
2010-09-16T23:21:37.653Z
I think googling for fault-tolerant leader election algorithms would be a good starting point.
Jukka Suomela
CC BY-SA 2.5
2010-09-16T23:31:30.883Z
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](http://www.cs.technion.ac.il/~hagit/DC/).  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
<dc.distributed-comp>
Distributed Elections using Logical Clocks (hints and tips)
Andrew Matthews
# Distributed Elections using Logical Clocks (hints and tips)

(Asked by: username_0 on 2010-09-16)

I need to implement one of the logical clock algorithms (described [here](https://rads.stackoverflow.com/amzn/click/com/0521876346)), 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?

Thanks in Advance.

**Tags:** dc.distributed-comp

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_0**: Is the consensus protocol the preferred solution to this kind of issue?  
> **username_1**: I think googling for fault-tolerant leader election algorithms would be a good starting point.  
> **username_2**: 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](http://www.cs.technion.ac.il/~hagit/DC/).  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.)  

---

## 4 answers

### Answer by username_3 on 2010-09-16. Score: 8

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>

> **Comments:**
> **username_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 (http://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?  
> **username_3**: 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).  

---

### Answer by username_4 on 2010-10-27. Score: 8

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

<http://www.springerlink.com/content/p2mm567706w10315/>

<http://www.cs.washington.edu/homes/arvind/cs425/doc/mattern89virtual.pdf>

> **Comments:**
> **username_4**: Just to clarify, for practical implementation of vector clocks, a partial view of processes in the system will suffice  

---

### Answer by username_5 on 2010-10-27. Score: 6

If you need a total message send/receive order, you may want to use a synchronous (time-triggered) protocol. This approach starts with a (fault-tolerant) clock synchronization protocol at the bottom layer, and then executes a message send/receive schedule on top of that. Using this infrastructure, it is trivial to implement consensus algorithms. The distributed time base can also be used to assign globally consistent time-stamps to events throughout the system to recover a global order of events, up to the chosen clock synchronization precision. The book of [Kopetz (1997)](http://rads.stackoverflow.com/amzn/click/0792398947) is a good reference for the theoretical aspects. Practical implementations include protocols and industry standards such as FlexRay, TTP, ARINC 659, TTEthernet, ProfiNet IRT, IEEE1588 (PTP).

> **Comments:**
> **username_3**: Total order broadcast is equivalent to consensus (if you have one of them, you can implement the other) http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=644722. Without consensus any clock synchronization fails to provide total order, only (consistent) partial order.  
> **username_5**: Yes, I agree. Clock synchronization alone cannot establish a total order of time-stamps on events that occur within 3 sync precision intervals. Note, however, that this limitation only applies to the ordering of events generated outside the system. For events generated within the system, according to the schedule with each event scheduled at least 4 precision intervals appart, the total event order can always be established without any higher-level consensus protocol. Chapter 3 of the Kopetz (1997) gives the detailed argument.  

---

### Answer by username_6 on 2010-10-29. Score: 1

You probably would have better luck with one of the many [Paxos protocol](http://en.wikipedia.org/wiki/Paxos_algorithm) variants to ensure global progress given 2n+1 machines in the face of n system/link failures. No global clock necessary, just ballots.


---

