7 votes
Accepted

Determinism and pi-calculus

There are plenty such typing systems. Most work is based on the linear/affine typing system introduced in (1) and generalised in (2). Here are the main works on this subject. In (3) the typing system ...
Martin Berger's user avatar
6 votes
Accepted

Resources (books, etc) to learn about concurrency theory

There are not that many books on this subject, as it continues to evolve at a rapid pace. Classic books on process calculi (that don't focus on π-calculus-like mobility) are: C. A. R. Hoare, ...
Martin Berger's user avatar
5 votes

Can concurrency models be compared in terms of some metrics?

There are no metrics, but an excellent discussion of many concurrency models, in Tony Garnock-Jones PhD thesis. See the (HTML version of the) chapter "Approaches to coordination". This ...
gasche's user avatar
  • 2,040
5 votes

How to design concurrent data structures?

While I have not read deeply in this area, I found The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit to be a helpful introduction and survey of techniques. It explores different ...
user650881's user avatar
3 votes

Under what conditions is the Dining Philosophers Problem unsolvable?

Well, if the philosophers are following the exact same strategy and there is nothing to distinguish them (like who is closest to the door etc.) then they will do exactly the same and deadlock must ...
Bjørn Kjos-Hanssen's user avatar
3 votes

How to design concurrent data structures?

The answer is not as simple as functional programming. In functional programming here we have a general concept of what is functional programming and the specification of data structures themselves do ...
Kaveh's user avatar
  • 21.6k
3 votes

How exactly does a compatible reduction relation change the $\pi$-calculus?

Interesting question. As Damiano says, while syntactically trivial a change, the π-calculus with non-blocking inputs is a different model of computing. (A very different one, and an extremely ...
Martin Berger's user avatar
3 votes
Accepted

How exactly does a compatible reduction relation change the $\pi$-calculus?

I don't know "exactly" how it changes the calculus, in the sense that I don't have a formal statement measuring the difference (and I am not aware that there exists one), but allowing ...
Damiano Mazza's user avatar
2 votes

Confusion about a formal definition of PRAM consistency

When they define PRAM (page 11 of the arxiv preprint) they actually state that vis is a partial order (in particular, transitive): We define PRAM consistency by requiring the visibility partial ...
Bjørn Kjos-Hanssen's user avatar
1 vote

Equivalence of finitary and infinitary semantics of concurrent programs

For such $P_i$ we have that $\mathcal{R}(P_i)$ is the limit-closure of $\mathcal{F}(P_i)$. That the $P_i$ in general need to be finitely-branching for this claim is due to the fact that infinite ...
Kai's user avatar
  • 854
1 vote

Reference request: pi-calculus with simultaneous events

Milner defines the SCCS calculus in [1]. This is a generalization of CCS where the actions form an abelian group, and where the communication rule is defined as in my question. [1] Milner, R. Calculi ...
Ulrik Rasmussen's user avatar
1 vote

Algorithms to synthesize optimal plans satisfying temporal logic constraints

Maybe take a look at http://www.syntcomp.org/ This is a competition of tools solving the LTL synthesis problem (and some related problems).
Markus's user avatar
  • 366
1 vote

Why do timeouts require synchronized clocks?

Note that the authors also assume the following: Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processesor about ...
Peter's user avatar
  • 1,251
1 vote

How to design concurrent data structures?

The first rule of concurrent data structures is: You do not want concurrency. In the ideal case, distributed/parallel/concurrent computing means that you have a number of completely independent ...
Jouni Sirén's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible