En este tipo de arquitectura todos los procesos (workers) envían su valor local al procesador central (coordinador), este suma los N datos y reenvía la información de la suma al resto de los procesos.
Por lo tanto se ejecutan 2(N-1) mensajes. Si el procesador central dispone de una primitiva broadcast, se reduce a N mensajes.

En cuanto a la performance global, los mensajes al coordinador se envían casi al mismo tiempo.
Estos se quedarán esperando hasta que el coordinador termine de computar la suma y envíe el resultado a todos.

chan valor(INT);
resultados[n](INT suma);

Process P[0]{              // coordinador, v está inicializado
    INT v; INT sum = 0;
    sum = sum + v;
    for (i = 1 to n-1){
        receive valor(v);
        sum = sum + v;
    }
    for (i = 1 to n-1)
        send resultado[i](sum);
}

process P[i = 1 to n-1]{   // worker, v está inicializado
    INT v; INT sum;
    send valor(v);
    receive resultado[i](sum);
}

🧩 Supuestos

De nuevo usamos n = 4 procesos:

🎯 Objetivo

• P[0] recibe los valores de todos los procesos.
• Suma: 2 + 3 + 5 + 7 = 17.
• Luego envía la suma global de vuelta a todos los workers.

🚀 Ejecución paso a paso

📨 Fase 1: Envío de los valores al coordinador

📤 Fase 2: Coordinador difunde la suma

✅ Resultado final

💬 Observaciones

• Total de mensajes: 2(n - 1) = 2(4 - 1) = 6 mensajes
• Con broadcast: solo n = 4 mensajes (1 de cada worker al coordinador, 1 broadcast de vuelta).
• Buena performance en tiempo, porque los workers envían todos al mismo tiempo.
• Pérdida de paralelismo en el cómputo: solo el coordinador trabaja, los demás esperan.
• Punto único de falla: si P[0] se cae, el sistema no funciona.

Se tiene un anillo donde P[i] recibe mensajes de P[i-1] y envía mensajes a P[i+1]. P[n-1] tiene como sucesor a P[0]. El primer proceso envía su valor local ya que es el único que conoce.

Este esquema consta de dos etapas:

1. Cada proceso recibe un valor y lo suma con su valor local, transmitiendo la suma local a su sucesor.
2. Todos reciben la suma global.

P[0] debe ser algo diferente para poder “arrancar” el procesamiento: debe enviar su valor local ya que es el único que conoce. Se requerirán 2(n-1) mensajes.

A diferencia de la solución centralizada, esta reduce los requerimientos de memoria por proceso pero tardara más en ejecutarse, por más que el número de mensajes requeridos sea el mismo. Esto se debe a que cada proceso debe esperar un valor para computar una suma parcial y luego enviársela al siguiente proceso; es decir, un proceso trabaja por vez, se pierde el paralelismo.

chan valor[n](suma);

process p[0] {
    INT v;
    INT suma = v;
    send valor[1](suma);
    receive valor[0](suma);
    send valor[1](suma);
}

process p[i = 1 to n-1] {
    INT v;
    INT suma;
    receive valor[i](suma);
    suma = suma + v;
    send valor[(i + 1) mod n](suma);
    receive valor[i](suma);
    if (i < n - 1)
        send valor[i + 1](suma);
}

El objetivo es que todos los procesos conozcan la suma total, que es 2 + 3 + 5 + 7 = 17.

🧠 Etapa 1: Suma parcial hacia adelante

🧠 Etapa 2: Difusión de la suma global

✅ Resultado final

Todos los procesos conocen el valor total 17.

💬 Observaciones

• Cantidad de mensajes: 2(n - 1) = 2(4 - 1) = 6 mensajes, como indica tu descripción.
• Secuencialidad: cada proceso espera su turno para sumar → no hay paralelismo.
• P[0] es especial, porque inicia la suma y también es el primero que difunde la suma global.

Todos los procesos ejecutan el mismo algoritmo. Existe un canal entre cada par de procesos.
Cada uno transmite su dato local v a los n-1 restantes. Luego recibe y procesa los n-1 datos que le faltan, de modo que en paralelo toda la arquitectura está calculando la suma total y tiene acceso a los n datos.

Se ejecutan n(n-1) mensajes. Si se dispone de una primitiva de broadcast, serán n mensajes.
Es la solución más corta y sencilla de programar, pero utiliza el mayor número de mensajes si no hay broadcast.

chan valor[n](INT);

process p[i=0 to n-1] {
    INT v;
    INT nuevo, suma = v;
    
    for (k=0 to n-1 st k <> i)
        send valor[k](v);
        
    for (k=0 to n-1 st k <> i) {
        receive valor[i](nuevo);
        suma = suma + nuevo;
    }
}

🧩 Supuestos

Usamos de nuevo n = 4 procesos y valores locales:

🚀 ¿Qué hace cada proceso?

• Cada proceso envía su valor a los otros 3 (n-1).
• Luego, recibe los 3 valores que le faltan, y los suma.
• Esto se hace en paralelo, es decir, todos los procesos trabajan al mismo tiempo.

📊 Ejecución paso a paso

Fase 1: Envío

Fase 2: Recepción y suma

Cada proceso recibe 3 valores y los suma con el propio:

✅ Resultado final

Todos conocen la suma global 17.

💬 Observaciones

• Total de mensajes: n(n-1) = 4 × 3 = 12 mensajes
• Todos trabajan en paralelo → alta velocidad
• Pero: requiere muchos canales y mensajes
• Si tuvieras broadcast, solo necesitarías n mensajes (1 por proceso).

Se tiene una red de procesadores (nodos) conectados por canales de comunicación bidireccionales. Cada nodo se comunica directamente con sus vecinos. Si un nodo quiere enviar un mensaje a toda la red, debería construir un árbol de expansión de la misma, poniéndose a él mismo como raíz.

El nodo raíz envía un mensaje por broadcast a todos los hijos, junto con el árbol construido. Cada nodo examina el árbol recibido para determinar los hijos a los cuales deben reenviar el mensaje, y así sucesivamente.

Se envían n - 1 mensajes, uno por cada padre/hijo del árbol.

🧩 Supuestos

• Tenemos n = 7 nodos numerados del 0 al 6.
• Se construye un árbol de expansión para propagar un mensaje, con el nodo 0 como raíz.
• El árbol tiene esta estructura (por simplicidad):

        0
      / | \
     1  2  3
        |   \
        4    5
              \
               6

🎯 Objetivo

Difundir un mensaje desde el nodo raíz (0) hacia todos los demás nodos usando el árbol.

🚀 Ejecución paso a paso

✅ Resultado final

Todos los nodos reciben el mensaje, usando solo n - 1 = 6 mensajes.

💬 Observaciones

