17

Just to make sure we are on the same page, first let us consider these three definitions: Definition. Test-and-set is a read-modify-write instruction on some binary register (let's just say that 0 and 1 are possible values) where a thread obtains the old value and writes 1. Definition. Consensus is reached between $n$ threads iff all $n$ threads decide on ...


7

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 of processes accept a value. A majority in these algorithms means that at least $N / 2 + 1$ processes accept a value, where $N$ is the total number of ...


6

The wikipedia article does have a reference that answers you question, but perhaps you don't want to read that 26 page paper. I'll give a simplified version of the (quite technical) proof, showing that test-and-set can not solve binary consensus for 3 processes. This kind of argument is widely used in proving consensus numbers. Let's suppose we have a ...


4

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 the original paper (some math notation expressed in Latex, I will use pseudo code instead) add on my understanding/interpretation. Q&A myself important ...


4

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 steps". p taking no step means it has died/failed. From case 1 of lemma 3, we know that there exists a pair of messages, called e and e' which affect the ...


4

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 of a multidigraph in which the edges are labelled by events. $\mathscr{C}$ is the set of nodes reachable in any number of steps from $C$ while not following ...


4

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 it only solves "all" our problems if the clock has the additional constraint of a meaningful relationship with real time. The two best solutions we have are ...


4

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 Security & Privacy 2011. The difference is that they propose that detection can be done by the central server, after the fact, by analyzing all of a ...


3

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 number of steps is very large though! Probably not suitable to carry out by hand. You could try a simpler protocol: Alice picks a message $m_A$, computes a ...


3

Let $A,B,C$ be the first, second and third majorities. If there are $M$ players, we can think of $A,B,C$ as subsets of $[M] = \{1,\ldots,M\}$ satisfying $|A|,|B|,|C|>M/2$. If $A,B$ were disjoint then $|A \cup B| = |A| + |B| > M$, which contradicts $A \cup B \subseteq [M]$; that's why two majorities always have an acceptor in common. If $C$ intersects ...


3

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 consistency requires that all of the operations appear to have executed atomically in some sequential order that is consistent with the order seen at a local level (...


3

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 round of Paxos. The main result of the "Paxos made simple" is that if a value was reported as chosen then any further rounds of Paxos will propose the same value....


2

This paper [1] provides a consensus algorithm in a model where, in each round, each node can query 2 randomly chosen nodes and update its own value accordingly. As this is essentially a balls-into-bins scenario, the load balancing will be very good. It is shown that this "converges" to a consensus within $O(\log n)$ rounds even if an omniscient adversary ...


2

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 simulation for short). The BG simulation allows 3 processors using registers only to simulate any algorithm in which 2 processors use registers and (3,2). ...


2

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 test&set using read/write registers only, I guess that they are not wait-free. (They may be lock-free instead.) Added: After the discussions with the OP ...


2

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 happen, but no messages are corrupted in transit and all agents obey the protocol. What this means is that it would be perfectly fine to write the timeout-based ...


2

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 solving Y. Some protocols for consensus elect a leader, but that doesn't necessarily imply that all approaches to solve consensus require electing a leader. (For ...


2

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 guarantee progress (section 2): A restricted version of the preliminary protocol provided the basic protocol that guaranteed consistency, but not progress. (...


2

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"), which requires multiple parties to take action, either happens or doesn't happen. It can't happen only in part. One classic example (because this is one domain ...


2

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. See https://en.wikipedia.org/wiki/Ranked_voting and https://en.wikipedia.org/wiki/Social_choice_theory. Unfortunately, there are also negative results showing ...


1

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 numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n. This means that acceptors are allowed ...


1

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 course, without the definitions of $E_i$, $e$, $\mathscr C$, and $\mathscr D$, this isn't much use either. We're given a configuration $C$. $e$ is by assumption ...


1

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$ was chosen because $e(C_1)$ is 1-valent, even though $C_0$ and $C_1$ are bivalent neighbors (when applying $e'$).


1

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". All communication in distributed system is asynchronous, and you always need to wait for reply. You could start all nodes with ordered list of all possible ...


1

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 and Fast Paxos are optimal consensus algorithms that are simple and elegant, while suitable for efficient implementation Reading further section 3.4. Scale Up , ...


1

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 protocol is shown in Figure 13. The processes share an array of registers $a[1 \ldots n]$ whose elements are initialized to $0$ and a single register $r$, ...


1

[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 2) [Assume not. Then all starting configurations are monovalent, and by the need to avoid triviality, at least one must be 0-valent and at least one must be 1-...


1

"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. The main requirement to elect (and sustain) a primary in a MongoDB replica set is a healthy majority of configured voting members able to communicate with each ...


1

At a high level, you are considering consistency models (@wiki) in distributed systems, like a distributed replicated data store in your example. Consistency models specify what values may be returned by a read given that memory operations may only be partially ordered. Note that this has imposed restrictions on the order in which all the operations are ...


1

The notion of perfection in consensus: Tangaroa is a BFT flavored Raft usually consisting of 3 - 5 systems in a cluster and can tolerate failure of up to 1/2 of the node count with a concept of "randomization in election of leadership". PBFT is the "practical" BFT system designed for more deterministic behavior with a concept of "eventual leadership". ...


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