7 votes
Accepted

Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

The paper says By an easy induction, there exist neighbors $C_0, C_1 \in \mathscr{C}$ such that $D_i = e(C_i)$ is $i$-valent, $i = 0, 1$ Here is a proof: The set of configurations forms the nodes ...
jbapple's user avatar
  • 3,310
7 votes
Accepted

What is the consensus algorithm that requires an odd number of nodes?

To my knowledge there is no quorum-based consensus algorithm that requires an odd number of nodes (processes). That's because such algorithms don't require a majority in the sense that a higher number ...
gdvieira's user avatar
6 votes
Accepted

Algorithm notation

⋃ is the n-ary union operator, similar to how ∑ is the n-ary addition operator. So, in the same way that ∑j someExpressionDependingOnJ means "add the values of all the different instances of ...
Jörg W Mittag's user avatar
5 votes

Why is the commit phase in PBFT necessary?

PBFT is a master piece, for its technical breakthrough and exquisitely precise language. Many descriptions on the protocol details worth reading multiple times to grasp all the nuances. I will: quote ...
Alex Xiong's user avatar
4 votes

What is the consensus algorithm that requires an odd number of nodes?

"Always have an odd number of replica set members" is a common simplification of the MongoDB replica set election process and best practices for deployment, but certainly not a strict requirement. ...
Stennie's user avatar
  • 141
4 votes
Accepted

Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system?

You're right that this is an impossible problem to solve in an asynchronous distributed system, and you're also right that it would solve a lot of problems if we could get a totally ordered clock. But ...
jordojuice's user avatar
4 votes

Consensus protocols in multiplayer video games

Section IX of the following paper proposes a variant of your idea: OpenConflict: preventing real time map hacks in online games. Elie Bursztein, Mike Hamburg, Jocelyn Lagarenne, and Dan Boneh. IEEE ...
D.W.'s user avatar
  • 156k
4 votes
Accepted

Is there a difference between total-ordering consistency and linearizability?

Total, FIFO and causal are all different sequential approaches for ordering the events. Now, consistency applies to all these types ordering and at different levels: local and global. Sequential ...
Andrei's user avatar
  • 362
4 votes

Where does the FLP impossibility proof depend on allowing a single process failure?

The part of the original paper's proof that requires node failure to prove the impossibility is case 2 of lemma 3. This case assumes that there is a "finite deciding run from C0 in which p takes no ...
trungaczne's user avatar
3 votes

Looking for two-way communication/consensus/contract algorithm for use in marriage proposal

If you're feeling up for something particularly geeky, you might enjoy a fair exchange protocol, either one based on gradual release (see e.g., this paper) or one based on Bitcoin (e.g., this). The ...
D.W.'s user avatar
  • 156k
3 votes

Paxos consistency

In your example no client gets a confirmation that the value was written hence the system is in undefined state, but it is consistent with its history. To read a value a client should initiate a new ...
rystsov's user avatar
  • 131
2 votes

Is the consensus number of SetAgree(3, 2) 2 or 1 (proof needed)?

