Bob Metcalfe y su Ethernet: premio Turing 2022
La semana pasada el ingeniero y emprendedor Bob Metcalfe ha sido galardonado con el mayor honor en Ciencias de la Computación: Premio Turing 2022. Fue premiado por su trabajo junto a David R. Boggs por el desarrollo del protocolo Ethernet gracias al cual en la actualidad existen miles de millones de usuarios conectados y, prácticamente todos los aspectos de la vida humana dependen de esta red.
He preparado este artículo para explicarle a nuestra comunidad dos aspectos fundamentales en el trabajo científico de Bob Metcalfe, creemos que este reconocimiento es enormemente merecido y lo vemos como una excelente oportunidad para reflexionar sobre la importancia de los algoritmos de consenso en nuestra vida diaria.
La vida de Bob Metcalfe transcurrió en paralelo con el crecimiento de internet y sus contribuciones son relevantes desde un punto de vista científico pero también desde el punto de vista industrial. Antes de su trabajo internet era un reto tanto para ingenieros como para científicos de la computación.
Los dos temas sobre los que hablaremos son:
- Binary Exponential Backoff y la red Ethernet
- Metcalfe's Law
Teoría de colas y cadenas de markov
Supongamos que nos interesa fijar las reglas con las cuales se comunicarán los miembros de una red gigantesca de una manera descentralizada. Por ejemplo podríamos pensar en sucursales interestelares de alguna empresa, llamémosle Colegio de Matemáticas Bourbaki y digamos que en buena parte de los planetas en el universo existen sucursales de Bourbaki.
Los mensajes que se envían las distintas sucursales podrían ser por ejemplo nuevos algoritmos de machine learning para enseñarles a los alumnos, bases de datos para que ellos puedan resolver sus ejercicios o inclusive bibliotecas de Python actualizadas para construir modelos.
Existen dos problemas fundamentales en la comunicación de esta red:
- A una sucursal probablemente le interese comunicarse simultáneamente con más de una.
- Dada la lejanía entre algunas sucursales, los mensajes que se envían están claramente en riesgo de no llegar a su destino.
El primero de los problemas está relacionado con los tiempos de espera durante la transmisión de un mensaje, supongamos que existe una unidad mínima de información que enviaremos, por ejemplo una palabra. Cuando hablamos en persona difícilmente dejamos largos tiempos muertos entre una palabra y otra y gracias a esta hipótesis podemos centrar toda nuestra atención en la conversación con un solo elemento de la red. Si hiciéramos esto en la red de sucursales de Bourbaki, nuestro protocolo sería poco eficiente pues en los tiempos de espera entre palabras cuando A y B no se están comunicando, A podría enviar información a C.
El segundo de los problemas es aún más grave pues debemos asumir que algunos mensajes no llegarán, ¡recordemos que entre sucursales podrían estar a años luz de distancia! Para resolver este problema Norm Abramson propuso que cuando un mensaje no llegue adecuadamente, no nos afanemos intentando re-enviarlo inmediatamente sino que podríamos esperar inclusive una cantidad aleartoria de segundos para volverlo a enviar. Este problema ocurría en Hawai (donde Abramson era profesor) exactamente igual a como lo hemos planteado solo que las distancias en lugar de ser interestelares eran las que hay entre islas hawaianas.
Cuando Metcalfe estaba estudiando su doctorado en Harvard y trabajaba en Xerox Palo Alto Research Center conoció el trabajo de Abramson sin embargo no estaba convencido de que las hipótesis eran las correctas y por lo tanto su funcionamiento podría estar en peligro pues nada garantiza que un mensaje tarde un tiempo arbitrariamente largo en enviarse
Para resolver este problema construyó una cadena de markov a través del tiempo T para modelar tanto el número de palabras que en el instante T una de las sucursales está por mandar, como el número de intentos fallidos que en ese momento ha hecho.
La existencia de un comportamiento límite para esta cadena de markov garantizaría que el tiempo de espera para que un mensaje se envíe está acotado. La garantía teórica de este comportamiento está relacionado con la estacionariedad, la ergodicidad o la recurrencia positiva.
Es muy llamativo que la demostración matemática de que el protocolo Ethernet funciona no llegó inmediatamente sino hasta que se publicó el artículo On the Stability of the Ethernet. Aún así la intuición de Metcalfe y Boggs era la correcta y pronto implementarían físicamente y comercializarían el Ethernet.
¿Cuánto vale una red?
La segunda contribución de la que hablaremos se conoce como la ley de Metcalfe. Desde su punto de vista estar conectados a una red tiene un valor intrínseco V el cual podemos calcular contando el número N de nodos que pertenecen a esta red R.
En los últimos años el mismo Metcalfe y otros investigadores han utilizado datos de Facebook, Bitcoin y otras redes sociales para poner a prueba su ley y los resultados son muy prometedores.
¿Dónde aprender más?
Quienes deseen comprender las matemáticas detrás de las cadenas de markov y cómo se utilizan para resolver problemas financieros, del análisis de datos e inteligencia artificial les recomendamos inscribirse a nuestros próximos cursos:
- Track de Ciencia de Datos. (49 semanas).
- Machine Learning & AI for the Working Analyst ( 12 semanas).
- Matemáticas para Ciencia de Datos ( 24 semanas).
- Especialización en Deep Learning. (12 semanas).
- Track de Finanzas Cuantitativas (49 semanas)
- Aplicaciones Financieras De Machine Learning E IA ( 12 semanas).
- Las matemáticas de los mercados financieros (24 semanas).
- Deep Learning for Finance (12 semanas).