• Mensajes totales: n - 1 = 6
• Es la forma más eficiente si ya tenemos el árbol.
• Permite paralelismo: varios nodos pueden reenviar a la vez.
• Ideal para redes distribuidas con vecindades limitadas (no totalmente conectadas).
• Si se necesita hacer una suma global, se puede hacer un recorrido postorden (bottom-up), y luego difundir el resultado (top-down).

La granularidad de una aplicación concurrente o paralela se refiere a la relación entre el tiempo dedicado al cómputo y el tiempo dedicado a la comunicación entre procesos o hilos.

• Si una aplicación realiza mucho cómputo local antes de necesitar comunicarse, se dice que tiene grano grueso.
• Si, por el contrario, realiza frecuentes comunicaciones con poco cómputo entre medio, se dice que tiene grano fino.

Esta característica es clave para el diseño y rendimiento de programas paralelos, ya que:

• Grano grueso suele ser más eficiente en arquitecturas donde la comunicación es costosa.
• Grano fino puede aprovechar mejor arquitecturas con alta velocidad de comunicación o memoria compartida eficiente.

🔧 Resumen:

La granularidad es la proporción entre el cómputo y la comunicación en una aplicación. Afecta cómo se adapta el programa a una arquitectura paralela, diferenciándose entre grano fino (más comunicación) y grano grueso (más procesamiento local).

🔎 Probamos combinaciones buscando x = 9

❌ Caso 1: P1 completo → P2 → P3

// P1 ejecuta completo:
x = 0 → entra al if
y = 4*0 + 2 = 2
x = y + 2 + x = 2 + 2 + 0 = 4

// P2 ejecuta:
x = 4 + 1 = 5

// P3 ejecuta:
x = 10 * 5 + 1 = 51 → ❌ no es 9

❌ Caso 2: P2 → P3

// P2 ejecuta:
x = 0 + 1 = 1

// P3 ejecuta:
x = 10 * 1 + 1 = 11 → ❌

❌ Caso 3: P3 → P2

// P3 ejecuta:
x = 10 * 0 + 1 = 1

// P2 ejecuta:
x = 1 + 1 = 2 → ❌

❌ Caso 4: P3 con x = 2

// Supongamos que x llega a 2 por P2 → P2
x = 0 + 1 = 1
x = 1 + 1 = 2

// P3 ejecuta:
x = 10 * 2 + 1 = 21 → ❌

❌ Conclusión del inciso a)

✅ x = 9 no se puede alcanzar, porque:

• P1 produce como mucho x = 4
• P2 suma 1 cada vez
• P3 hace x = 10 * x + 1, lo cual siempre da un número impar mayor (nunca 9)

✅ Respuesta final del inciso a):
FALSO – No existe ninguna secuencia de ejecución posible que lleve a x = 9.

✔️ Verdadero

Una posible traza:

1. P1 ejecuta parcialmente: y := 4 * 0 + 2 = 2
2. P3 ejecuta: x := 0 * 8 + 0 * 2 + 1 = 1
3. P2 ejecuta: x := 1 + 1 = 2
4. P1 finaliza: x := y + 2 + x = 2 + 2 + 2 = 6

Por lo tanto, es posible llegar a x = 6.

✔️ Verdadero

Una traza simple:

1. P2 ejecuta: x := 1
2. P3 ejecuta: x := 10 * 1 + 1 = 11

P1 no entra porque x ≠ 0.
Resultado final: x = 11 → válido.

✔️ Verdadero

Análisis por casos:

• y = 0: si P1 no ejecuta el cuerpo del if (porque x ≠ 0 al momento de evaluarlo)
• y = 2: si P1 ejecuta el if con x = 0, y aún no ha sido modificado
• y = 6: si x = 1 al momento de ejecutar y := 4 * x + 2
• y = 10: si x = 2 cuando se evalúa la asignación

Como la asignación de y depende directamente del valor de x, que puede ser modificado por otros procesos antes de ejecutarla, solo esos cuatro valores son posibles.

Claramente, a partir de p = 2, se observa que la eficiencia E₁ = 1/p es mayor que la eficiencia E₂ = 1/p². Analicemos algunos valores:

• Para p = 1:
  E₁ = 1/1 = 1  E₂ = 1/1 = 1
• Para p = 2:
  E₁ = 1/2 = 0.5  E₂ = 1/4 = 0.25
• Para p = 3:
  E₁ = 1/3 ≈ 0.33  E₂ = 1/9 ≈ 0.11

Como se puede apreciar, E₁ siempre es mayor que E₂ a partir de p = 2, y ambas eficiencias decrecen al aumentar el número de procesadores.

Conclusión:
La solución con E = 1/p se comporta más eficientemente que la de E = 1/p², ya que decrece más lentamente. Sin embargo, ninguna de las dos escala bien cuando p crece mucho, ya que ambas tienden a eficiencia cero.

No, la solución no funciona correctamente con la disciplina de señalización Signal and Continue (S&C).

Bajo esta disciplina, cuando un proceso realiza un signal, continúa ejecutando dentro del monitor, y el proceso que fue despertado es enviado a la cola de listos (ready queue) del sistema operativo. Esto implica que su reingreso al monitor depende de la política de planificación del sistema, y no se garantiza que sea el próximo en ejecutarse.

En consecuencia, un proceso con menor tiempo (según la política Shortest Job Next) podría quedar retrasado si otro proceso ingresa antes al monitor. Por lo tanto, el orden de ejecución no refleja necesariamente la prioridad establecida por el parámetro tiempo, y no se cumple el objetivo del SJN.

Respuesta de un random

Con S&C un proceso que es despertado para poder seguir ejecutando es pasado a la cola de ready en cuyo caso su orden de ejecución depende de la política que se utilice para ordenar los procesos en dicha cola. Puede ser que sea retrasado en esa cola permitiendo que otro proceso ejecute en el monitor antes que el por lo que podría no cumplirse el objetivo del SJN.

Sí, la solución funciona correctamente con la disciplina de señalización Signal and Wait (S&W).

En esta disciplina, cuando un proceso ejecuta un signal, cede inmediatamente el control del monitor al proceso que fue despertado, el cual continúa su ejecución justo después del wait. El proceso que hizo el signal pasa a la cola de listos y debe esperar su turno para volver a ingresar al monitor.

Esto garantiza que el proceso con menor tiempo (según la política Shortest Job Next) —que estaba esperando con prioridad— será efectivamente el próximo en acceder al recurso, evitando que otro proceso pueda adelantarse y violar el orden deseado.

Por lo tanto, la política SJN se respeta correctamente bajo Signal and Wait, ya que se mantiene el control sobre el orden de ejecución de los procesos en espera.

📘 Definiciones complementarias:

