Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There exists no probabilistic (anonymous) leader election algorithm with both, a guaranteed termination and a guaranteed correctness (only one leader). If I remember right, you will find a proof in N. Lynch's book on Distributed Systems. </p> <p>However, there exists algorithms with a probability limit of zero for non-termination for a sufficient long runtime of the algorithm. In addition, the expected runtime is rather short (AFIR, in the order of ln(k) for k initiators). </p> <p>The main idea for such an algorithm follows your second approach. However, do not simple restart the process in case of several leaders, but only allow the winners of the last round to become candidates in the next round. </p> <p><strong>EDIT 1-3:</strong></p> <p>If you asking for a non-anonymous leader election, there are several probabilistic algorithms that guarantees termination. E.g., take a normal ring algorithm and delay messages with with a certain probability, as smaller the ID as greater the chance for delay. In this way, messages with low chance of winning are erased earlier, resulting in less overall messages. </p> <p>If you want to have a different outcome for non-anonymous members, you can e.g. use a two phase algorithm:</p> <ol> <li>Perform a classical leader election => a nodes A with the highest ID wins</li> <li>Let A roll a dice to determine the actual leader. </li> </ol> <p>The element of fortuity could also be distributed:</p> <ol> <li>Any nodes knows the set of identities (S) (if not, use a flooding algorithm to tell)</li> <li>All nodes select by chance an ID of ouf S and send it to any other node</li> <li>The ID that is named most often, wins. If there is more than one such ID, select one of them in a deterministic way, e.g., the median.</li> </ol> <p>Termination and a non-deterministic outcome are granted for both alogrithm. However, the first has a lower average message complexity (<em>n</em> <strong>log</strong> <em>n</em> vs. <em>n²</em> ; the worst case complexity is the same) and is more fair (i.e., the probability that a ID wins is equaly distributed, what is not true for the second algorithm). I'm pretty sure, that at least the last disadvantage can eliminated by a more sophisticated algorithm, but the question here was for the general existence of such an algorithm.</p>
    singulars
    1. This table or related slice is empty.
    1. POIs there a non-deterministic leader election algorithm?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USMatthias
    1. USMatthias
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POIs there a non-deterministic leader election algorithm?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. CODear Matthias, I am not asking for an anonymous leader election algorithm since we can use the process ID information part. Maybe I should clarify what I mean with a nondeterministic program. A non-deterministic program is a program that given the same input every time, can show different executions and thus give different results. Furthermore I think what you describe here is a probabilistic algorithm and I'm wondering how it can guarantee termination... Thanks for your reply though!
      singulars
      1. PO
      1. USSnowflake
    2. CO@Snowflake: Please, see my (additional) edit.
      singulars
      1. PO
      1. USMatthias
    3. CODear Matthias, I indeed also thought about a two phase algorithm. However it kind of seems pointless choosing "the actual leader" again in my opinion though. Are there alternatives?
      singulars
      1. PO
      1. USSnowflake
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload