En el siguiente experimento, un grupo de alumnos es llevado a un salón donde no hay luz, por lo que no pueden ver nada. Entonces se les pide que, uno por uno, todos digan su nombre. ¿Cuál sería el mejor algoritmo para lograrlo en el menor tiempo posible?
¿Quién comienza, quién continúa? Una posibilidad es utilizar el siguiente algoritmo:
1] Intentar decir el nombre.
2] Si al iniciar a hablar, se escucha un ruido (otro alumno diciendo su nombre), callarse y pasar a 4.
3] Si no hay ruido, decir el nombre y terminar.
4] Esperar el doble de tiempo que antes y regresar a 1.
Curiosidades
Este problema de congestión es bien conocido para la mayoría de las personas que viven en grandes ciudades, pues lo sufren todos los días en la forma de tráfico vehicular. En la ciudad de México, por ejemplo, diariamente circulan más de 3 000 000 de vehículos, lo cual, además de generar congestión o tráfico vehicular, es la principal causa de contaminación.
Es decir, se intenta decir el nombre; si hay ruido, se debe esperar dos segundos y se vuelve a intentar; si hay ruido, ahora la espera es de 22 = 4 segundos y se vuelve a intentary así hasta lograr decir el nombre. Éste es un algoritmo utilizado en redes ethernet estándar para evitar la congestión y se conoce como exponential backoff.
¿Si tienen que hacer lo mismo, pero en un salón con luz, como procederían? Esto es típico, por ejemplo, en el primer día de clases, cuando el profesor les pide a todos que se presenten diciendo su nombre. Hay varias opciones: la primera sería definir un orden, por ejemplo recorriendo las filas de adelante hacia atrás, de izquierda a derecha. Otra opción sería que cada alumno levante la mano si aún no se ha presentado y esperar a que el profesor seleccione a uno. Este último algoritmo, donde existe un moderador, es muy socorrido en computación y deben considerarse dos conceptos importantes: imparcialidad y hambruna.
En este contexto, imparcialidad es la idea de que a todos los estudiantes —o a los paquetes en una red de computadoras— se les dé una oportunidad de transmitir. El problema de que un moderador elija al siguiente es que puede seleccionar a los mismos para transmitir, ignorando a algunos, los cuales estarían entonces en un estado de hambruna, pues no pueden avanzar en su tarea.
En las redes de computadoras existen distintos tipos de transmisión de datos, entre ellos unicast, que va de un nodo a otro de manera directa y, en el otro extremo, broadcast, donde la transmisión se realiza de manera simultánea a todos los nodos en la red.
