Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [concurrency]

Concurrency is the study of systems that operate simultaneously. For example given a set of elevators and a pool of people who want to go to various floors. An example of a concurrent system would be the management system that would tell where the elevators go and where to let off a person of the pool of people.

18 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13 votes
0 answers
534 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)$ ...
A T's user avatar
  • 566
5 votes
0 answers
140 views

What is the significance of regarding the mutual exclusion problem as a problem of physics?

In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote Most computer scientists regard synchronization problems, such ...
hengxin's user avatar
  • 2,329
4 votes
0 answers
136 views

What are the parts of consistency model playing in hardware, operating system, and programming language?

In multiprocessor programming, consistency model is the key concept to express the correctness of concurrent objects ranging from simple read/write shared variable to concurrent data structures like ...
hengxin's user avatar
  • 2,329
3 votes
0 answers
230 views

In what sense, does a safe register exist?

In the paper "On Interprocess Communication", the author Leslie Lamport have developed a formalism for interprocess communication via shared registers based on lower-level, non-atomic operations and ...
hengxin's user avatar
  • 2,329
3 votes
0 answers
268 views

Atomic snapshot algorithms on tree-structured shared registers

Background: Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety. The Gang of Six algorithm ...
hengxin's user avatar
  • 2,329
2 votes
0 answers
308 views

Are CCS and CSP still worth studying?

In Winskel's The formal semantics of programming languages 1993, Ch14 Nondeterminism and parallelism says This chapter is an introduction to nondeterministic and parallel (or concurrent) ...
Tim's user avatar
  • 639
2 votes
0 answers
106 views

Are the sets of executions of data-race free programs equal, when run on causal memory and on sequentially consistent memory respectively?

In the paper "Causal Memory: Definitions, Implementations, and Programming (Distributed Computing [DC] 1995)", the authors present a formal definition of causal memory, an abstraction of distributed ...
hengxin's user avatar
  • 2,329
2 votes
0 answers
110 views

non-malleable commitment and security parameters

Although it is not clear, it appears that definition 5 of this paper, page 10 of this paper, and page 6 of this paper, each assume that the honest parties will all use the same security parameter. ...
user avatar
2 votes
0 answers
784 views

On the Bakery Mutual exclusion Algorithm

Lamport's Bakery Algorithm is one of the most elegant algorithms for mutual exclusion. The beauty of it is that it works even when the underlying system only provides a weak form of registers called ...
kryptos's user avatar
  • 460
1 vote
0 answers
57 views

How to justify this causally consistent execution in the $(vis, ar)$ framework for distributed consistency models?

In Figure 5.1 of the book "Principles of Eventual Consistency" by Sebastin Burckhardt, 2014, Causal Consistency (CC); wiki is (mainly) defined as the conjunction of $hb \subseteq vis$ and $hb \...
hengxin's user avatar
  • 2,329
1 vote
0 answers
112 views

Confusion about the visibility and arbitration relations in a formal framework for distributed consistency models

In the POPL'14 paper "Replicated Data Types: Specification, Verification, Optimality" and the book "Principles of Eventual Consistency", the authors propose a formal framework for ...
hengxin's user avatar
  • 2,329
1 vote
0 answers
55 views

How to read this formula for composition in an asynchronous interaction category?

The paper is available here Interaction Categories and the Foundations of Typed Concurrent Programming Abramsky, Gay, Nagarajan p.38 composition of two processes $p:A \rightarrow B$, $q:B \rightarrow ...
Spearman's user avatar
1 vote
0 answers
56 views

What is the staleness in this execution of the $k$-atomic multi-writer register construction from $k$-atomic single-writer ones?

Background: $K$-atomicity is a consistency condition meaning that a read operation can return one of the values written by the last $k$ preceding writes in an order consistent with real time. It is a ...
hengxin's user avatar
  • 2,329
1 vote
0 answers
59 views

Correct algorithms with sequentially inconsistent executions

as far as I understood one wants that an algorithm produces only results that can be also achieved by a sequentially consistent execution. My question is whether this is true or whether there are ...
drvj's user avatar
  • 11
0 votes
1 answer
225 views

Where to read about PSO (partial store order) memory model

I have been reading about TSO (total store order) memory models for concurrent programs, but I can not find resources for PSO (partial store order) memory models. Can someone please point to resources....
Anonymous's user avatar
0 votes
0 answers
564 views

What is the difference between a model of computation and a programming language?

https://en.wikipedia.org/wiki/Model_of_computation includes sequential models, functional models and concurrency models. Sequential models include finite state machine, Turing machines, random access ...
Tim's user avatar
  • 639
0 votes
0 answers
160 views

Sequential Consistency, cannot find a sufficient explanation

I am having a hard time understanding the SC memory model properly. The sentence "the result of any execution is the same as if the operations of all the processors were executed in some sequential ...
Yarneo's user avatar
  • 101
-2 votes
1 answer
204 views

What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
gmr's user avatar
  • 121