• Signal and Continue: El proceso que ejecuta el signal continúa usando el monitor, mientras que el proceso despertado debe competir por reingresar al monitor.
• Signal and Wait: El proceso que ejecuta el signal cede el monitor al proceso despertado, que continúa su ejecución justo después del wait.

No, el programa no funciona correctamente en un entorno concurrente.

🔍 Justificación con secuencia de ejecución:

Supongamos que el buffer está lleno (ocupados = N). En ese momento:

1. El proceso P2 evalúa if (ocupados > 0), lo cual es verdadero.
2. Luego, P2 ejecuta ocupados := ocupados - 1, pero aún no ha leído el dato del buffer.
3. Justo después, el proceso P1 evalúa su condición if (ocupados < N), que ahora también es verdadera, ya que P2 lo acaba de decrementar.
4. Entonces, P1 escribe en el buffer un nuevo valor, sobrescribiendo el dato que P2 todavía no alcanzó a leer.

⚠️ Como resultado, P2 pierde el dato original y lee un valor nuevo que no era el que debía consumir. Esto genera una condición de carrera (race condition) y un error de sincronización.

✅ Solución propuesta:

Para evitar este problema, es necesario postergar el decremento de ocupados en P2 hasta después de leer el valor del buffer, asegurando que el dato se consuma correctamente antes de liberar el espacio.

✔️ Código corregido de P2

if (ocupados > 0) then
begin
    elemento_a_sacar := buffer;
    ocupados := ocupados - 1;
end;

Con esta corrección, P1 no podrá ingresar hasta que P2 haya terminado de leer el valor, manteniendo la coherencia del estado del buffer.

🧠 Nota adicional:

Este tipo de errores son comunes cuando no se usa un mecanismo de sincronización explícito, como semáforos, monitores o exclusión mutua. En un sistema real, lo ideal sería proteger el acceso al buffer con algún tipo de región crítica o control de concurrencia.

✅ Estoy de acuerdo con José.

Aunque las instrucciones sean atómicas, el programa no es seguro concurrentemente, ya que existen interleavings (intercalaciones de ejecución) posibles que generan un comportamiento incorrecto.

🔍 Ejemplo de secuencia de ejecución errónea:

1. El proceso P1 evalúa la condición if (cantidad = 0) → verdadera, y entra al begin.
2. P1 ejecuta la instrucción cantidad := cantidad + 1, pero aún no ha escrito en el buffer.
3. En ese momento, el proceso P1 se interrumpe, y P2 toma el control.
4. P2 evalúa if (cantidad > 0) → verdadera (porque cantidad ahora vale 1).
5. P2 ejecuta elemento_a_sacar := buffer, pero el buffer aún no fue actualizado por P1.
6. Como resultado, P2 lee un valor inválido o desactualizado del buffer.

⚠️ Problema identificado:

El hecho de que las instrucciones sean atómicas no garantiza la atomicidad de toda la sección crítica compuesta por múltiples instrucciones relacionadas entre sí.

✅ Modificación para que funcione correctamente:

Una forma de corregirlo es reordenar las instrucciones de P1, asegurando que el valor se escriba en el buffer antes de habilitar su lectura (es decir, antes de incrementar cantidad):

// P1 corregido:
if (cantidad = 0) then
begin
    buffer := elemento_a_agregar;
    cantidad := cantidad + 1;
end;

De este modo, si P2 observa que cantidad > 0, entonces es seguro asumir que el buffer ya contiene un valor válido para ser consumido.

🧠 Conclusión:

Estoy de acuerdo con José, porque:

• El código original permite que P2 lea un valor inválido si se interrumpe a P1 en el momento inadecuado.
• La solución requiere ajustar el orden de operaciones para garantizar consistencia en el acceso al buffer, incluso si cada instrucción individual es atómica.

P1 y P3 comienzan esperando a s1. Por ser un mutex, sólo puede continuar uno de ellos y no será interrumpido por el otro hasta liberar a s1.

Primer resultado

Si comienza P1:

• Asigna x=9
• luego incrementa s1 permitiendo que continúe P3.
• P3 asigna x=7 y señala s2.
• Esto habilita a P2 que estaba esperando.
• Si P2 continúa, intentará obtener s1 con lo cual se vuelve a bloquear volviendo el control a P3.
• En cualquier caso, P3 libera a s1 y termina.
• P2 es despertado, asigna x = 21 y termina.
• Valor final x=21.

Segundo y Tercer resultado

Si comienza P3:

• Asigna x = 1 y señala a s2.
• Esto habilita a P2 que estaba esperando.
• Si P2 continúa, intentará obtener s1 con lo cual se vuelve a bloquear volviendo el control a P3.
• Cuando P3 libera a s1, P1 y P2 pueden competir por él:
  • Si gana P1:
    • asigna x=1,
    • libera a s1 y termina;
    • finaliza P2 y asigna x = 3.
    • Valor final x=3.
  • Si gana P2:
    • asigna x=3,
    • libera a s1 y termina;
    • finaliza P1 y asigna x = 9.
    • Valor final x = 9.

P2 nunca puede comenzar la historia ya que espera un semáforo de señalización que sólo P3 señala. Cualquier historia en la que P2 esté antes de P3 es inválida. En todas las historias los semáforos terminan con los mismos valores con los que están inicializados.

// Ambos procesos ejecutan el mismo bucle:
for (i = 1 to K)
    N = N + 1;

✅ i) Valor final = 2K
Caso posible: ejecución secuencial sin interferencia.

Ejemplo (K = 3):

P1: N=0 -> 1 -> 2 -> 3
P2: N=3 -> 4 -> 5 -> 6
Resultado final: N = 6 = 2*K

❌ ii) Valor final = 2K + 2
Caso imposible.

Justificación:
Cada proceso ejecuta exactamente K incrementos. Como mucho se pueden hacer 2K sumas. No hay forma de hacer más sin ejecutar más iteraciones, lo cual no ocurre.

✅ iii) Valor final = K
Caso posible: interferencia total entre procesos. Se pisan las operaciones.

Ejemplo (K = 3):

N inicialmente = 0

Intercalado:
P1 lee N=0       // aún no actualiza
P2 lee N=0       // aún no actualiza
P1 escribe N=1
P2 escribe N=1   // pisa el valor anterior → se pierde un incremento

Repite este patrón durante las 3 iteraciones.

Resultado final: solo 3 incrementos efectivos → N = 3 = K

✅ iv) Valor final = 2
Caso posible: interferencia total y mal intercalado extremo.

Ejemplo (K = 3):

N = 0

P1 iteración 1: lee N=0
P2 iteración 1: lee N=0
P1 escribe N=1
P2 escribe N=1   → pisa a P1

P1 iteración 2: lee N=1
P2 iteración 2: lee N=1
P1 escribe N=2
P2 escribe N=2   → pisa a P1

