Structure of Message-Passing Programs

• Message-passing programs are often written using the asynchronous or loosely synchronous paradigms.
• In the asynchronous paradigm, all concurrent tasks execute asynchronously.
  • However, such programs can be harder and can have non-deterministic behavior due to race conditions.
• Loosely synchronous programs are a good compromise between two extremes.
  • In such programs, tasks or subsets of tasks synchronize to perform interactions.
  • However, between these interactions, tasks execute completely asynchronously.
• In its most general form, the message-passing paradigm supports execution of a different program on each of the $p$ processes.
• This provides the ultimate flexibility in parallel programming, but makes the job of writing parallel programs effectively unscalable.

• For this reason, most message-passing programs are written using the single program multiple data (SPMD).
• In SPMD programs the code executed by different processes is identical except for a small number of processes (e.g., the "root" process).
• In an extreme case, even in an SPMD program, each process could execute a different code (many case statements).
• But except for this degenerate case, most processes execute the same code.
• SPMD programs can be loosely synchronous or completely asynchronous.