21–30 of 47 posts
So, what is the inductive invariant in that simple algorithm?
The only actionable advice in here for someone tasked with developing a curriculum for teaching concurrency is to make sure the prerequisite courses instill the idea of computation as a sequence of state transitions.
“Sequence of state transitions” implies you can order them by time. Generally, various state transitions happen in parallel, their relative order is undefined even on an SMP system. You can serialize the transitions if you want, but that usually costs performance. This is especially true for distributed parallel computing, where the state is also distributed.
I think the first thing people should be taught about concurrency... is when not to use it. Concurrency can result in increased maintenance costs and complexity. Concurrency is also not more efficient on a single core. Concurrency can help with latency and response time. In embedded systems in particular, there is an over-use of concurrency which often results in bloated, complex code.
Concurrency is usually not a feature of the algorithm but a feature of the problem domain. If you have many requests coming in at the same time, all competing for a limited amount of computational resources -- you have concurrency.
How you handle it is a different matter. You can decide to handle the requests one by one, but then, by Little's law, your throughput would be very low, and your server will crash if the rate of requests is over some small limit (which depends on the time it takes to service each request).
Earlier quoted context omitted.
> one of those is what actually happens No it’s not. If the heads aren’t moving in lockstep, what actually happens is you’ll extremely rarely have a moment of time when both locations are whole numbers. At one moment you have { head1loc=0, head2loc=4.17 }, head #1 reached the cell position on the tape, head #2 is still moving. After a while, you’ll have { head1loc=0.872, head2loc=5}, head #1 is on its way, head #2 re…
Even if a Turing machine were a physical object (I had thought you would be aware that it's not), either one of those moves completes before the other, or both complete simultaneously.
I’d like to point out, the very moment you hooked second asynchronously moving head to the machine, the abstraction leaked spectacularly. With two asynchronous heads, the machine no longer has state; suddenly we need to consider physical time, not just count steps; and so on.
Turing machine is useful abstraction for sequential computing, but nearly useless to research parallel computing problems. The same happens with many other abstractions and approaches when going parallel.
> either one of those moves completes before the other
Yeah, but in parallel computing, we don’t know that order, and have no way of knowing. Meaning the “sequence of state transitions” idea is IMO nearly useless.
I think the first thing people should be taught about concurrency... is when not to use it. Concurrency can result in increased maintenance costs and complexity. Concurrency is also not more efficient on a single core. Concurrency can help with latency and response time. In embedded systems in particular, there is an over-use of concurrency which often results in bloated, complex code.
The next thing they should be taught is that even if an existing serial implementation can be made more efficient using concurrency, that doesn't mean it should be. That should be followed quickly by teaching that concurrency should be implemented over the smallest possible surface of the code.
I think the first thing people should be taught about concurrency... is when not to use it. Concurrency can result in increased maintenance costs and complexity. Concurrency is also not more efficient on a single core. Concurrency can help with latency and response time. In embedded systems in particular, there is an over-use of concurrency which often results in bloated, complex code.
> Concurrency is also not more efficient on a single core. Concurrency can be more efficient even on a single core. When blocking synchronous I/O is involved, concurrency may help saturate the bandwidth with multiple in-flight requests.
Otherwise, no.
(and in general, people just throw concurrency at the problem instead of analysing whether they are in fact I/O bound or CPU bound).
(Downvoted why??)
I think the first thing people should be taught about concurrency... is when not to use it. Concurrency can result in increased maintenance costs and complexity. Concurrency is also not more efficient on a single core. Concurrency can help with latency and response time. In embedded systems in particular, there is an over-use of concurrency which often results in bloated, complex code.
> Concurrency is also not more efficient on a single core. This isn't a hard and fast rule. There is overhead to parallelism.
For I/O bound code, concurrency can give you some benefit.
...but in general, people do not analyse this before throwing tasks at a problem.
So, what is the inductive invariant in that simple algorithm?
The inductive invariant is the correctness property itself (when all processes are done then at least one y is 1) in conjunction with "for all processes, when the process is not on line 1, then its x value is 1". You can probably replace the second conjunct with "for all processes, if the x value is 0, then the process is not done", but the proof gets a bit harder.
This is our partial correctness property
PartialCorrectness ≜ AllDone ⇒ ∃ p ∈ ProcSet : y[p] = 1
Inv ≜ PartialCorrectness
∧ ∀ p ∈ ProcSet : pc[p] ≠ "Line1" ⇒ x[p] = 1
Earlier quoted context omitted.
> Concurrency is also not more efficient on a single core. This isn't a hard and fast rule. There is overhead to parallelism.
For CPU bound code, concurrency is pure overhead. For I/O bound code, concurrency can give you some benefit. ...but in general, people do not analyse this before throwing tasks at a problem.
Would that be just anecdotal ?
Earlier quoted context omitted.
> Concurrency is also not more efficient on a single core. Concurrency can be more efficient even on a single core. When blocking synchronous I/O is involved, concurrency may help saturate the bandwidth with multiple in-flight requests.
if you are in an I/O bound situation, then yes, concurrency will allow you to exploit some parallelism. Otherwise, no. (and in general, people just throw concurrency at the problem instead of analysing whether they are in fact I/O bound or CPU bound). (Downvoted why??)