Resultado final: N = 2

monitor Controlador_ListaEnlazada {
    int numSearchers = 0, numInserters = 0, numDeleters = 0;
    cond searchers, inserters, deleters;

    procedure pedir_Deleter() {
        while (numSearchers > 0 OR numInserters > 0 OR numDeleters > 0) {
            wait(deleters);
        }
        numDeleters = numDeleters + 1;
    }

    procedure liberar_Deleter() {
        numDeleters = numDeleters - 1;
        signal(inserters);
        signal(deleters);
        signal_all(searchers);
    }

    procedure pedir_Searcher() {
        while (numDeleters > 0) {
            wait(searchers);
        }
        numSearchers = numSearchers + 1;
    }

    procedure liberar_Searcher() {
        numSearchers = numSearchers - 1;
        if (numSearchers == 0 AND numInserters == 0) {
            signal(deleters);
        }
    }

    procedure pedir_Inserter() {
        while (numDeleters > 0 OR numInserters > 0) {
            wait(inserters);
        }
        numInserters = numInserters + 1;
    }

    procedure liberar_Inserter() {
        numInserters = numInserters - 1;
        signal(inserters);
        if (numSearchers == 0) {
            signal(deleters);
        }
    }
}

🧵 Procesos:

process Searchers[i = 1..S] {
    Controlador_ListaEnlazada.pedir_Searcher();
    <Realiza búsqueda en la lista>
    Controlador_ListaEnlazada.liberar_Searcher();
}

process Inserters[j = 1..I] {
    Controlador_ListaEnlazada.pedir_Inserter();
    <Inserta en la lista>
    Controlador_ListaEnlazada.liberar_Inserter();
}

process Deleters[k = 1..D] {
    Controlador_ListaEnlazada.pedir_Deleter();
    <Borra en la lista>
    Controlador_ListaEnlazada.liberar_Deleter();
}

🧠 Resumen: Monitor Controlador_ListaEnlazada

👥 Tipos de procesos:

• Searchers: pueden acceder concurrentemente, salvo que haya un Deleter.
• Inserters: acceden de a uno, pero pueden convivir con Searchers.
• Deleters: requieren exclusión total (no pueden ejecutarse junto a ningún otro proceso).

🔒 Comportamiento de sincronización:

• Searchers esperan si hay un Deleter.
• Inserters esperan si hay otro Inserter o un Deleter.
• Deleters esperan si hay cualquier otro proceso activo (Searcher o Inserter).
• Al liberar, se despiertan procesos bloqueados según condiciones.

✅ ¿Funciona correctamente? Sí, el monitor implementa correctamente las restricciones de sincronización para los tres tipos de procesos. Asegura exclusión mutua, convivencia segura y respeta la lógica de prioridades.

La criba de Eratóstenes es un algoritmo clásico para determinar cuáles números en un rango son primos. Supongamos que queremos generar todos los primos entre 2 y n. Primero, escribimos una lista con todos los números:

2 3 4 5 6 7 ... n

Comenzando con el primer número no tachado en la lista, 2, recorremos la lista y borramos los múltiplos de ese número. Si n es impar, obtenemos la lista:

2 3 5 7 ... n

En este momento, los números borrados no son primos; los números que quedan todavía son candidatos a ser primos. Pasamos al próximo número, 3, y repetimos el anterior proceso borrando los múltiplos de 3. Si seguimos este proceso hasta que todo número fue considerado, los números que quedan en la lista final serán todos los primos entre 2 y n.

Para solucionar este problema de forma paralela podemos emplear un pipeline de procesos filtro.

• Cada filtro recibe una serie de números de su predecesor y envía una serie de números a su sucesor.
• El primer número que recibe un filtro es el próximo primo más grande;
• Le pasa a su sucesor todos los números que no son múltiplos del primero.

El siguiente es el algoritmo pipeline para la generación de números primos.

Por cada canal, el primer número es primo y todos los otros números no son múltiplo de ningún primo menor que el primer número:

Process Criba[1]
{
    int p = 2;

    for [i = 3 to n by 2] 
        Criba[2] ! (i);
}

Process Criba[i = 2 to L]
{
    int p, proximo;

    Criba[i-1] ? p;
    do Criba[i-1] ? (proximo) →
        if ((proximo MOD p) <> 0) →
            Criba[i+1] ! (proximo);
        fi
    od
}

• El primer proceso, Criba[1], envía todos los números impares desde 3 a n a Criba[2].
• Cada uno de los otros procesos recibe una serie de números de su predecesor.
• El primer número p que recibe el proceso Criba[i] es el i-ésimo primo.
• Cada Criba[i] subsecuentemente pasa todos los otros números que recibe que no son múltiplos de su primo p.
• El número total L de procesos Cribe debe ser lo suficientemente grande para garantizar que todos los primos hasta n son generados. Por ejemplo, hay 25 primos menores que 100;
• el porcentaje decrece para valores crecientes de n.

El programa anterior termina en deadlock, ya que no hay forma de saber cuál es el último número de la secuencia y cada proceso queda esperando un próximo número que no llega.

Podemos fácilmente modificarlo para que termine normalmente usando centinelas, es decir que al final de los streams de entrada son marcados por un centinela

# EOS: End Of Stream (-1 indica fin del flujo)

Process Criba[1] {
    int p = 2;

    # Enviar todos los números impares desde 3 hasta n a Criba[2]
    for [i = 3 to n by 2]
        Criba[2] ! i;

    # Enviar fin de flujo
    Criba[2] ! -1;
}

Process Criba[i = 2 to L] {
    int p, proximo;
    boolean seguir = true;

    # Recibe el primer número (primo)
    Criba[i-1] ? p;

    do (seguir);
        # Recibe siguiente candidato
        Criba[i-1] ? proximo ->

        if (proximo = -1) {
            seguir = false;
            Criba[i+1] ! -1;   # Propaga EOS al siguiente proceso
        }
        else if ((proximo MOD p) <> 0) {
            Criba[i+1] ! proximo;  # Si no es múltiplo, lo pasa
        }
    od
}

type clase_op = enum(adquirir, liberar);
chan request(int idCliente, claseOp oper, int idUnidad);
chan respuesta[n](int id_unidad);

Process Administrador_Recurso {
    int disponible = MAXUNIDADES;
    set unidades = valor inicial disponible;
    queue pendientes;

    while (true) {
        receive request(idCliente, oper, id_unidad);

        if (oper == adquirir) {
            if (disponible > 0) {
                disponible = disponible - 1;
                remove(unidades, id_unidad);
                send respuesta[idCliente](id_unidad);
            } else {
                insert(pendientes, idCliente);
            }
        } else {
            if (empty(pendientes)) {
                disponible = disponible + 1;
                insert(unidades, id_unidad);
            } else {
                remove(pendientes, idCliente);
                send respuesta[idCliente](id_unidad);
            }
        }
    }
}
// Fin del proceso Administrador_Recurso