We can prove that 2-set-consensus among 3 processors (noted (3,2)) cannot be used (together with registers) to solve consensus among 2 processors (noted (2,1)) using the Borowsky-Gafni simulation (BG ...
nano's user avatar
  • 166
2 votes
Accepted

Consensus anomaly about read-write registers and test&set

Consensus number and consensus hierarchy are defined in the classic paper "Wait-Free Synchronization" by Maurice Herlihy, 1991. Note the keyword: wait-free. Since you did not give the algorithms for ...
hengxin's user avatar
  • 9,501
2 votes

Paxos made simple -- two details

What exactly is the reason for rule P1? The paper says: We use the customary asynchronous, non-Byzantine model... In other words, it assumes that everything can take an arbitrarily long time to ...
Dave Turner's user avatar
2 votes
Accepted

Are consensus (and atomic broadcast) protocols limited by single node's resources?

Your argument for "no" is flawed, for two reasons: When we say that X reduces to Y, we mean that a solution to Y is one way to solve X. But there might be other ways to solve X that don't rely on ...
D.W.'s user avatar
  • 156k
2 votes

FLP Impossiblity Result assumption of $C_1 = e'(C_0)$

At least in this part of the article, the character C is used for bivalent configurations. The index $0$ for the bivalent $C_0$ was chosen simply because $e(C_0)$ is 0-valent and the index $1$ in $C_1$...
Albert Hendriks's user avatar
2 votes

Paxos Consensus

The basic Paxos protocol (that is, without leader election) is totally asynchronous. In Lamport's paper, the basic protocol is derived from a consistency lemma in section 2.2. However, it does not ...
Curtis F's user avatar
  • 1,003
2 votes
Accepted

Consensus/ranked ordering algorithm

I have both good news, and bad news. Not only is there a way to do it; there are many candidate ways to do it. For instance, you could use IRV, Condorcet voting, Borda count, or many other schemes. ...
D.W.'s user avatar
  • 156k
2 votes
Accepted

How does paxos algorithm handle partial failures of accept messages?

The paper's specification for the phase 2(b) of the algorithm, which is how an acceptor responds to an accept message is the following: If an acceptor receives an accept request for a proposal ...
Dimos's user avatar
  • 163
2 votes
Accepted

Why is a threshold determined for Byzantine Fault Tolerance of an "Asynchronous" network? (where it cannot tolerate even one faulty node)

The answer has to do with tracking the precise assumptions that are made in these different results. In short, while both results assume asynchrony, the "impossibility of distributed consensus with ...
Caleb Stanford's user avatar
2 votes

Algorithm notation

Possibly suitable is also to bring general formal definition of union with respect to indexed family: Suppose we have set $X$, called indices set, and for each $\alpha \in X$ is defined some $U_\...
zkutch's user avatar
  • 2,364
1 vote

Guaranteed existence of a blocking set in the accept definition of Stellar

What is guaranteed is that if a quorum of an intact nodes accepts a statement s, then eventually every intact node v will find itself v-blocked by a set of nodes that has accepted s, i.e. "accept s" ...
nano's user avatar
  • 166
1 vote

Where were the ideas of vote, accept and commit phases originally introduced?

This dates back to the Byzantine broadcast algorithm of Bracha: Bracha, Gabriel. "Asynchronous Byzantine agreement protocols." Information and Computation 75.2 (1987): 130-143.
nano's user avatar
  • 166
1 vote

In the FLP Impossibility paper, why did the authors claim that e is applicable to every E in proof of lemma 3?

The crucial understanding here is the notion applicability of an event in some configuration versus the effect of applying the event to that configuration. If an event e applies to configuration C, it ...
Emil Koutanov's user avatar
1 vote

Impossibility of Distributed Consensus with One Faulty Process

Adding context: If $E_i\in\mathscr C$, let $F_i = e(E_i)\in\mathscr D$. Otherwise, $e$ was applied in reaching $E_i$, and so there exists $F_i \in \mathscr D$ from which $E_i$ is reachable. Of ...
Derek Elkins left SE's user avatar
1 vote

Is it possible to write a wait free leader election algorithm?

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". ...
mpm's user avatar
  • 111
1 vote

Does Paxos consensus algorithm scale linearly?

Apologies if this answer does not belong to this site According to this paper released in 2013 which compares the performance over scale of Paxos and an optimized version of it Fast Paxos Paxos ...
Romantic Electron's user avatar
1 vote
Accepted

Consensus number of memory-to-memory swap

See Theorem 10 (Figure 13) of the paper "Wait-Free Synchronization " by Herlihy, 1991. Theorem 10: An array of registers with memory-to-meory swap has infinite consensus number. Proof: The ...
hengxin's user avatar
  • 9,501
1 vote

Where does the FLP impossibility proof depend on allowing a single process failure?

In the PROOF of LEMMA 2: Now consider some admissible deciding run from $C_0$ in which process p takes no steps, and let u be the associated schedule. The protocol can become deciding ...
Lucien's user avatar
  • 11
1 vote

Where does the FLP impossibility proof depend on allowing a single process failure?

[Well, I am no expert, but here we go.] The assumption of at most a single faulty process is used twice. First, it is used to establish that there is one bivalent starting configuration. (FLP Lemma ...
Martin Frické's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible