Classification of concurrency patterns

[Jay Nelson]

In an earlier thread I alluded to not understanding how to express  
concurrency patterns.  My belief was that they are more complicated  
to categorize and differentiate than design patterns of OO because  
they cross the architecture rather than just a single software  
module.  I wasn't sure what elements were necessary to describe them  
and think that is starting to show in the discussion on this thread.  
I think it will take a little analysis and negotiation to arrive at a  
reasonable description.

Thus far, this thread has mainly enumerated specific instances of  
architectures without looking at the attributes and features of the  
entire problem space with a goal of identifying the measures which  
would differentiate approaches.  A proper analysis should result in  
some as yet uncommon or undiscovered concurrency patterns by filling  
in missing examples on a diagram of possibilities.

To make progress we need to look at the range of features needed to  
describe the domain of concurrency patterns.  Here are some key  
attributes of a concurrent architecture that I can think of offhand,  
along with measures of each that could be used to classify them  
(considering only process-based concurrency), the main point being  
different ways of describing the processes that participate in a  
pattern:

Number of processes
    - One =>  all OO design patterns fall in here
    - Few => typically task oriented processes with dedicated  
functionality
    - Dozens => typically partitioned systems with worker pools
    - Many => event driven spawning or grid-like computations
    - Dynamic => distributed hashes, communal participatory  
computation (SETI)

Lifetime of processes
    - Static/Infinite => dedicated services essential to working system
    - Enduring => self-recovering stable functions (reconnect on  
disconnect),
                               resource pool workers
    - Temporary => services needed on demand, caching
    - Ephemeral => reactive workers or task-oriented computation
    - Dormant => resource conserving (hibernation)

Scheduling of processes
    - Once => static service
    - Periodic => cron-like services, Comet / AJAX polling
    - On Demand => event-driven services

Static Organization of processes
    - Network computation topologies => hypercube, star, mesh, ring,  
etc.
    - Functional relationships => supervisors, serial servers, pub/ 
sub, pool
    - Partitioning => isolation of failure, allocation of resources

Dynamic Organization of processes
    - Load adaptive => efficient resource allocating services
    - Demand driven => swarm computing
    - Migratory => mobile agents, resource discovery, continuation  
patterns
    - Coordinated => failover / takeover, command and control, leader  
election
    - Participatory => distributed hash, SETI

Data flow through processes
    - Static => networked dataflow, traditional partitioned
    - Affinity-based => data flocking for efficient computation
    - Routed / Queue distributed => pub/sub, worker pools
    - Activation propagation => traditional dataflow, pipeline
    - Central distributed => serial server, rendezvous
    - Scatter / Gather => map reduce, grid
    - Network overlay => SIMD grid

Location of processes
    - Static => traditional concurrency
    - Dynamic => mobile agents, adaptive load systems
    - Admin directed => command and control concurrency
    - Resource associated => adaptive load, efficient data computation

Process-Mapped Resource Access
    - Continuous => traditional
    - Repeated static => pool workers
    - Repeated dynamic => event driven, load adaptive
    - One-shot => caching, dataflow, tcp proxy

As you can see, the OO patterns eliminate a few dimensions of the  
range of possibilities and therefore are presumably easier to describe.

Not all of these features are necessary simultaneously to classify  
the entire domain (as seen by some of my overlapping descriptions),  
arguments exist for selective sets of them or combinations.  I think  
that because a concurrent system is more complex and dynamic, it is  
necessary to describe an architecture with both static attributes  
(typically called "the architecture") and dynamic attributes (process  
lifecycle, dataflow) over time.

I think this is a highly relevant thread, and an important topic for  
the Concurrency Oriented Programming Language (COPL) community to  
come to agreement on.  Doing so will advance software and training at  
the pace of the multi-core options that are becoming available.  I  
think this outline could form the basis of a collaborative wiki to  
discover a better classification hierarchy.

jay