Skip to main content
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
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 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

algebraic topology in distributed computing

Maurice Herlihy, Dmitry Kozlov and Sergio Rajsbaum, "Distributed Computing Through Combinatorial Topology", 2014
Kaveh's user avatar
  • 21.7k
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

What's the difference between the Actor Model of Concurrency and Communicating Sequential Processes

CSP is roughly like processes communicating via TCP connections (sender blocks until the receiver ACKed), the actor model is roughly like processes communicating via UDP (you send packets and hope for ...
saolof's user avatar
  • 111

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