Process Cliente[i = 1 to n] {
    int id_unidad;

    send request(i, adquirir, 0);
    receive respuesta[i](id_unidad);

    // Usa la unidad

    send request(i, liberar, id_unidad);
}

🧠 1. Modelo de comunicación

• Monitores utilizan una comunicación directa entre procesos a través de procedimientos compartidos. El proceso cliente entra al monitor, ejecuta adquirir() o liberar(), y bloquea su ejecución si no puede continuar (por ejemplo, si no hay recursos).

• Mensajes asincrónicos, en cambio, se basan en comunicación por paso de mensajes. El cliente envía un mensaje al administrador (request) y luego espera la respuesta por otro canal (respuesta[i]). No hay acceso directo a las variables compartidas; todo se coordina mediante mensajes.

🔁 2. Sincronización y control de acceso

• En el monitor, la sincronización es implícita: si disponible == 0, el proceso ejecuta wait(libre) y queda suspendido automáticamente hasta que otro proceso haga signal(libre) al liberar un recurso.

• En la versión con mensajes, no hay suspensión automática. El administrador debe mantener una cola de espera (pendientes) y decidir manualmente a quién responder y cuándo. Si alguien libera una unidad y hay clientes esperando, el administrador desencola y responde explícitamente.

🔐 3. Visibilidad y consistencia del estado

• En el monitor, los procesos tienen acceso directo a las variables disponible, unidades, etc., pero solo uno a la vez, garantizando exclusión mutua.

• Con mensajes asincrónicos, solo el administrador conoce y modifica el estado global. Los clientes no ven directamente cuántos recursos quedan; solo saben si obtuvieron uno o no, cuando reciben la respuesta.

🧩 4. Modelo de espera

• En monitores, la espera se maneja con wait y signal, que pueden funcionar según dos disciplinas:

  • Signal and Wait (el proceso que señala cede el monitor al despertado)
  • Signal and Continue (el proceso que señala continúa)

• En mensajes, la espera es activa y manual: el cliente se bloquea esperando una respuesta, y el administrador debe tener lógica para enviarle esa respuesta cuando le toque.

⚙️ 5. Aplicabilidad según arquitectura

• Los monitores son más adecuados para sistemas centralizados o con memoria compartida, ya que dependen de sincronización interna y acceso directo a variables.

• Los mensajes asincrónicos son ideales en sistemas distribuidos o clusters, donde no existe memoria compartida y cada proceso corre en su propio nodo. Permiten separar cómputo y comunicación y escalar fácilmente.

💬 Ejemplo concreto

Supongamos que hay 3 unidades disponibles, y 5 procesos piden recursos.

• En el monitor, los 3 primeros entran y adquieren recursos; los otros 2 quedan bloqueados con wait(libre) hasta que alguien libere. Luego, liberar() hace signal() y despierta a uno.

• En la versión con mensajes, los 3 primeros reciben respuesta del administrador inmediatamente. Los otros 2 son enviados a la cola pendientes, y recién serán atendidos cuando un recurso sea liberado y el administrador procese esa cola.

✅ Conclusión

• El uso de monitores es más directo y automatizado, pero menos flexible fuera de sistemas con memoria compartida.
• El enfoque de mensajes asincrónicos permite mayor control y distribución, pero requiere manejar manualmente colas, lógica de respuesta y sincronización, lo cual lo hace más complejo pero también más escalable.

Mejor caso:
En el escenario más favorable, los arreglos ya están correctamente distribuidos:

• Los n/2 valores más pequeños están en el proceso P1.
• Los n/2 valores más grandes están en P2.

Como los extremos (mayor de a1 y menor de a2) ya están en orden, los procesos solo necesitan hacer una comparación inicial y confirmar que no hay que intercambiar nada.

Resultado: Solo se envían 2 mensajes:

• P1 envía su mayor a P2.
• P2 responde con su menor a P1.

🧪 Ejemplo con n = 6 (a1 y a2 de tamaño 3)

Supongamos:

P1: a1 = [1, 2, 3]     (valores más chicos)
P2: a2 = [4, 5, 6]     (valores más grandes)

• Proceso:
  • 1) P1 envía el mayor de a1: 3
  • 2) P2 envía el menor de a2: 4
  • 3) P1 verifica: 3 < 4 ✅, así que todo está ordenado
• ✅ Resultado:
  • Se intercambian 2 mensajes: 3 →, 4 →
  • No se modifica nada

Peor caso:

En el peor de los casos, todos los elementos están en el proceso equivocado:

• Es decir, los mayores están en P1 y los menores en P2.

Esto obligará a intercambiar completamente los n/2 elementos entre ambos procesos.
Cada valor necesita un mensaje de ida y uno de vuelta, ya que el intercambio es coordinado y requiere validación mutua.

Resultado: Se intercambian n mensajes:

• n/2 valores de P1 a P2
• n/2 valores de P2 a P1 → total: (n/2) * 2 = n mensajes

Supongamos:

P1: a1 = [6, 5, 4]     (valores grandes, mal ubicados)
P2: a2 = [3, 2, 1]     (valores chicos, mal ubicados)

• Proceso:
  • P1 envía su mayor 6, P2 su menor 1
  • Ambos comparan y detectan que los elementos están desordenados, por lo tanto empiezan a intercambiar valores de uno en uno.
• Intercambios:
  • 1. 6 ↔ 1
  • 2. 5 ↔ 2
  • 3. 4 ↔ 3

Cada par requiere 2 mensajes (ida y vuelta).

✅ Resultado:

• Se hacen 3 intercambios
• Se envían 6 mensajes (3 * 2)

📊 Resumen final:

process Proc[i = 1..k] {
    int a[1..n/k];        // subarreglo local ordenado
    int dato;
    const min = 1;
    const max = n/k;

    ordenar_localmente(a);  // ordenar el arreglo local al iniciar

    for ronda = 1 to k {

        // Si la ronda y el índice tienen la misma paridad: proceso actúa como EMISOR
        if (i mod 2 == ronda mod 2 and i < k) {
            // Enviar el mayor valor local al vecino derecho
            send(proc[i+1], a[max]);
            receive(proc[i+1], dato);

            while (a[max] > dato) {
                // Insertar el dato recibido ordenadamente en 'a', descartando el mayor
                insertar_en_orden(a, dato);
                send(proc[i+1], a[max]);
                receive(proc[i+1], dato);
            }
        }

        // Si la ronda y el índice tienen distinta paridad: proceso actúa como RECEPTOR
        if (i mod 2 != ronda mod 2 and i > 1) {
            receive(proc[i-1], dato);
            send(proc[i-1], a[min]);

            while (a[min] < dato) {
                // Insertar el dato recibido ordenadamente en 'a', descartando el menor
                insertar_en_orden(a, dato);
                receive(proc[i-1], dato);
                send(proc[i-1], a[min]);
            }
        }
    }
}

