Questions tagged [concurrency]
Questiont about issues of concurrency such as synchronization and deadlocks.
239
questions
0
votes
2answers
68 views
Is this a deadlock?
Consider we have two processes P1 and P2. There are also two semaphores M and N which are initialized to zero. Here's how they execute:
...
1
vote
0answers
25 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?...
1
vote
0answers
59 views
How to prove that an algorithm has no deadlock
I need to mathematically prove that this algorithm is deadlock-free:
...
0
votes
1answer
40 views
What is google docs solution to handling multiple users editing and reading at the same time?
I have always been curious as to how google solved the solution of real time collaboration in their google docs product where they allow multiple users to edit and read the same document in real time.
...
1
vote
1answer
18 views
Distributed algorithm can be executed in a single process
Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency ...
2
votes
0answers
22 views
Concurrent Element-wise Reduction Algorithm (multi-threaded) (C++)
I'd like to implement a high-performance implementation of a multi-threaded reduction, element-wise, on x86 CPUs. Without loss of generality, assume the reduction operation is a sum of integers (so, ...
1
vote
0answers
23 views
Comparing wait-signal alternatives for synchronizing two piece of programs
I came across following problem:
A certain computation generates two arrays a and b such that ...
2
votes
1answer
51 views
Designing solution to critical section problem with two semaphores vs single semaphore
I came across following problem:
Let two processes P1 and P2 are there:
...
2
votes
0answers
23 views
Does this state certify to be called as a deadlock?
I came across following problem:
Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others ...
0
votes
2answers
247 views
Whats exact definition of 'atomicity' in programming?
the definition of 'atomicity' says that a transaction should be able to be terminated without being touched or manipulated by possibly concurrent running actions during its process. But does that also ...
4
votes
1answer
54 views
Are two CCS processes equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas?
I was skimming this recent paper and I was struck by the following statement:
two processes are equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML ...
1
vote
0answers
46 views
1
vote
1answer
77 views
Can a schedule be conflict serializable but not serializable?
A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then,
My question is: Can a schedule be conflict serializable but ...
0
votes
0answers
82 views
When cascadeless and / or recoverable schedules can contain blind writes?
Some quick definitions / theory:
If instructions $I_i$ and $I_j$ of two different transactions operate on same data item and if any of them is a write operation then they are conflicting ...
3
votes
1answer
143 views
What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?
Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle).
It ...
1
vote
0answers
45 views
Prove that set of operations form a commutative Monoid
this is my first post on this exchange.
I am looking for some help with defining a proof that a set of operations I have designed forms a commutative monoid.
(Disclaimer: I am not sure that I have ...
1
vote
2answers
31 views
System restarted before transaction is committed
Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.
...
1
vote
1answer
89 views
Can 2-philosophers problem be analogous to dining philosophers problem?
Two philosophers A and B, two forks numbered "1", "2"; A needs both "1" and "2" for eating, so does B.
Is this theoretical a dining philosopher problem? I'm questioning about the forks philosopher A ...
1
vote
0answers
54 views
How can I implement locking a range of values in a sorted sequence?
I am trying to write a general purpose locking algorithm which allows me to lock a range of contiguous values in a sorted array. To start with, these could be exclusive locks - so two concurrent locks ...
0
votes
0answers
864 views
Thoughts on definition for disadvantage of concurrent processing?
I'm a Computer Science student currently learning about concurrent processing. I found the benefits and disadvantages in my book vague, did some online research and put together a more detailed way of ...
2
votes
2answers
65 views
What is the formal statement of the dining philosopher's problem?
I've read about it in a few places and I'm not sure I get it.
Are the philosopher's allowed to act simultaneously?
Do they each take 1 action simultaneously, then go on to their next action?
1
vote
0answers
52 views
Do we really need a mutex in this case?
Wikipedia's solution for multi Producer-Consumer problem uses both mutexes and semaphores.
...
1
vote
1answer
379 views
Which Peterson’s Solution is right?
I have seen two different Peterson’s Solution to mutual exclusion, one is from Modern Operating Systems:
...
2
votes
0answers
96 views
how to find the depth of a concurrency bug
How to find the depth of a concurrency bug
The below program runs on two separate threads and shares the variable x. Variables t1 and t2 are local to their threads. The program has a concurrency bug ...
0
votes
1answer
29 views
Can Multiprocessor Systems Implement Both Temporal Multithreading and Simultaneous Multithreading?
I am aware that multiprocessor systems often implement simultaneous multithreading in order to allow multiple threads to run on different CPUs. I am also aware that uni-core systems often implement ...
0
votes
1answer
68 views
What is the Difference Between Many-to-Many (M:M) Threading and Hybrid (M:N) Threading?
I have been researching threading and come across several websites which all say contradicting statements about which and how many thread models exist. Some websites say there are only three: 1:1, M:1 ...
1
vote
1answer
113 views
What fraction of all combinations is guaranteed to be deadlock free?
I found this question in the exercise of Tanenbaum (operating systems):
Two processes, $A$ and $B$,each need three records $1, 2, \text{ and } 3$ in a database. If $A$ asks for them in the
order $...
1
vote
0answers
61 views
How to Optimise Each Multithreading Technique? (Cooperative/Preemptive/Simultaneous)
I am currently in the process of writing an IB Extended Essay on the efficacy of multithreading on increasing the performance of applications. So far, I have been able to deduce that there are three ...
3
votes
0answers
145 views
0
votes
1answer
66 views
Checking claim in paper “A Read-Only Transaction Anomaly Under Snapshot Isolation” by Alan Fekete et al
In the 2004 paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al. (which can be found here and here) the authors state:
We also note that any execution of T1 and T2 ...
0
votes
1answer
41 views
How to keep track of changes done to concurrent stacks?
I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions:
...
1
vote
1answer
22 views
Are process-safe mutexes shared between OSes?
I understand you can use process wide mutexes, but does this still apply if you have an additional virtualized operating system provisioned?
For example, take two OSes: ...
1
vote
2answers
801 views
Serializability and the Lost Update Problem
Serializability is the strongest consistency level with regard to the execution of two concurrent transactions T1 and T2. That is, if T1 and T2 independently change the application between consistent ...
-2
votes
1answer
60 views
Erlang- Creating a function which only adds/subtracts positive integers
I want to create a function which allows me to input a list, and then add all of the positive numbers from the list together, leaving any that are negative.
([3,1,-1])
For example only 3 and 1 would ...
2
votes
1answer
64 views
What are good resources for self teaching parallel/concurrent/multithreaded programming techniques? [closed]
I’m having a hard time finding anything thorough. I have found some courses with titles like "parallel and concurrent programming in Java", but I'm looking to learn general techniques, not their use ...
4
votes
1answer
100 views
Task scheduling algorithm that limits concurrency
My prof introduced us an algorithm with semaphores that was used to solve the "dining philosophers" problem.
The algo is ok, apart from that it limits concurrency.
What does mean that it "limits ...
0
votes
1answer
116 views
Concurrency and fairness
I'm studying the concurrency in programming and the atomic instructions.
What i have not understood is the concept of "fairness" applied to this matter.
Can you give me an hint ?
0
votes
0answers
24 views
Concurrency and non deterministm
I was introduced in concurrency programming this morning.
I haven't understood why "non deterministm" is a fundamental aspect of cuncurrenty programming.
What i think is that, since there is a ...
14
votes
2answers
2k views
Is it possible for a stack-based programming language to be concurrent?
I have been reading about stack-based programming languages, such as FORTH and Cat, and it seems that given their nature, they can only execute one action at a time regardless of their paradigm (FORTH ...
2
votes
0answers
192 views
interval tree clocks
I understand how vector clocks detect concurrent events, but they are designed for a fixed number of nodes, so we can't easily add and remove nodes. And with interval tree clock we can.
Could you ...
1
vote
0answers
127 views
bakery algorithm, switching up the condition
I'm currently studying the Bakery Algorithm. I understand it for what it is but now I want to switch it up a bit.
If we changed the < in the 2nd ...
2
votes
1answer
64 views
Compute the mode of an array concurrently
As an academic exercise, I have to write a parallel algorithm that given a sorted array of $n$ integers computes the mode (i.e. the item with the highest frequency) efficiently using $p$ processors, ...
2
votes
1answer
116 views
How to do compare-and-increment different locations with in memory MVCC?
I'm reading the paper An Empirical Evaluation of
In-Memory Multi-Version Concurrency Control which is about implementations of MVCC for in-memory databases. Section 3.3 on Two-phase Locking (MV2PL) ...
1
vote
1answer
1k views
What does synchronous and asynchronous mean in computer science?
Words synchronous and asynchronous can be met several times, in different contexts, when studying computer science. As an example :
Synchronous and asynchronous circuits.
Synchronous and asynchronous ...
0
votes
0answers
18 views
concurrency control in real time database
Can Lamport's Bakery algorithm be used for controlling concurrency in soft real time database system (case study of stock trading)?
0
votes
2answers
89 views
Conflict serializibility
So, the task is to prove the following:
If S is a schedule containing at most one write action, then S is conflict-serializable.
The answer is yes, but I disagree, because the following schedule ...
3
votes
1answer
1k views
Number of conflict serializable schedules
Two transactions $T_1$ and $T_2$ are given as:
$$T_1: r_1(X)w_1(X)r_1(Y)w_1(Y)$$
$$T_2: r_2(Y)w_2(Y)r_2(Z)w_2(Z)$$
where $r_i(V)$ denotes a read operation by transaction $T_i$ on a ...
2
votes
1answer
73 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 ...
1
vote
0answers
45 views
Lamport's distributed mutual exclusion: wait-chain order clock
Regarding Lamport's mutual exclusion... Where messages are exchanged in the following sequence between nodes S, G1, and G2. G1 and G2 are the members of the group.
(for this, lets just assume that ...
1
vote
0answers
109 views
Is Dekker's algorithm not k-bounded for any finite k?
Consider this version of the algorithm, for only 2 processes, 0 and 1:
...
