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 ...
- 86
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 ...
- 3,290
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 ...
- 5,821
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 ...
- 151
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.
...
- 141
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.♦
- 154k
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 ...
- 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 ...
- 41
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 ...
- 201
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.♦
- 154k
3
votes
What does atomicity mean in distributed systems?
There is one primary meaning of the word "atomicity", and one additional property that some people use on occasion.
The primary meaning is that a complex operation (usually called a "transaction"), ...
- 21.3k
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 ...
- 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 ...
- 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 ...
- 9,461
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 ...
- 141
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.♦
- 154k
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$...
- 2,469
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.♦
- 154k
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 ...
- 163
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 ...
- 1,003
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 ...
- 6,863
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_\...
- 2,356
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.
- 166
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 ...
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 ...
- 111
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". ...
- 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 ...
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 ...
- 9,461
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 ...
- 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 ...
Only top scored, non community-wiki answers of a minimum length are eligible