El algoritmo de búsqueda de árbol distribuido ( DTS ) es una clase de algoritmos para buscar valores de manera eficiente y distribuida. Su propósito es iterar a través de un árbol trabajando a lo largo de múltiples ramas en paralelo y fusionando los resultados de cada rama en una solución común, con el fin de minimizar el tiempo dedicado a buscar un valor en una estructura de datos similar a un árbol.
El artículo original fue escrito en 1988 por Chris Ferguson y Richard E. Korf, del Departamento de Ciencias Informáticas de la Universidad de California. Utilizaron otras IA de ajedrez para desarrollar este algoritmo de mayor alcance.
El algoritmo de búsqueda de árbol distribuido (también conocido como algoritmo Korf-Ferguson) fue creado para resolver el siguiente problema: "Dado un árbol con un factor de ramificación y una profundidad no uniformes, búsquelo en paralelo con una cantidad arbitraria de procesadores lo más rápido posible".
La parte de nivel superior de este algoritmo es general y no utiliza un tipo particular de búsqueda de árbol existente, pero puede especializarse fácilmente para adaptarse a cualquier tipo de búsqueda de árbol no distribuida.
DTS consiste en utilizar múltiples procesos, cada uno con un nodo y un conjunto de procesadores asociados, con el objetivo de buscar en el subárbol que se encuentra debajo de dicho nodo. Cada proceso se divide entonces en múltiples subprocesos coordinados que se dividen recursivamente hasta que se encuentra una forma óptima de buscar en el árbol en función de la cantidad de procesadores disponibles para cada proceso. Una vez que un proceso termina, DTS reasigna dinámicamente los procesadores a otros procesos para mantener la eficiencia al máximo mediante un buen equilibrio de carga, especialmente en árboles irregulares.
Una vez que un proceso termina de buscar, envía y fusiona recursivamente una señal resultante a su proceso padre, hasta que se hayan fusionado todas las diferentes subrespuestas y se haya resuelto todo el problema. [1]
DTS solo es aplicable bajo dos condiciones principales: la estructura de datos a buscar es un árbol y el algoritmo puede hacer uso de al menos una unidad de cálculo (aunque no puede considerarse distribuido si solo hay una).
Un ejemplo importante del uso cotidiano de DTS es el enrutamiento de redes. Internet puede verse como un árbol de direcciones IP y una analogía con un protocolo de enrutamiento podría ser cómo funcionan las oficinas de correos en el mundo real. Dado que actualmente hay más de 4.3 mil millones de direcciones IP, la sociedad depende en gran medida del tiempo que tardan los datos en llegar a su destino. Como tal, el enrutamiento IP divide el trabajo en múltiples subunidades, cada una con diferentes escalas de capacidades de cálculo y utiliza los resultados de cada una para encontrar la ruta de una manera muy eficiente. Este es un ejemplo de DTS que afecta a más del 43% de la población mundial, por razones que van desde el entretenimiento hasta la seguridad nacional. [2]
Aunque DTS es actualmente uno de los algoritmos más utilizados, muchas de sus aplicaciones tienen alternativas que potencialmente podrían convertirse en soluciones más eficientes y que demanden menos recursos, si se investigaran más.
Uno de los ejemplos más controvertidos es el procesamiento de Big Data. En aplicaciones como Google Search Engine, Facebook y YouTube, la búsqueda debe optimizarse para mantener el tiempo de espera dentro de un margen razonable. Esto se puede lograr mediante el uso simple de DTS, pero se utilizan otros algoritmos en su lugar (por ejemplo, el algoritmo de hash de datos en bases de datos SQL ) o en conjunto (el algoritmo Haystack de Facebook agrupa la búsqueda en árbol paralela, el algoritmo de hash de datos y el ordenamiento/clasificación de memoria). [3]
Una de las limitaciones más importantes de DTS es el hecho de que requiere un árbol como entrada. Los árboles son una subinstancia de una estructura de datos conocida como grafos, lo que significa que cada grafo se puede convertir en un árbol. Aunque actualmente no existe una mejor manera de buscar en árboles que el algoritmo de Korf-Ferguson, cada tarea tiene particularidades diferentes y en la mayoría de los casos, existirán estructuras de datos más eficientes para representar el problema y resolverlo que mediante la búsqueda en árboles. Y por lo tanto, existen instancias de estructuras de árboles con ciclos que no pueden ser más rápidos que una búsqueda en grafos sobre la misma estructura con la misma capacidad de procesamiento.
Existen pocas controversias en torno al algoritmo DTS de Korf-Ferguson, ya que se lo reconoce como muy completo, pero simple. Muy a menudo se lo utiliza como trampolín para que los estudiantes descubran los fundamentos y conceptos clave de la resolución distribuida de problemas.
El desafío más importante a este concepto algorítmico fue un artículo de Kröll B, "Balanced Distributed Search Trees Do Not Exist", que no ataca la veracidad o la eficiencia actual del algoritmo, sino más bien el hecho de que el DTS en sí, sin importar cuántas mejoras se le hagan (por ejemplo, balanceando el árbol de entrada de antemano), nunca podrá alcanzar un tiempo de resolución óptimo. [4] Esto abre un nuevo punto de vista: ¿se utilizan demasiados recursos para completar el DTS, lo que impide que se investiguen y desarrollen nuevos algoritmos con mayor potencial de eficiencia? Otro límite del DTS es el hecho de que, sin importar cuán eficiente sea la división, coordinación y fusión de las soluciones, siempre estará limitada por la cantidad de material o procesadores y su poder de procesamiento.