Lo de abajo no hace falta pero es para probar

Con k = 4 procesos y n = 8 valores, llevando las rondas hasta que los valores queden totalmente ordenados globalmente.

Configuración inicial

Cada proceso tiene 2 elementos (n/k = 2), ordenados localmente:

Rondas del algoritmo (hasta que esté ordenado)

P1: [1, 3]
P2: [4, 5]
P3: [6, 7]
P4: [8, 9]
→ Resultado final: [1, 3, 4, 5, 6, 7, 8, 9]

El arreglo quedó completamente ordenado tras 7 rondas, que coincide con el peor caso esperado (hasta k rondas).

Si cada proceso ejecuta suficientes rondas para garantizar que la lista estará ordenada (en general, al menos k rondas), en el k-proceso, cada uno intercambia hasta (n/k)+1 mensajes por ronda. El algoritmo requiere hasta k^2 * (n/k+1).

Se puede usar un proceso coordinador al cual todos los procesos le envían en cada ronda si realizaron algún cambio o no.

Si al recibir todos los mensajes el coordinador detecta que ninguno cambio nada les comunica que terminaron.

Esto agrega overhead de mensajes ya que se envían mensajes al coordinador y desde el coordinador. Con n procesos tenemos un overhead de 2*k mensajes en cada ronda.

Nota: Utilice un mecanismo de pasaje de mensajes, justifique la elección del mismo.

PMS es más adecuado en este caso porque los procesos deben sincronizar de a pares en cada ronda por lo que PMA no sería tan útil para la resolución de este problema ya que se necesitaría implementar una barrera simétrica para sincronizar los procesos de cada etapa.

Para la alternativa del pipeline de filtros, se requieren n procesos, ya que cada uno actúa como un filtro que retiene el valor mínimo recibido hasta el momento y envía los valores mayores al siguiente. Como se desea ordenar n elementos y cada proceso retiene uno, se necesitan n procesos para que todos los valores queden almacenados, uno en cada proceso, en orden ascendente.

En cambio, para la alternativa de la red de procesos filtro (basada en una estructura de árbol binario), se necesitan n - 1 procesos. Esto se debe a que los valores iniciales están en las hojas del árbol (hay n hojas), y los nodos internos se encargan de ir fusionando pares de valores o secuencias. En un árbol binario completo con n hojas, hay exactamente n - 1 nodos internos. Por lo tanto, se requieren n - 1 procesos de merge para combinar todos los valores en una única secuencia ordenada.

Perfecto, Fabián. A continuación te doy un ejemplo para cada alternativa (pipeline de filtros y red de merges) con n = 4 valores (potencia de 2) y su tabla de ejecución correspondiente para que visualices cómo se comportan ambos métodos.

📌 Ejemplo 1: Pipeline de filtros

Idea: Cada proceso filtra el mínimo de los valores que recibe y pasa el resto al siguiente.

Valores iniciales: 6, 2, 8, 4 (se envían en ese orden)

Estructura:

Entrada → P1 → P2 → P3 → P4

Tabla de ejecución

Resultado final:
P1: 2
P2: 4
P3: 6
P4: 8
→ [2, 4, 6, 8] (ordenado)

Procesos necesarios: 4 (uno por cada valor)

📌 Ejemplo 2: Red de merges (filtros)

Idea: Se usan procesos que combinan pares de valores en orden. Cada proceso mergea dos entradas ordenadas y produce una salida ordenada.

Valores iniciales (en hojas):
Entrada a M1: 6 y 2
Entrada a M2: 8 y 4

Estructura:

Nivel 0:      6     2       8     4
               \   /         \   /
Nivel 1:         M1           M2
                  \         /
Nivel 2:             M3

Tabla de ejecución

Procesos necesarios:

• 3 merges → n − 1 = 3 procesos

📋 Comparación en tabla

📌 Pipeline

A cada proceso se le asigna un número del 1 al n, y los valores se envían uno por uno al primer proceso.

• El proceso 1 recibe n valores, se queda con el menor y envía n−1 al proceso 2.
• El proceso 2 recibe n−1 valores, se queda con el menor y envía n−2 al proceso 3.
• …
• El proceso n recibe 1 valor y no envía ninguno.

La cantidad total de mensajes enviados entre procesos es:

A esto se le suman n mensajes EOS (End Of Stream), ya que cada proceso necesita saber cuándo detenerse. Por lo tanto:

📌 Red de procesos filtro (merge tree)

En este caso, con n valores a ordenar y una red de log₂(n) niveles, la cantidad de mensajes de combinación es:

Esto incluye las comparaciones y fusiones realizadas en cada nivel del árbol.

Además, se deben sumar:

• n mensajes para enviar los valores desde los nodos hoja (datos iniciales).
• n − 1 mensajes EOS desde los nodos internos al superior para finalizar.

📌 Odd/Even Exchange Sort

Si cada proceso ejecuta suficientes rondas para garantizar el orden (en general, hasta k rondas con k procesos), entonces en cada ronda cada proceso intercambia hasta:

Cada intercambio requiere dos mensajes (ida y vuelta), y se repite durante k rondas, así que el total de mensajes es:

Resumen de todos los resultados

• En el Pipeline, cada proceso filtra y pasa el resto, por lo que la cantidad de mensajes crece cuadráticamente.
• En la Red de filtros (árbol de merges), el ordenamiento sigue una estructura logarítmica. Muy eficiente para merges en paralelo.
• En el Odd/Even, el ordenamiento depende de la cantidad de rondas (k), y aunque es simple de implementar, puede requerir muchos mensajes si los datos están muy desordenados.

• Pipeline de filtros:
  Una vez que el pipeline está lleno, es posible enviar mensajes en paralelo entre todos los procesos del pipeline. Cada proceso está recibiendo, procesando y enviando valores simultáneamente. Por lo tanto, en un instante dado, pueden enviarse en paralelo hasta n mensajes (uno por cada proceso). Al inicio y al final, el envío es más secuencial, pero en régimen estable, el flujo es completamente paralelo.

• Red de procesos filtro (merge tree):
  En esta estructura, los mensajes pueden enviarse en paralelo a nivel de cada capa del árbol. Cada proceso del mismo nivel actúa de forma independiente, por lo que se pueden enviar hasta n / 2, n / 4, …, 1 mensajes en paralelo según el nivel. El envío entre niveles debe ser secuencial (los procesos de un nivel deben esperar los resultados del anterior).

