Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [consensus]

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. use this tag for consensus kind of problem.

3
votes
0answers
37 views

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

The paper is available here: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf The 1st paragraph of lemma 3's proof says In other words,if event e is applicable to config C,and E is any ...
0
votes
0answers
38 views

Under which conditions is it possible to scale a distributed log with checksums?

This question is related to Amazon's QLDB, but my question is about the generic architecture of such a software system. The question arises from the fact that Amazon advertises the service as "highly ...
0
votes
0answers
22 views

Does Cassandra provide strong consistency?

Cassandra is claiming to provide strong consistency, making use of the idea of read/write quorums, as presented in the Dynamo paper. More concretely, the claim is that if for a specific item: N is ...
0
votes
1answer
49 views

Paxos Consensus

how does Paxos Consensus algorithm behave in an asynchronous environment? Because as far as I know Paxos only work in synchronous environment. Correct me if I am wrong :) Sorry for the noob question,...
2
votes
0answers
43 views

Why is a primary node needed in pBFT algorithm for consensus?

Why is primary needed in pBFT algo? Since many issues of viewchange etc. come up because primary may be faulty - is it possible to have a version of pBFT which doesn't have nodes assigned as primary? ...
2
votes
0answers
51 views

Byzantine generals (n=3, m=1)

Leslie Lamport describes a algorithm to come to consensus for the case for n>3*m, there m is the number of traitors in ...
1
vote
0answers
22 views

Can someone clarify Invariant 4.7 of the PBFT correctness proof paper?

I am reading the PBFT Correctness Proof Paper and I cannot make completely sense of the Invariant 4.7 and its proof: Here are my concerns: I assume that the symbol $\Leftrightarrow$ is used with the ...
3
votes
1answer
92 views

Impossibility of Distributed Consensus with One Faulty Process

I'm reading Fischer et al.'s Impossibility of Distributed Consensus with One Faulty Process, and I don't quite follow 2 points: The first is in the proof of Lemma 3, pg. 378: Otherwise, $e$ was ...
1
vote
0answers
14 views

Does consensus require a turing machine?

Can we achieve consensus (paxos, zab, etc.) without using a turing machine? What's the least powerful machine we can use to achieve consensus?
0
votes
0answers
27 views

BFT algorithm perfo

Understand that BFT algorithms are always prepared for the worst possible circumstances and pays a price for this in terms of speed. Can one reasonably make the statement / assessment that non BFT ...
0
votes
0answers
16 views

Byzantine Fault Tolerant - What happens when the threshold of malicious/arbitrary fault is reached?

I understand that through the use of Proof of Work (PoW), Sybil attacks are deterred in public blockchains. The longest chain prevails. Malicious attackers are deterred. For consortium and/or private ...
1
vote
0answers
19 views

Multi-Paxos Full Disclosure: How does the acceptor know about the chosen value after it marks an entry as chosen?

I am learning multi paxos from the slides of this made by John Ousterhout and Diego Ongaro. In this section talking about Full Disclosure, it says the acceptor mark entry 6 as chosen, since the ...
1
vote
1answer
35 views

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

