6
$\begingroup$

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?

Thanks in Advance.

|cite|improve this question|||||
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela Sep 16 '10 at 7:58
  • 3
    $\begingroup$ 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. $\endgroup$ – Aaron Sterling Sep 16 '10 at 16:44
  • $\begingroup$ 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. $\endgroup$ – Andrew Matthews Sep 16 '10 at 22:54
  • 1
    $\begingroup$ I think googling for fault-tolerant leader election algorithms would be a good starting point. $\endgroup$ – Jukka Suomela Sep 16 '10 at 23:21
  • 5
    $\begingroup$ 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.) $\endgroup$ – Aaron Sterling Sep 16 '10 at 23:31
8
$\begingroup$

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

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Andrew Matthews Sep 17 '10 at 0:29
  • $\begingroup$ 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). $\endgroup$ – M. Alaggan Sep 17 '10 at 1:38
8
$\begingroup$

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

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Just to clarify, for practical implementation of vector clocks, a partial view of processes in the system will suffice $\endgroup$ – kryptos Oct 27 '10 at 15:20
6
$\begingroup$

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) 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).

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Total order broadcast is equivalent to consensus (if you have one of them, you can implement the other) ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=644722. Without consensus any clock synchronization fails to provide total order, only (consistent) partial order. $\endgroup$ – M. Alaggan Oct 27 '10 at 20:04
  • $\begingroup$ 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. $\endgroup$ – Martin Schwarz Oct 29 '10 at 8:18
1
$\begingroup$

You probably would have better luck with one of the many Paxos protocol variants to ensure global progress given 2n+1 machines in the face of n system/link failures. No global clock necessary, just ballots.

|cite|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.