# Tag Info

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
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,380

### 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 ...
• 161
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 ...
• 6,150
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

### 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

### 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 ...

### 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 ...
• 160k

### Why is the commit phase in PBFT necessary?

PBFT do need the commit phase to ensure that message m is assigned with sequence number n even during view change. This is because if a message m with sequence number n is committed at some replica ...

### 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
Accepted

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,561

### 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
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 ...
• 160k

### 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,521
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. ...
• 160k
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

### 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,043
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 ...
• 7,088