The main question is the following: When designing a system supporting atomic broadcast, can it be proved theoretically that the performance & scalability dimensions (i.e. latency, throughput, ...
2
votes
1answer
53 views

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

FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor ...
3
votes
1answer
160 views

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

I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously. Finally I want to know how to derive the consensus number of this algorithm. ...
3
votes
2answers
132 views

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

Just what the title says. Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system (without a single point of failure)? My current thoughts are that this ...
1
vote
1answer
194 views

Does Paxos consensus algorithm scale linearly?

I'm trying to build a P2P web application using Paxos to obtain a consensus value. How well does Paxos scale? linearly? or what kind of distribution can you expect? E.g. in using 10 to 10,000 users ...
3
votes
0answers
46 views

Auction website with Paxos consensus algorithm

As a project, I'm trying to construct a P2P auction web application with paxos in a high latency environment. The idea is that each user visiting the website will keep a small log file with the ...
2
votes
1answer
105 views

Consensus number of memory-to-memory swap

I think that consensus number of mem-to-mem-swap(a,b) operation which atomically swaps the values between shared locations a and b (shared R/W memory) is infinite , but I'm having trouble proving it. ...
1
vote
0answers
58 views

Behaviour of Regular Registers for Multiple Writer Case ( in context of Safe, Regular and Atomic Registers)

From the link below I understand the behaviour of different kinds of registers. However that raises few more queries in my mind. https://stackoverflow.com/questions/8871633/whats-the-difference-...
3
votes
1answer
89 views

Consensus anomaly about read-write registers and test&set

I read this answer below and got into another question. Why is the consensus number for test-and-set, 2? I also read that read/write registers have consensus number 1. But I see that in test&...
2
votes
1answer
71 views

Solving consensus for a known number of processes

I was given an object with exactly 2 operations test-and-reset that sets the value of the object to 0 only if it was previously set to 1 and does not return a value ...
3
votes
1answer
121 views

Paxos made simple — two details

I'm missing two details from Paxos made easy P1. An acceptor must accept the first proposal that it receives. What exactly is the reason for rule P1? What if the rule P2 was different, i.e. Upon ...
1
vote
0answers
22 views

Scalable byzantine consensus protocol for a boolean variable

Consider the following problem: We have an extremely large set of nodes, $\pi_0, \ldots, \pi_{N - 1}$ with $N$, e.g., in the order of millions. Each node has a boolean variable $b_0, \ldots, b_{N - 1}...
4
votes
2answers
766 views

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

Question I'm reading the FLP impossibility paper. I think I understand the idea of the proof, and I don't have questions about it. However, it seems like the assumption of having at most, a single ...
5
votes
1answer
161 views

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

Please bear with my unhelpful typesetting. My question is regarding well known FLP paper Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson While ...
3
votes
3answers
1k views

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

Last week I stood up and gave a talk on the Raft Consensus Algorithm. The first question I got was: Doesn't it need an odd number of nodes? I answered "During leader election, the first node to ...
1
vote
0answers
114 views

Using consensus for atomic commits

I read that consensus algorithms allow you to ensure the atomic commit. That is, in order to save a large amount of data on the disk, as if it is a single object, the article advises a consensus ...
5
votes
1answer
1k views

Why is the commit phase in PBFT necessary?

I've read many papers and slides on Practical Byzantine Fault Tolerance (PBFT) but I'm still confused about why a COMMIT phase is required. Most material states that PREPARE phase ensures fault-...
1
vote
1answer
80 views

Synchronisation and ordering in distributed systems

I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages ...
5
votes
1answer
366 views

Consensus protocols in multiplayer video games

I'm not 100% sure this appropriate for CS. Sorry. I'm looking for prior art on an idea I had, but either my Google fu is lacking, or it genuinely hasn't happened. In distributed systems, there are a ...
3
votes
1answer
1k views

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

By total-ordering I mean the following definition[0]: Total Event Ordering: Controller replicas should process events in the same order and subsequently all controller application instances ...
1
vote
1answer
465 views

What advantage does Tangaroa offer over PBFT?

Tangaroa is a relatively new project adding Byzantine fault-tolerance to the Raft consensus protocol using techniques that were already used in the PBFT algorithm. What are the advantages, when should ...
2
votes
1answer
1k views

What does atomicity mean in distributed systems?

In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem? Does atomicity have a different meaning in this context?
6
votes
1answer
320 views

Paxos consistency

I'm looking at the paxos family of protocols for solving consensus in a network of unreliable processors. I'm working through scenarios where processors fail, and I know I'm wrong, but I don't know ...
4
votes
1answer
314 views

Symmetric protocols for consensus

All the consensus algorithms that I've seen always depend on having a leader elected with all queries directed at the leader (assuming that we're not OK with getting back stale data). Are there any ...
2
votes
1answer
126 views

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

SetAgree(n, k) An object that allows n threads to propose() n values. It guarantees Each thread will decide() on a (single) value. The cardinal number of the set of all values decided on is lower or ...
16
votes
4answers
3k views

Why is the consensus number for test-and-set, 2?

According to Wikipedia, The test-and-set operation can solve the wait-free consensus problem for no more than two concurrent processes. Why can't it solve the problem for more than two processes?
5
votes
1answer
36 views

Proof of commonality of acceptors in majorities

In the Paxos consensus protocol, a fact that follows from its construction is "any two majority sets of acceptors will have at least one acceptor in common". This observation can be extended to any N ...