![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
continued from [1]
and connectivity
small world networks
imagine that there are a zillion nodes in some unknown topology. Notes can directly communicate with their neighbors. One might imagine that this is a discrete approximation to a continuous fluid of nodes. Primitives provided include:
http://groups.csail.mit.edu/mac/projects/amorphous/papers/lsmas-final.pdf
a similar system which is explicitly for the purpose of sensor networks is Regiment: http://www.cs.harvard.edu/~mdw/papers/regiment-ipsn07.pdf
https://en.wikipedia.org/wiki/Bulk_synchronous_parallel
http://software-carpentry.org/blog/2011/03/tuple-spaces-or-good-ideas-dont-always-win.html
(what is the event (re)ordering model of tuple spaces?)
http://www.diku.dk/~vinter/cc/Lecture10TupleSpaces.pdf
" General purpose cores Flexible multithreading 2. Vector hardware Vector parallelism 3. GPUs Restrictive data parallelism 4. FPGAs Customized dataflow 5. Custom accelerators Various forms "
an interesting thing that i am seeing all over is the application of the 'referential transparency'/'purely functional' idea to larger systems, in a few specific ways. First, the software is architected as a stateless (purely functional) computation that is given events and access to external state as input and spits out actions as output. Second, each memory location in the external state doesn't just hold the current value, but also all past values, with some sort of timestamp (or equivalently (in this model), integer sequence number). Not all of these examples do exactly that, but they are all related:
Examples:
Criticism of this pattern, in databases: http://www.xaprb.com/blog/2013/12/28/immutability-mvcc-and-garbage-collection/
"The Propagator Programming Model is built on the idea that the basic computational elements are autonomous machines interconnected by shared cells through which they communicate. Each machine continuously examines the cells it is interested in, and adds information to some based on computations it can make from information from the others. Cells accumulate information from the propagators that produce that information. The key idea here is additivity.
...
The ingredients of a propagator network are cells and propagators. The cells' job is to remember things; the propagators' job is to compute. The analogy is that propagators are like the procedures of a traditional programming language, and cells are like the memory locations; the big difference is that cells accumulate partial information (which may involve arbitrary internal computations), and can therefore have many propagators reading information from them and writing information to them.
...
Cells must support three operations:
add some content
collect the content currently accumulated
register a propagator to be notified when the accumulated content changes
When new content is added to a cell, the cell must merge the addition with the content already present. When a propagator asks for the content of a cell, the cell must deliver a complete summary of the information that has been added to it.
The merging of content must be commutative, associative, and idempotent. The behavior of propagators must be monotonic with respect to the lattice induced by the merge operation. "
Links:
channel mutex semaphore condition variable
---
"Transactional memory support is what it sounds like: hardware support for transactions. This is through three new instructions, xbegin, xend, and xabort." [4]
---
" Of all the ways of doing concurrency, callbacks are by far the worst, Twisted was plagued by them and is the main reason why it failed, and that was with a much more sane and reasonable language like Python (stackless Python was a much better alternative and used a model similar to Go’s CSP).
And the sad thing is that there are much better alternatives around with much more sound models and environments, Erlang and Go are the two obvious examples, and that is for the highly specialized situations where you have great concurrency needs, for any other problem anything else will be much better than Node.js, even PHP.
– uriel, in response to Why Node.JS is absolutely terrible, by Hasen el Judy " -- http://harmful.cat-v.org/software/node.js
---
https://en.wikipedia.org/wiki/Systolic_array
---
summary of https://glyph.twistedmatrix.com/2014/02/unyielding.html :
" shared-state multithreading...are a bad idea...make local reasoning difficult...in a single-tasking, nonconcurrent system...When you’re looking at a routine that manipulates some state..., To imagine the different states, you need only to read the routine and imagine executing its instructions in order from top to bottom. This means that the number of instructions you must consider is n, where n is the number of instructions in the routine. By contrast, in a system with arbitrary concurrent execution - one where multiple threads might concurrently execute this routine with the same state - you have to read the method in every possible order, making the complexity nn. ... Those of you who actually use threads to write real software are probably objecting at this point. “Nobody would actually try to write free-threading code like this,” I can hear you complain, “Of course we’d use a lock or a queue to introduce some critical sections if we’re manipulating state.”
Mutexes can help mitigate this combinatorial explosion, but they can’t eliminate it, and they come with their own cost; you need to develop strategies to ensure consistent ordering of their acquisition. Mutexes should really be used to build queues, and to avoid deadlocks those queues should be non-blocking but eventually a system which communicates exclusively through non-blocking queues effectively becomes a set of communicating event loops, and its problems revert to those of an event-driven system; it doesn’t look like regular programming with threads any more. ... But even if you build such a system, if you’re using a language like Python (or the ones detailed above) where modules, classes, and methods are all globally shared, mutable state, it’s always possible to make an error that will affect the behavior of your whole program without even realizing that you’re interacting with state at all. ... What are you going to do instead?
There’s a lot of debate over the best way to do “asynchronous” programming - that is to say, “not threads”, four options are often presented.
Straight callbacks: Twisted’s IProtocol, JavaScript’s on<foo> idiom, where you give a callback to something which will call it later and then return control to something (usually a main loop) which will execute those callbacks,
“Managed” callbacks, or Futures: Twisted’s Deferred, JavaScript’s Promises/A[+], E’s Promises, where you create a dedicated result-that-will-be-available-in-the-future object and return it for the caller to add callbacks to,
Explicit coroutines: Twisted’s @inlineCallbacks, Tulip’s yield from coroutines, C#’s async/await, where you have a syntactic feature that explicitly suspends the current routine,
and finally, implicit coroutines: Java’s “green threads”, Twisted’s Corotwine, eventlet, gevent, where any function may switch the entire stack of the current thread of control by calling a function which suspends it.One of these things is not like the others; one of these things just doesn’t belong.
...
Options 1-3 are all ways of representing the cooperative transfer of control within a stateful system. They are a semantic improvement over threads. Callbacks, Futures, and Yield-based coroutines all allow for local reasoning about concurrent operations.
So why does option 4 even show up in this list? ... it’s a bit of a distraction from the much bigger advantage of event-driven programming, which is simply that it’s easier to write programs at scale, in both senses (that is, programs containing lots of code as well as programs which have many concurrent users). ... A system that presents “implicit coroutines” – those which may transfer control to another concurrent task at any layer of the stack without any syntactic indication that this may happen – are simply the dubious optimization by itself. ... When you look at the implementation of a potentially concurrent routine written using callbacks or yielding coroutines, you can visually see exactly where it might yield control, either to other routines, or perhaps even re-enter the same routine concurrently. If you are using callbacks – managed or otherwise – you will see a return statement, or the termination of a routine, which allows execution of the main loop to potentially continue. If you’re using explicit coroutines, you’ll see a yield (or await) statement which suspends the coroutine ... ((example bug:)) ... As it happens, this is the same variety of example Guido van Rossum gives when he describes why chose to use explicit coroutines instead of green threads for the upcoming standard library asyncio module, born out of the “tulip” project, so it's happened to more than one person in real life. ... Let’s say we have this program:
def transfer(amount, payer, payee, server): if not payer.sufficient_funds_for_withdrawl(amount): raise InsufficientFunds?() log("{payer} has sufficient funds.", payer=payer) payee.deposit(amount) log("{payee} received payment", payee=payee) payer.withdraw(amount) log("{payer} made payment", payer=payer) server.update_balances([payer, payee])
In a world without concurrency, this is of course correct. ...
But if we were to run transfer with the same two accounts in an arbitrary number of threads simultaneously, it is (obviously, I hope) wrong. One thread could update a payer’s balance below the funds-sufficient threshold after the check to see if they’re sufficient, but before issuing the withdrawl.
So, let’s make it concurrent, in the PEP 3156 style. That update_balances routine looks like it probably has to do some network communication and block, so let’s consider that it is as follows:
@coroutine def transfer(amount, payer, payee, server): if not payer.sufficient_funds_for_withdrawl(amount): raise InsufficientFunds?() log("{payer} has sufficient funds.", payer=payer) payee.deposit(amount) log("{payee} received payment", payee=payee) payer.withdraw(amount) log("{payer} made payment", payer=payer) yield from server.update_balances([payer, payee])
...now let’s make another, subtler code change: our hypothetical operations team has requested that we put all of our log messages into a networked log-gathering system for analysis. A reasonable request, so we alter the implementation of log to write to the network.
Now, what will we have to do to modify the green-threaded version of this code? Nothing! ... ((but, by contrast, in the cooperative coroutine version:)) In order to update this routine for a non-blocking version of log, we had to type a yield keyword between the sufficient_funds_for_withdrawl check and the withdraw call, between the deposit and the withdraw call, and between the withdraw and update_balances call. If we know a little about concurrency and a little about what this program is doing, we know that every one of those yield froms are a potential problem. If those log calls start to back up and block, a payer may have their account checked for sufficient funds, then funds could be deducted while a log message is going on, leaving them with a negative balance....the mechanical act of typing these out is an opportunity to notice that something’s wrong, both now and later. Even if we get all the way through making the changes without realizing the problem, when we notice that balances are off, we can look only (reasoning locally!) at the transfer routine and realize, when we look at it, based on the presence of the yield from keywords, that there is something wrong with the transfer routine itself, regardless of the behavior of any of the things it’s calling.
Tedious as it may be, the asynchronousness of an individual function is, in fact, something that all of its callers must be aware of, just as they must be aware of its arguments and its return type.
In fact you are changing its return type: in Twisted, that return type would be Deferred, and in Tulip, that return type is a new flavor of generator. This new return type represents the new semantics that happen when you make a function start having concurrency implications.
Haskell does this as well, by embedding the IO monad in the return type of any function which needs to have side-effects. This is what certain people mean when they say Deferreds are a Monad.
The main difference between lightweight and heavyweight threads is that it is that, with rigorous application of strict principles like “never share any state unnecessarily”, and “always write tests for every routine at every point where it might suspend”, lightweight threads make it at least possible to write a program that will behave deterministically and correctly, assuming you understand it in its entirety. When you find a surprising bug in production, because a routine that is now suspending in a place it wasn’t before, it’s possible with a lightweight threading system to write a deterministic test that will exercise that code path. With heavyweight threads, any line could be the position of a context switch at any time, so it’s just not tractable to write tests for every possible order of execution. " -- https://glyph.twistedmatrix.com/2014/02/unyielding.html
another post making similar points is https://glyph.twistedmatrix.com/2012/01/concurrency-spectrum-from-callbacks-to.html
---
" smsm42 4 days ago [-]
> the mental model works better for asynchrony; instead of describing a series of steps to follow, and treating the interrupt as the exception, you describe the processes that should be undertaken in certain circumstances
I could never understand how this works better as a mental model. Say you ask somebody to buy you a gadget in a store they don't know. What do you do tell them:
a) "drive in your car on this street, turn left on Prune street, turn right on Elm street, the store will be after the second light. Go there, find "Gadgets" isle, on the second shelf in the middle there would be a green gadget saying "Magnificent Gadget", buy it and bring it home"
or:
b) when you find yourself at home, go to car. When you find yourself in the car, if you have a gadget, drive home, otherwise if you're on Elm street, drive in direction of Prune Street. If you're in the crossing of Elm street and Prune street, turn to Prune street if you have a gadget but to Elm street if you don't. When you are on Prune street, count the lights. When the light count reaches two, if you're on Prune street, then stop and exit the vehicle. If you're outside the vehicle and on Prune street and have no gadget, locate store and enter it, otherwise enter the vehicle. If you're in the store and have no gadget then start counting shelves, otherwise proceed to checkout. Etc. etc. - I can't even finish it!
I don't see how "steps to follow" is not the most natural mental model for humans to achieve things - we're using it every day! We sometimes do go event-driven - like, if you're driving and somebody calls, you may perform event-driven routine "answer the phone and talk to your wife" or "ignore the call and remember to call back when you arrive", etc. But again, most of these routines will be series of steps, only triggered by an event.
reply
" -- [5]
---
" Communicating sequential processes (Go, PHP+MySql?) makes IO have a modestly simpler synchronous syntax at the cost of communicating between I/O operations much more complex (sending a message to a port or performing some sort of transaction instead of just assigning to a value). It's a tradeoff. " -- [6]
---
difference between actors and CSP:
both are 'message passing' models as opposed to 'shared state'
"The difference between the CSP program and the Actor system is that the Actor Z does not get messages using a guarded choice command from multiple channels. Instead it processes messages in arrival ordering, and by the laws for Actor systems, the stop message is guaranteed to arrive." -- [7]
"
CSP:
Actors:
then there's also pi-calculus "The π-calculus, partially inspired by the Actor model as described by Milner above, introduced dynamic topology into the process calculi by allowing dynamic creation of processes and for the names to be passed among different processes. However, the goal of Milner and Hoare to attain an algebraic calculus led to a critical divergence from the Actor model: communication in the process calculi is not direct as in the Actor model but rather indirectly through channels " [8]
related: https://www.quora.com/How-are-Akka-actors-different-from-Go-channels
--
CSP link:
https://en.wikipedia.org/wiki/Communicating_sequential_processes#Primitives
"The concurrency primitives of CSP were input, output, guarded commands, and parallel composition whereas the Actor model is based on asynchronous one-way messaging." [9]
---
Actor implementation: Akka
---
Petri nets
---
https://en.wikipedia.org/wiki/Calculus_of_communicating_systems
---
"Leading examples of process calculi include CSP, CCS, ACP, and LOTOS.[1] More recent additions to the family include the π-calculus, the ambient calculus, PEPA, the fusion calculus and the join-calculus." [10]
"CCS, CSP, and ACP constitute the three major branches of the process calculi family: the majority of the other process calculi can trace their roots to one of these three calculi" [11]
"Various process calculi have been studied and not all of them fit the paradigm sketched here. The most prominent example may be the ambient calculus. " [12]
---
"The use of channels for communication is one of the features distinguishing the process calculi from other models of concurrency, such as Petri nets and the Actor model (see Actor model and process calculi)." [13]
---
" Here is how I think Erlang works. I believe Akka is very similar.
Each process has a single mailbox. Messages are put into the receiver's mailbox by the sender, and fetched by the receiver using pattern matching. This matching process can change message ordering in the sense that the oldest message in a mailbox may not match, but a younger one does. In this case the younger one is consumed first. Other than that, message ordering is preserved.
With this in mind, the asynchronous π -calculus extended with input pattern matching input from buffer describes Erlang (and hence Akka) semantics accurately, although one needs to do a bit of work in the encoding, since the π-calculus doesn't have the restriction to single channels per process. However, one usually doesn't want an encoding, but rather a calculus that models the target system directly. Such a calculus exists, and it's called Featherweight Erlang. It is by Mostrous and Vasconcelos. Their paper focusses on typing, but you can ignore that and just look at the untyped calculus in Section 3. " -- [14]
---
https://en.wikipedia.org/wiki/Parallel_programming_model
---
https://en.wikipedia.org/wiki/Barrier_(computer_science)
---
https://en.wikipedia.org/wiki/Rendezvous_(Plan_9)
---
" There is one important downside to the CSP way ((compared to Actors)) of networking concurrent behaviour:
Any network of goroutines that has some mutual dependency may deadlock. The developer must be aware of this and code so that deadlock is eliminated; this involves identifying mutual dependencies and altering them in some way (there are several well-known techniques, the easiest of these being to use a pure client-server pattern, which is known to be deadlock-free).
But consider what happens if a deadlocking network of goroutines is converted to Akka. The non-blocking communications means that deadlock won't happen - but how can we be sure that the queues will not overflow? There is a direct equivalence between deadlock and exhaustion of not-so-infinite buffers. " -- https://www.quora.com/How-are-Akka-actors-different-from-Go-channels
---
https://en.wikipedia.org/wiki/Systolic_array
---
https://en.wikipedia.org/wiki/Futex
---
some history of CSP:
https://swtch.com/~rsc/thread/
---
" riffraff 1605 days ago [-]
AFAIR kilim guarantees statically checked safety, exactly because "messages" that can be sent across actor borders have guaranteed properties of being aliaseable^mutable. "
---
" A Fiber is a lightweight thread that uses cooperative multitasking instead of preemptive multitasking. A running fiber must explicitly "yield" to allow another fiber to run, which makes their implementation much easier than kernel or user threads.
A Coroutine is a component that generalizes a subroutine to allow multiple entry points for suspending and resuming execution at certain locations. Unlike subroutines, coroutines can exit by calling other coroutines, which may later return to the point where they were invoked in the original coroutine.
A Green Thread is a thread that is scheduled by a virtual machine (VM) instead of natively by the underlying operating system. Green threads emulate multithreaded environments without relying on any native OS capabilities, and they are managed in user space instead of kernel space, enabling them to work in environments that do not have native thread support. " -- http://programmers.stackexchange.com/questions/254140/is-there-a-difference-between-fibers-coroutines-and-green-threads-and-if-that-i
---
concurrency vs parallel
Different people have different definitions. One common one is that concurrent processes may have their steps arbitrarily interleaved but may not necessarily ever have one step from each process executing simultaneously, whereas parallelism admits actual simultaneous execution.
An example is seen in the case of multitasking on a single CPU vs. on multiple CPUs. On a computer with a single CPU, you can still 'multitask', that is, run two separate threads of execution, by first executing the first task a little bit, then executing the second task a little bit, then executing a little more of the first task, etc. The two tasks are executing concurrently, but not in parallel; there is no chance that a step in the first task and a step in the second change will actually execute simultaneously, because you only have one CPU. By contrast, on a machine with two CPUs, you could have one CPU executing the first thread while the second CPU is executing the second thread. This means that the two threads can actually execute simultaneously.
Other people might have different definition of these terms. One alternate definition says concurrency is a property of the program (the program is broken into multiple threads which can tolerate interleaved or simultaneous execution), while parallelism is a property of the hardware (there are actually multiple CPUs). Some people use the phrase 'truly concurrent' to denote simultaneous execution (as opposed to merely interleaved execution).
---
"
Process: OS-managed (possibly) truly concurrent, at least in the presence of suitable hardware support. Exist within their own address space.
Thread: OS-managed, within the same address space as the parent and all its other threads. Possibly truly concurrent, and multi-tasking is pre-emptive.
Green Thread: These are user-space projections of the same concept as threads, but are not OS-managed. Probably not truly concurrent, except in the sense that there may be multiple worker threads or processes giving them CPU time concurrently, so probably best to consider this as interleaved or multiplexed.
Protothreads: I couldn't really tease a definition out of these. I think they are interleaved and program-managed, but don't take my word for it. My sense was that they are essentially an application-specific implementation of the same kind of "green threads" model, with appropriate modification for the application domain.
Fibers: OS-managed. Exactly threads, except co-operatively multitasking, and hence not truly concurrent.
Coroutines: Exactly fibers, except not OS-managed.
Goroutines: They claim to be unlike anything else, but they seem to be exactly green threads, as in, process-managed in a single address space and multiplexed onto system threads. Perhaps somebody with more knowledge of Go can cut through the marketing material." -- [15]
"Threads scheduled by user-mode code are what’s known as lightweight threads; in Quasar (as well as in some other languages) they are called fibers."- -http://blog.paralleluniverse.co/2014/02/06/fibers-threads-strands/
(as you can see, different people define 'fibers' differently)
---
a quick overview of some of the stuff in here:
Concurrency paradigms can be deterministic or non-deterministic
A race condition is (often undesirable) non-deterministic program behavior resulting from concurrency. When programming in a non-deterministic concurrency paradigm, race conditions are possible, and the programmer must use patterns, analysis, and discipline to avoid, detect, and eliminate undesirable race conditions.
Threads and stuff like them (there is no consensus on terminology):
shared memory vs none; scheduled vs yield to target; preemptive vs cooperative (have to yield) vs semipreemptive (wont preempt in tight loop). preemptive or semipreemptive implies scheduled.
Processes: no shared memory between different processes, scheduled, preemptive
Threads: mb shared memory, scheduled, preemptive. Defined this way, processes are special cases of threads (threads with no shared memory), note however that in many systems you can have many threads within each process.
Fibers: scheduled? (different people disagree on the definition here; many define it the same as a coroutine, but for some, something that explicitly yields to a scheduler is a fiber), cooperative (have to yield) [16] [17] [18]