• Odd/Even Exchange Sort:
  En cada ronda (par o impar), todos los procesos que participan pueden enviar mensajes en paralelo. Por ejemplo, en una ronda impar, todos los procesos con índice impar se comunican simultáneamente con sus vecinos. Por lo tanto, en cada ronda puede haber hasta n/2 mensajes en paralelo.

📋 Comparación: Paralelismo en el envío de mensajes

📌 Algoritmo 1: Pipeline de filtros

Cada mensaje enviado implica una comparación y luego el envío (2 unidades de tiempo).

En el punto (a) se determinó que se envían

Por lo tanto, el tiempo total es:

Entonces:

📌 Algoritmo 2: Red de procesos filtro (árbol de merges)

Cada mensaje también implica 1 comparación y 1 envío → 2 unidades por mensaje.

Ya vimos que se envían

Entonces:

📌 Algoritmo 3: Odd/Even Exchange Sort

• En cada ronda, cada proceso:
  • Hace una comparación (1)
  • Envía un mensaje (1)
  • Recibe un mensaje (1)
  • Asigna/intercambia valores (1)
    → Total = 4 unidades por proceso por ronda
• En el peor caso, se necesitan hasta n rondas.
• Entonces:

Acomodando la tabla final

sem depositar := 1;
sem retirar := 1;
sem consumi[n] := ([n] 0);
int cant_consumido := ([n] 0);
T buffer;

process productor {
    while (true) {
        P(depositar);
        buffer := generarDato();     // Devuelve un entero para el buffer
        cant_consumido := 0;
        for i to n do
            V(consumi[i]);
    }
}

process consumidor[i = 1..n] {
    T dato;
    while (true) {
        P(consumi[i]);              // Espero que el dato esté en el buffer
        P(retirar);                 // Espero para tener acceso al buffer
        dato := buffer;
        cant_consumido++;
        if (cant_consumido == n)
            V(depositar);
        V(retirar);
    }
}

🎯 Objetivo

El productor debe generar un dato y colocarlo en un buffer compartido.
Cada consumidor debe leer ese dato una única vez.
Solo cuando todos lo hayan leído, el productor podrá colocar un nuevo dato.

🧩 Supuestos para el ejemplo

• Hay n = 2 consumidores: C1 y C2
• El buffer inicialmente está vacío
• El productor genera números enteros: 1, 2, 3, etc.

🔄 Ejecución paso a paso

🔹 Estado inicial

⏱ Paso 1: El productor genera un dato

1. P(depositar) → pasa (vale 1)
2. buffer := generarDato() → 1
3. cant_consumido := 0
4. V(consumi[1]) → consumi[1] = 1
5. V(consumi[2]) → consumi[2] = 1

🔁 El productor queda esperando a que los 2 consumidores consuman antes de generar otro dato.

⏱ Paso 2: El consumidor 1 consume

1. P(consumi[1]) → pasa
2. P(retirar) → pasa (vale 1)
3. dato := buffer = 1
4. cant_consumido := 1
5. cant_consumido != n → no hace nada
6. V(retirar) → retirar = 1

⏱ Paso 3: El consumidor 2 consume

1. P(consumi[2]) → pasa
2. P(retirar) → pasa
3. dato := buffer = 1
4. cant_consumido := 2
5. cant_consumido == n → entonces V(depositar) → ahora el productor puede seguir
6. V(retirar)

⏱ Paso 4: El productor continúa

1. P(depositar) → pasa (porque fue liberado)
2. buffer := 2
3. cant_consumido := 0
4. V(consumi[1]), V(consumi[2]) → y sigue el ciclo

✅ Garantías del algoritmo

sem retirar[tamBuffer] := 1;              // semáforo para cada slot del buffer
sem consumir[n] := ([n] 0);
int cant_consumido[tamBuffer] := ([n] 0);
T buffer[tamBuffer];

process productor {
    int posLibre := 0;                   // Siguiente posición libre del buffer (productor)
    while(true){
        P(depositar);
        buffer[posLibre] := generarDato();     // Devuelve dato tipo T para el buffer
        cant_consumido[posLibre] := 0;
        for i to n do
            V(consumir[i]);
        posLibre := (posLibre + 1) mod n;
    }
}

process consumidor[i: 1..n] {
    int post_actual := 0;               // Slot del que debe consumir
    T dato;
    while(true){
        P(consumir[i]);
        P(retirar[post_actual]);        // Espera por un slot en particular
        dato := buffer[post_actual]; // El acceso de esta manera no se encuentra en la imagen pero supongo que esta bien
        cant_consumido[post_actual]++;
        if (cant_consumido[post_actual] == n)
            V(depositar);
        V(retirar[post_actual]);
        post_actual := (post_actual + 1) mod n;
    }
}

🧩 Supuestos del ejemplo

• tamBuffer = 2 → hay dos slots: buffer[0] y buffer[1]
• n = 2 → hay dos consumidores: C1 y C2
• buffer[i] contiene datos generados por el productor
• Cada dato debe ser consumido por ambos consumidores antes de poder sobrescribir el slot
• Los consumidores deben leer los datos en orden

🔁 Estado inicial

⏱ Paso 1: El productor genera el primer dato

1. P(depositar) → OK
2. buffer[0] := generarDato() → 10
3. cant_consumido[0] := 0
4. V(consumir[1]), V(consumir[2])
5. posLibre := 1 (próximo slot)

⏱ Paso 2: Ambos consumidores empiezan a consumir buffer[0] (dato 10)

Consumer 1:

1. P(consumir[1])
2. P(retirar[0]) → OK
3. dato := buffer[0] → 10
4. cant_consumido[0] := 1
5. V(retirar[0]) (libera acceso al slot)
6. post_actual := 1

Consumer 2:

1. P(consumir[2])
2. P(retirar[0]) → OK
3. dato := buffer[0] → 10
4. cant_consumido[0] := 2
5. cant_consumido[0] == n → V(depositar) → libera al productor
6. V(retirar[0])
7. post_actual := 1

⏱ Paso 3: El productor genera el segundo dato

1. P(depositar) → OK (fue liberado)
2. buffer[1] := generarDato() → 20
3. cant_consumido[1] := 0
4. V(consumir[1]), V(consumir[2])
5. posLibre := 0

⏱ Paso 4: Ambos consumidores consumen buffer[1] (dato 20)

Consumer 1:

1. P(consumir[1])
2. P(retirar[1])
3. dato := buffer[1] → 20
4. cant_consumido[1] := 1
5. V(retirar[1])
6. post_actual := 0

Consumer 2:

1. P(consumir[2])
2. P(retirar[1])
3. dato := buffer[1] → 20
4. cant_consumido[1] := 2
5. V(depositar) (productor puede continuar)
6. V(retirar[1])
7. post_actual := 0

🔁 Y así continúa el ciclo…

✅ Propiedades garantizadas

