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.

Filter by
Sorted by
Tagged with
1
vote
1answer
39 views

Where were the ideas of vote, accept and commit phases originally introduced?

In the Stellar Consensus Protocol SCP, the voting procedure follows a 3 phase commit i.e. vote, accept and confirm i.e. see section 5. Is this a novel introduction or has this been previously been ...
1
vote
0answers
14 views

Are Physical 2-Person Lock Systems Informed by The Byzantine Generals Problem

The Byzantine Generals Problem says a set of generals who are greater than 2/3rds loyal is required to guarantee that securely issuing an order is possible the loyal generals. Because of this, I am ...
1
vote
0answers
18 views

Problem of making entities agree on some wavelength

I remember seeing this problem somewhere before, but don't remember what it's called and can't find it again. It was presented as two guys having $n$ phones each that don't ring when called. Each ...
0
votes
0answers
10 views

How to detect a consensus is BFT or not?

Can we divide consensus algorithms into BFT (Byzantine Fault Tolerant) and non-BFT ? If so, How to detect a consensus is BFT or non-BFT ? Is there any non-BFT consensus algorithm example ?
0
votes
0answers
16 views

What is the relationship between Consistency Models and Consensus Algorithms?

I know that: Each replication technique should follow a consistency model. A consistency model defines a set of rules for the order of the write and read operations. In some replication techniques ...
1
vote
1answer
27 views

Looking for two-way communication/consensus/contract algorithm for use in marriage proposal

I am looking for some sort of communication or consensus algorithm with the following properties: Can be used with just two parties (and ideally doesn't collapse to a trivial case with two parties) ...
2
votes
1answer
29 views

Consensus/ranked ordering algorithm

Say I have a set of numbers, for example {1, 2, 3, 4, 5}. Is there an algorithm that allows these numbers to be put into a consensus ordering based on a ranked vote?...
1
vote
1answer
38 views

How does paxos algorithm handle partial failures of accept messages?

I've been reading the basic paxos algorithm from the "Paxos Made Simple" paper. I can't understand how paxos algorithm maintains the safety properties under partial failures of the accept messages, ...
1
vote
0answers
24 views

Why don't RDBMS use a quorum based solution to do failover

For RDBMS viz. MySql, PostgreSql a common solution for scalability and high availability is to run a primary instance as master that is a read-write instance and one or more read replicas. If the ...
4
votes
0answers
71 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
44 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
1answer
73 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
67 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
107 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
26 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
141 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
17 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
30 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 ...
1
vote
0answers
23 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
2answers
81 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
69 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
192 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
190 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
253 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 ...
2
votes
0answers
50 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
179 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
69 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-...
2
votes
1answer
109 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
93 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
2answers
145 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
25 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
1k 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 ...
4
votes
1answer
202 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
2k 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
137 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 ...
6
votes
1answer
2k 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
92 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
464 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
2k 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
506 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?
5
votes
1answer
340 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
344 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
139 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
4k 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
40 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 ...