Flujo sincrónico dentro de un árbol de procesos concurrentes no deterministas

propuesto por josejuan

Si un proceso inicia procesos concurrentes no deterministas y éstos a su vez inician otros, podemos "dibujar" el árbol de procesos generado y el orden en el que ésto ocurre. Se pide programar un entorno (¿API?) que permita recuperar de forma sincrónica cierto producto (ej. un log) de los procesos concurrentes.

Enunciado
Si un proceso inicia procesos concurrentes no deterministas y éstos a su vez inician otros, podemos "dibujar" el árbol de procesos generado y el orden en el que ésto ocurre. Se pide programar un entorno (¿API?) que permita recuperar de forma sincrónica cierto producto (ej. un log) de los procesos concurrentes.

Por ejemplo, sea el árbol:
  P0
   |
   +-- P1
   |    |
   |    +-- P11
   |    |
   |    +-- P12
   |
   +-- P2


A la acción sincronizada podemos llamarla WriteLog (o similar), aunque puede tratarse de "cualquier cosa" (los detalles pueden depender de muchos factores).

Entonces, si pedimos que cada uno de ellos impriman (llamen a WriteLog) en orden (el orden dentro del árbol) su nombre, la salida sería con independencia de lo que tarde en ejecutarse cada proceso (ej. aunque P2 sea mucho más rápido que el resto):

P0
P1
P11
P12
P2


A modo de ejemplo, supongamos que queremos implementar una versión paralela del siguiente fibonacci:
fibonacci(n) {
  WriteLog n
  if n == 0 || n == 1
  then
    devolver 1
  else
    devolver (fibonacci(n - 1) + fibonacci(n - 2))
}


Este problema ha sido inspirado en

http://fpish.net/blog/anton.tayanovskyy/id/3722/201426-deterministic-parallelism-with-logging

NOTA el problema de paralelización determinista es mucho más amplio que el resuelto en este desafío :P

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

2 Soluciones

Dar mi solución

Dar mi solución