Bag of tasks

Best illustrated by 2_2/cp/lec/03/Trapezium.scala.

• [3.32] Controller has bag of tasks, distributing to workers.
  • Faster workers can do more tasks.
• [3.36] Receiving results from workers can be separate process.

Client/server

• [5.2] Server repeatedly handles requests from clients.
• [5.3, 5.20] Option[Response] or wait till available (beware deadlock).
• [5.17] Client can create ephemeral reply channel.
• [5.26] Buffered channels enable useful work while client waiting.
• [5.29] Multiple channels vs single channel with multiple types.

Interacting peers

• [5.6] Reason about
  • Invariants
  • Total messages
  • Maximum length (totally-ordered) chain of \(\prec\) messages (rounds)
• [5.7] Centralized pattern (star), [5.14] fully-connected/symmetric, [5.19] ring topology, [5.28] tree/heap topology.

Others

• [11.3] Recursive parallelism.
  • Calculate directly for base case, recurse by spawning parallel processes.
  • [11.6] Need to limit number spawned.
  • [11.9] Also consider bag-of-tasks with replacement.
• [11.10] Parallel collections as in Scala.
• [11.11] Competition parallel.
  • In problems where different algorithms perform well/badly in different situations, run in parallel and use result of first to finish.
• [11.12] Task-parallel.
• [11.14] MapReduce.
• [11.18] Futures where value computed while execution continues, e.g. Scala.
• [11.21] Lock-free programming allowing race conditions.