# Tag Info

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

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

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

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

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

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

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

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

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

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

### 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
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. ...
• 156k
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
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,958