Una butterfly barrier tiene log2(n) etapas.
Cada Worker sincroniza con un Worker distinto en cada etapa.
En particular, en la etapa s un Worker sincroniza con un Worker a distancia 2^(s-1).

Se usan distintas variables flag para cada barrera de dos procesos.

Cuando cada Worker pasó a través de log2(n) etapas, todos los Workers deben haber arribado a la barrera y por lo tanto todos pueden seguir.
Esto es porque cada Worker ha sincronizado directa o indirectamente con cada uno de los otros.

Diagrama (sincronizaciones por etapa)

Workers     1   2   3   4   5   6   7   8

Etapa 1     └───┘   └───┘   └───┘   └───┘

Etapa 2     └─────────┘   └─────────┘

Etapa 3     └───────────────────────┘

Codigo

int N = 8;
int E = log(N);
int arribo[1:N] = ([N] 0);

process Worker[i = 1 to N] {
    int j;
    int resto;
    int distancia;

    while (true) {
        // Sección de código anterior a la barrera.

        // --- Inicio de la barrera butterfly ---
        for (etapa = 1; etapa <= E; etapa++) {
            distancia = 2 ^ (etapa - 1);           // distancia = 2^(etapa-1)
            resto = i mod 2 ^ etapa;

            if (resto == 0 || resto > distancia)   // define si sincroniza con i+dist o i-dist
                distancia = -distancia;

            j = i + distancia;

            while (arribo[i] == 1) skip;           // espera a que su flag esté en 0
            arribo[i] = 1;                         // indica que llegó

            while (arribo[j] == 0) skip;           // espera a su par
            arribo[j] = 0;                         // limpia la flag del otro
        }
        // --- Fin de la barrera butterfly ---

        // Sección de código posterior a la barrera.
    }
}

Este no me quedo del todo claro pero bueno

Chan valores[1:n; 1:n](int);

Process P[i = 1 to n, j = 1 to n] {
    Int v;
    Int Nuevo, minimo = v, maximo = v;
    Int cantVecinos;
    Vecinos[1..cantVecinos];

    For (k = 1 to cantGeneraciones) {
        For (p = 1 to cantVecinos) {
            Send valores[vecinos[p].fila, vecinos[p].columna](v);
        }

        For (p = 1 to cantVecinos) {
            Receive valores[i, j](nuevo);
            if (nuevo < minimo)
                minimo = nuevo;
            if (nuevo > maximo)
                maximo = nuevo;
        }
    }
}

🎯 Supongamos 3 procesos: A, B, C

A --- B --- C

• A tiene valor 5
• B tiene valor 2
• C tiene valor 8

Cada uno está conectado con sus vecinos inmediatos.

🧪 Generación 1: Intercambio de valores

• 1. A envía 5 a B
• 2. B envía 2 a A y C
• 3. C envía 8 a B

     [5]        [2]        [8]
      A  <-->   B   <-->   C

🔍 ¿Qué recibe cada uno?

✅ Resultado final (después de 1 ronda)

A: mínimo = 2, máximo = 5  
B: mínimo = 2, máximo = 8  
C: mínimo = 2, máximo = 8

Si hacemos otra ronda, A también recibirá el 8 (a través de B), y entonces todos tendrán:

mínimo = 2, máximo = 8

📌 Esto mismo pasa en grillas grandes: con varias generaciones, los valores extremos se difunden.

En cada ronda, los procesos envían mensajes a sus vecinos. Dependiendo de su posición en la grilla, cada proceso tiene distinta cantidad de vecinos:

🔹 Esquinas (4 procesos)

• Cada uno tiene 2 vecinos → envía 2 mensajes por ronda

• Total por todas las rondas:

  4 procesos * 2 mensajes * (n-1) rondas * 2 (envío y recepción)  
  = 4 * 2 * (n - 1) * 2  
  = (n - 1) * 16 mensajes

  plaintext

🔹 Bordes (sin esquinas) → hay 4 lados con (n - 2) procesos cada uno

• Cada uno tiene 3 vecinos → envía 3 mensajes por ronda

• Total:

  (n - 2) * 4 procesos * 3 mensajes * (n - 1) rondas * 2  
  = (n - 2) * 4 * 3 * (n - 1) * 2  
  = (n - 1)(n - 2) * 12 mensajes

  plaintext

🔹 Internos → (n - 2) × (n - 2) procesos

• Cada uno tiene 4 vecinos → envía 4 mensajes por ronda

• Total:

  (n - 2)^2 * 4 mensajes * (n - 1) rondas * 2  
  = (n - 2)^2 * (n - 1) * 8 mensajes

  plaintext

No, no es posible reducir el número de mensajes, ya que no existe una forma de saber con certeza cuándo un proceso ha recibido el valor mínimo o máximo global.
Por lo tanto, para garantizar que todos los procesos lleguen a conocer los valores extremos, es necesario ejecutar las (n - 1) × 2 generaciones completas.

Es un esquema donde un mensaje especial (token) circula entre los procesos. Solo el que tiene el token puede ejecutar una acción crítica, como entrar a la sección crítica o tomar decisiones.

Ejemplo: exclusión mutua distribuida, detección de terminación.

Ventajas: simple de implementar, no necesita reloj ni identificadores globales, funciona bien en topologías como anillo.

Desventajas: si se pierde el token el sistema se bloquea; no hay paralelismo (solo trabaja quien tiene el token); puede haber demoras innecesarias.

Mejor comunicación: asincrónica, porque permite circulación sin bloqueo. Se adapta bien a arquitecturas de memoria distribuida (AMP).

Varios procesos replican un recurso compartido (archivo, base de datos) para brindar alta disponibilidad y tolerancia a fallos. A los clientes les parece que hay un único servidor.

Ejemplo: mozos en el problema de los filósofos, sistemas de archivos distribuidos.

Ventajas: mayor disponibilidad, tolerancia a fallos, mejora el rendimiento si se balancean bien los pedidos.

Desventajas: mantener la consistencia entre réplicas es complejo; puede haber conflictos si dos servidores procesan escrituras en paralelo.

Mejor comunicación: asincrónica (evita bloquear al cliente), ideal en AMP. En SMP es más difícil porque hay que mantener varios canales y controlarlos.

Un nodo envía mensajes “probe” a sus vecinos; cuando todos responden con “eco”, el emisor sabe que se llegó a todos. Sirve para explorar redes desconocidas o detectar nodos activos.

Ejemplo: descubrimiento de topología en redes móviles o dinámicas.

Ventajas: útil sin conocer la red; robusto frente a cambios; permite diseminar o recolectar información.

Desventajas: puede generar muchos mensajes; necesita control para evitar ciclos o duplicación.

Mejor comunicación: asincrónica, ideal en AMP por su descentralización y tolerancia a variaciones en la red.