3
$\begingroup$

I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously.

Finally I want to know how to derive the consensus number of this algorithm. Googling did not work.

$\endgroup$
  • $\begingroup$ By non-shared do you mean distributed over asynchronous networks? Or is this distributed-but-synchronously-connected? $\endgroup$ – GManNickG Dec 18 '17 at 21:47
  • $\begingroup$ Yes, the communication between nodes is assumed to be asynchronous. Edited my question if people may want this detail. $\endgroup$ – ultimate cause Dec 20 '17 at 4:38
  • 1
    $\begingroup$ So, leader election requires a CP system, which according to CAP can be unavailable in an asynchronous network (meaning no liveness guarantees). I think that alone proves this is impossible. $\endgroup$ – GManNickG Dec 20 '17 at 4:47
  • 1
    $\begingroup$ Getting a distributed network of processors to agree on a common value is impossible in an asynchronous setting: the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility $\endgroup$ – Albert Hendriks Dec 20 '17 at 6:38
  • 1
    $\begingroup$ @Albert Hendriks - I have read this paper, and this paper has added a disclaimer that this paper only presents a theoretical impossibility. While we can have additional assumptions to make things possible. Today in a network of routers we make one of them as leader using asynchronous leader election algorithms. cs.indiana.edu/pub/techreports/TR521.pdf The paper you referred has an important condition of occurrence of a failure. $\endgroup$ – ultimate cause Dec 20 '17 at 18:51
0
$\begingroup$

I believe that leader election derives from consensus algorithm, not other way around. When electing leader you need consensus about who was chosen.

I'm not sure what you understand by "wait free". All communication in distributed system is asynchronous, and you always need to wait for reply.

You could start all nodes with ordered list of all possible leaders. When leader goes down all nodes could just pick next one from the list. But again, to notice that leader goes down you need to ping it, and wait for response. And probably coordinate (create consensus) that we changed a leader (if not, you will have a problem when encountering partitions).

So, last option is to choose one leader at start (trough config) and not allow any change. But this does not fulfills requirements of most distributed system or leader election problem.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your attempt to answer this question. Please refer internet for understanding Wait-free algorithms and the term consensus number. $\endgroup$ – ultimate cause Nov 21 '17 at 9:47
  • $\begingroup$ Just because you have to wait for a reply doesn't mean the system is on an asynchronous network. A synchronous network also has a wait time - it's just that you know with certainty what happened at the end of that wait time. An asynchronous network better models real distributed systems, of course. $\endgroup$ – GManNickG Dec 18 '17 at 21:48

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.