All Questions
Tagged with concurrency consensus
11 questions
1
vote
0
answers
20
views
Spin-free synchronization primitives
I'm interested in concurrent algorithms where, if a thread is waiting for a shared resource, it must call a blocking primitive, and not busy-wait. I'll call such algorithms spin-free. Specifically, I'...
3
votes
1
answer
530
views
Difference between consensus number n and consensus number infinite
In book Concurrent Programming: Algorithms, Principles, and Foundations of Michel Raynal, in Section 16.5.1, Theorem 75 says
Compare&swap objects have infinite consensus number.
and in ...
- 143
1
vote
0
answers
72
views
n thread consensus queues
Its generally agreed that wait free queues have a consensus number of 2.
But what about this following code for a consensus protocol for a queue.
How is it that this does not go against the idea above?...
- 11
3
votes
1
answer
107
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 ...
- 41
2
votes
1
answer
317
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.
...
- 157
1
vote
0
answers
147
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-...
- 265
2
votes
1
answer
166
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 ...
- 121
3
votes
3
answers
318
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 ...
- 31
6
votes
1
answer
540
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 ...
- 265
2
votes
1
answer
238
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 ...
- 21
19
votes
4
answers
7k
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?
- 295