All Questions
Tagged with paxos distributed-computing
33 questions
0
votes
1
answer
53
views
How does raft prevent submitted logs from being overwritten
figure 8 in raft paper
Consider a situation like the figure 8 in raft paper, but in (c), log entry from term 2 has been commited, and s1 crashs, s5 becomes leader, then s5 send append entry rpc to s2, ...
- 21
1
vote
1
answer
2k
views
what is the key difference between multipaxos and basic paxos protocol
how is multipaxos different from basic paxos? How does ordering work in multipaxos?
Can someone explain multi-paxos along with the diagram
Tried out going through videos and research papers but ...
- 15
2
votes
2
answers
169
views
In Paxos, why can't we use random backoff to avoid collision?
I understand that the heart of Paxos consensus algorithm is that there is only one "majority" in any given set of nodes, therefore if a proposer gets accepted by a majority, there cannot be ...
- 1,544
3
votes
1
answer
672
views
Paxos understanding
I have read the paper Paxos made simple.
And after hard thinking, I come to this conclusion:
The Paxos protocol always guarantees the majority of servers accept the same value at the same turn of the ...
- 385
1
vote
1
answer
201
views
paxos algorithm - how does the propose stage work?
I am looking at the pseudocode for the PROPOSE stage of the paxos algorithm: https://www.cs.rutgers.edu/~pxk/417/notes/paxos.html
did I receive PROMISE responses from a majority of acceptors?
if yes
...
- 7,275
0
votes
1
answer
49
views
How can I understand "value" in bacis paxos
I am reading Lamport's Paxos Mode Simple, and I get confused with the meaning "value" here.
For example, Lamport says:
If a proposal with value v is chosen, then every higher-numbered ...
- 2,907
1
vote
0
answers
114
views
Mencius and AllConcur Consensus Algorithms
Just wanted to ask if anyone has had any thoughts on the similarities and differences between the Mencius and AllConcur consensus protocols?
At first glance these algorithms are presented very ...
- 138
0
votes
2
answers
674
views
Two Phase Commit blocking on coordinator failure
I was trying to read the Paxos Commit paper and am struggling witih moving past the introduction. The intial section builds a motivation for a fault-tolerant transaction coordinator implementation in ...
- 21.4k
0
votes
2
answers
334
views
In paxos, what happens if a proposer is down after its proposal is rejected?
In this figure, the proposal of X is rejected.
At the end of the timeline, S1 and S2 accept X while S3, S4 and S5 accept Y. Proposer X is now supposed to re-send the proposal with value Y.
But what ...
- 169
2
votes
1
answer
936
views
Does paxos provide true linearizable consistency or not?
I think I might be confusing concepts here, but it seems to me like paxos would provide linearizable consistency for systems that implement it.
I know Cassandra uses it. I'm not 100% clear on how but ...
- 31.3k
3
votes
1
answer
985
views
Is Paxos Strongly Consistent?
Consider a distributed system with 3 nodes- n1, n2, n3. There is a shared data, x, among the nodes. Paxos is running on the nodes. In the beginning, x is equal to 4.
A client sends an update request ...
- 443
5
votes
3
answers
556
views
How do replicas coming back online in PAXOS or RAFT catch up?
In consensus algorithms like for example PAXOS and RAFT, a value is proposed, and if a quorum agrees, it's written durably to the data store. What happens to the participants that were unavailable at ...
- 832
3
votes
2
answers
525
views
Commit Failure in Paxos
I am new to the Distributed System and Consensus Algorithm. I understand how it works but I am confused by some corner cases: when the acceptors received an ACCEPT for an instance but never heard back ...
- 43
0
votes
1
answer
1k
views
Why is leader election mandatory for a write but not for a read request?
In a reliable distributed system leader election is mandatory for write success and I can understand that it's required to follow the Paxos algorithm.
However, why is a leader election (thus ...
0
votes
1
answer
283
views
Consistency in Different Context (Distributed System vs Memory Model vs Database)
I am confused by the term "Consistency". It's been used in many different context, i.e Distributed System, Memory Model and Database. People/Wikipedia summarize all different Consistency Model in the ...
- 585
5
votes
2
answers
800
views
Why Paxos is design in two phases
Why Paxos requires two phases(prepare/promise + accept/accepted) instead of a single one? That is, using only prepare/promise portion, if the proposer has heard back from a majority of acceptors, that ...
- 3,480
3
votes
2
answers
65
views
Is keep logging messages in group communication service or paxos practical?
In the case of network partition or node crash, most of the distributed atomic broadcast protocols (like Extended Virtual Synchrony or Paxos), require running nodes, to keep logging messages, until ...
- 33
3
votes
1
answer
487
views
using sql primary keys for master election- is there a flaw in this approach?
Let's say I've SQL schema like this-
create table master_lock(job_type int primary key, ip varchar);
Now each node tries to insert a value like this-
insert into master_lock values(1,192.168.1.1);...
- 1,368
3
votes
2
answers
217
views
Paxos and Discovery
Suppose I throw some machines in an elastic cluster and want to run some consensus algorithm in they (say, Paxos). Suppose they know the initial size of the network, say, 8 machines.
So, they'll run ...
- 2,709
4
votes
4
answers
2k
views
Paxos algorithm in the context of distributed database transaction
I had some confusion about paxos, specifically in the context of database transactions:
In the paper "paxos made simple", it says in the second phase that the proposer needs to choose one of the ...
- 1,915
2
votes
2
answers
633
views
Using Paxos to synchronize a large file across nodes
I'm trying to use Paxos to maintain consensus between nodes on a file that is around 50MB in size, and constantly being modified at individual nodes. I'm running into issues of practicality.
...
- 2,852
0
votes
0
answers
66
views
How is poxos keep replication logs in sync practically
I read the paxos can be used to keep replications in sync by syncing operation logs to replications.
To my understanding each paxos instance will define an log id with the operation
Ideally the ...
- 1
8
votes
2
answers
993
views
Why is it legit to use no-op to fill gaps between paxos events?
I am learning Paxos algorithm (http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf) and there is one point I do not understand.
We know that events follow a timely order, and ...
- 11.9k
4
votes
1
answer
594
views
Does paxos "ignore" the request for updating the value if it is not in sync with highest proposal number sent by acceptor?
Title here could be misleading. I will try my best to explain my doubt through an example.
I am reading about paxos algorithm from wiki and other sources.
1) Imagine a situation where a client's ...
- 31.2k
5
votes
1
answer
2k
views
What's the benefit of advanced master election algorithms over bully algorithm?
I read how current master election algorithms like Raft, Paxos or Zab elect master on a cluster and couldn't understand why they use sophisticated algorithms instead of simple bully algorithm.
I'm ...
- 339
48
votes
2
answers
17k
views
Paxos vs two phase commit
I am trying to understand the difference between paxos and two phase commit as means to reach consensus among multiple machines. Two phase commit and three phase commit is very easy to understand. It ...
- 4,188
8
votes
4
answers
2k
views
What to do if the leader fails in Multi-Paxos for master-slave systems?
Backgound:
In section 3, named Implementing a State Machine, of Lamport's paper Paxos Made Simple, Multi-Paxos is described. Multi-Paxos is used in Google Paxos Made Live. (Multi-Paxos is used in ...
- 1,999
6
votes
1
answer
1k
views
avoiding overuse of consensus protocols in a distributed system
I'm new to distributed systems, and I'm reading about "simple Paxos". It creates a lot of chatter and I'm thinking about performance implications.
Let's say you're building a globally-distributed ...
- 7,687
6
votes
3
answers
1k
views
How does a consensus algorithm guarantee consistency?
How does a consensus algorithm like Paxos "guarantee safety (freedom from inconsistency)" when two generals prove the "impossibility of designing algorithms to safely agree"?
When I consider the ...
1
vote
1
answer
623
views
How to make sense of Phase 2 in Paxos distributed consensus algorithm?
I have pasted pseudocode for a paxos algorithm here:
What is a "view" in the Paxos consensus algorithm?
and was wondering if someone could point me in the right direction.
The ...
- 1,939
1
vote
2
answers
1k
views
What is a "view" in the Paxos consensus algorithm?
I have pasted pseudocode for a paxos algorithm below and was wondering if someone could point me in the right direction. I am trying to implement the algorithm below, but I'm a confused what exactly "...
- 1,939
10
votes
4
answers
1k
views
Using Paxos in dynamic environment
Paxos algorithm can tolerate up to F failures when using 2F + 1 processors. As far as I understand, this algorithm works only with fixed number of processors. Is it possible to use this algorithm in ...
- 9,403
6
votes
4
answers
3k
views
In Paxos, can an Acceptor accept a different value after it has already accepted one?
In Multi-Paxos algorithm, consider this message flow from the viewpoint of an acceptor:
receive: Prepare(N)
reply: Promise(N, null)
receive: Accept!(N, V1)
reply: Accepted(N, V1)
receive: Accept!(...
- 790