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.
$\begingroup$
$\endgroup$
8
-
$\begingroup$ By non-shared do you mean distributed over asynchronous networks? Or is this distributed-but-synchronously-connected? $\endgroup$– GManNickGCommented Dec 18, 2017 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 causeCommented Dec 20, 2017 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$– GManNickGCommented Dec 20, 2017 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 HendriksCommented Dec 20, 2017 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 causeCommented Dec 20, 2017 at 18:51
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
1$\begingroup$ Thanks for your attempt to answer this question. Please refer internet for understanding Wait-free algorithms and the term consensus number. $\endgroup$ Commented Nov 21, 2017 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$ Commented Dec 18, 2017 at 21:48