Concurrent systems are systems where several threads of computation are potentially executing simultaneously and interacting.
1
vote
1answer
26 views
Definition of “K-fairness” with respect to concurrency?
There are definitions of Absolute, Strong and Weak Fairness available across the internet, but I cannot find a definition of "K-Fairness" property for critical section algorithms (also algorithms that ...
11
votes
1answer
137 views
What does 'true concurrency' mean?
I often hear phrases like 'true concurrency semantics' and 'true concurrency equivalences' without any references. What does those terms mean and why are they important?
What are some examples of ...
4
votes
1answer
53 views
Formalisms in concurrent and/or distributed programming?
My background came from imperative languages, primarily C, C++, and Python. I picked up Scala, Erlang, and a bit of Haskell a few years later and have since become very interested in functional ...
0
votes
1answer
58 views
concurrency and hardware
I've a couple of questions that I need answers for. What I am looking for here is the outline of the answers. Not necessarily the exact complete answer. I can do that.
The question is that common ...
2
votes
0answers
54 views
Is there a list of canonical problems in distributed systems? [closed]
Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about Solved Problems, Unsolved Problems and Non-Problems in Concurrency. The paper is easily readable, but ...
1
vote
1answer
43 views
Synchronization using serialization
How can someone synchronize two or more threads using serialization? According to my professor's slides and code assignments you can use serialization to solve the synchronization problem. (He doesn't ...
0
votes
1answer
21 views
applying CTL/LTL model-checking on some system
I apologies if my title is vague, I'm trying to apply CTL/LTL model-checking on some system written in java, however, I still don't understand how to reach a result using either of the approaches ...
2
votes
1answer
43 views
Process graphs and finding infinite processes
I am reading on concurrent processes and algorithms which find infinite processes by searching the process graph recursively.
Most of the material I have found is not for beginners. I am looking for ...
3
votes
2answers
57 views
Mutual exclusion for n processes
I want to implement mutual exclusion for $n$ processes. Critical section code:
...
3
votes
1answer
82 views
What is a linearization point?
With respect concurrent programming, what is a linearization point?
They seem to occur at a compare-and-swap instruction apparently. The best definition I could find is here.
All function calls ...
0
votes
0answers
72 views
How to calculate the blocking probability of processes with gamma-distributed service times using the Erlang formula?
I have seen numerous examples of using the Erlang formula to calculate the blocking probability for processes with exponentially distributed service times. However, I am not quite sure how to do that ...
3
votes
1answer
261 views
Banker's Algorithm and deadlocks
So we have the following table of processes , where A, B and $\Gamma$ are the resources.
Here is a pic that i drew with the processes and the resources.
So the exact question is this: Using ...
3
votes
1answer
134 views
Batch processing in increase-key function using binary heap
Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one ...
15
votes
1answer
367 views
Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.
I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
6
votes
1answer
110 views
Variation of the dining philosophers: is the standard solution still valid?
I have a problem that is almost equal to the standard one of the dining philosophers, but has a quirk: while a philosopher thinks, he still holds the fork on his left.
If after the period of thinking ...
5
votes
1answer
105 views
Compare-and-Swap in an RDBMS for custom locks and lock escalation
I'm applying the Compare-and-Swap technique to a SQL database to create custom row-level locking in my dataset, allowing for safe READ UNCOMMITTED isolation at the database level.
The Resource table ...
5
votes
1answer
162 views
What is the purpose of M:N (Hybrid) threading?
In other words, what advantages does Hybrid threading have over 1:1 (kernel only) and N:1 (user only) threading?
This is a follow-up to What is the difference between user-level threads and ...
11
votes
1answer
4k views
What is the difference between user-level threads and kernel-level threads?
After reading several sources I'm still confused about user- and kernel-level threads.
In particular:
Threads can exist at both the user level and the kernel level
What is the difference ...
8
votes
3answers
233 views
Similarities and differences in major process algebras
To my knowledge, there are three major process algebras that have inspired a vast range of research into formal models of concurrency. These are:
CCS and $\pi$-calculus both by Robin Milner
CSP by ...
7
votes
2answers
126 views
CCS process for a drink dispenser with two different prices
A drink dispenser requires the user to insert a coin ($\bar c$), then press one of three buttons: $\bar d_{\text{tea}}$ requests a cup of tea $e_{\text{tea}}$, ditto for coffee, and $\bar r$ requests ...
4
votes
1answer
119 views
termination of two concurrent threads with shared variables
We're in a shared memory concurrency model where all reads and writes to integer variables are atomic.
do: $S_1$ ...
6
votes
2answers
283 views
Does Peterson's 2-process mutual exclusion algorithm account for dying processes?
I think that in Peterson's algorithm for mutual exclusion, if the process first to enter the critical section were to die or be cancelled, the other process would loop forever, waiting to enter the ...
4
votes
1answer
46 views
Which instruction yields atomicity in this expression that makes the result 2?
I am reading about atomicity and came across the following scenario
...
5
votes
1answer
139 views
Reflection on Concurrency
Reflection is a common mechanism for accessing and changing the structure of a program at run-time, found in many dynamic programming languages such as Smalltalk, Ruby and Python, and in impoverished ...
