Computación distribuida

ModelosEditoriales

Muchas de las tareas que nos gustaría automatizar mediante el uso de un ordenador son de tipo pregunta-respuesta: queremos hacer una pregunta y el ordenador debe producir una respuesta. En la informática teórica, estas tareas se denominan problemas computacionales. Formalmente, un problema computacional consta de instancias junto con una solución para cada instancia. Las instancias son preguntas que podemos hacer, y las soluciones son las respuestas deseadas a estas preguntas.

La informática teórica busca entender qué problemas computacionales pueden ser resueltos mediante el uso de un ordenador (teoría de la computabilidad) y con qué eficiencia (teoría de la complejidad computacional). Tradicionalmente, se dice que un problema puede ser resuelto utilizando un ordenador si podemos diseñar un algoritmo que produzca una solución correcta para cualquier instancia dada. Dicho algoritmo puede implementarse como un programa informático que se ejecuta en un ordenador de propósito general: el programa lee una instancia del problema de entrada, realiza algún cálculo y produce la solución como salida. Formalismos como las máquinas de acceso aleatorio o las máquinas de Turing universales pueden utilizarse como modelos abstractos de un ordenador secuencial de propósito general que ejecuta dicho algoritmo.

El campo de la computación concurrente y distribuida estudia cuestiones similares en el caso de múltiples ordenadores, o de un ordenador que ejecuta una red de procesos que interactúan: ¿qué problemas computacionales pueden resolverse en dicha red y con qué eficiencia? Sin embargo, no es en absoluto evidente lo que se entiende por «resolver un problema» en el caso de un sistema concurrente o distribuido: por ejemplo, ¿cuál es la tarea del diseñador de algoritmos, y cuál es el equivalente concurrente o distribuido de un ordenador secuencial de propósito general?

La discusión que sigue se centra en el caso de múltiples ordenadores, aunque muchas de las cuestiones son las mismas para los procesos concurrentes que se ejecutan en un único ordenador.

Se suelen utilizar tres puntos de vista:

Algoritmos paralelos en modelo de memoria compartida

• Todos los procesadores tienen acceso a una memoria compartida. El diseñador del algoritmo elige el programa que ejecuta cada procesador.
• Un modelo teórico es el de las máquinas de acceso aleatorio paralelo (PRAM) que se utilizan. Sin embargo, el modelo clásico de PRAM asume un acceso síncrono a la memoria compartida.
• Los programas de memoria compartida pueden extenderse a sistemas distribuidos si el sistema operativo subyacente encapsula la comunicación entre nodos y unifica virtualmente la memoria en todos los sistemas individuales.
• Un modelo que se acerca más al comportamiento de las máquinas multiprocesadoras del mundo real y tiene en cuenta el uso de instrucciones de máquina, como Compare-and-swap (CAS), es el de la memoria compartida asíncrona. Hay un amplio cuerpo de trabajo sobre este modelo, un resumen del cual se puede encontrar en la literatura.

Algoritmos paralelos en modelo de paso de mensajes

• El diseñador del algoritmo elige la estructura de la red, así como el programa que ejecuta cada ordenador.
• Se utilizan modelos como los circuitos booleanos y las redes de ordenación. Un circuito booleano puede verse como una red de ordenadores: cada puerta es un ordenador que ejecuta un programa informático extremadamente sencillo. Del mismo modo, una red de ordenación puede verse como una red de ordenadores: cada comparador es un ordenador.

Algoritmos distribuidos en el modelo de paso de mensajes

• El diseñador del algoritmo sólo elige el programa de ordenador. Todos los ordenadores ejecutan el mismo programa. El sistema debe funcionar correctamente independientemente de la estructura de la red.
• Un modelo comúnmente utilizado es un grafo con una máquina de estado finito por nodo.

En el caso de los algoritmos distribuidos, los problemas computacionales suelen estar relacionados con grafos. A menudo, el gráfico que describe la estructura de la red informática es la instancia del problema. Esto se ilustra en el siguiente ejemplo.

Un ejemploEditar

Considere el problema computacional de encontrar una coloración de un grafo G dado. Diferentes campos podrían adoptar los siguientes enfoques:

Algoritmos centralizados

• El grafo G se codifica como una cadena, y la cadena se da como entrada a un ordenador. El programa informático encuentra una coloración del grafo, codifica la coloración como una cadena y emite el resultado.

Algoritmos paralelos

• De nuevo, el grafo G se codifica como una cadena. Sin embargo, varios ordenadores pueden acceder a la misma cadena en paralelo. Cada ordenador puede centrarse en una parte del grafo y producir una coloración para esa parte.
• El objetivo principal es la computación de alto rendimiento que explota la potencia de procesamiento de múltiples ordenadores en paralelo.
• Algoritmos distribuidos
  • El grafo G es la estructura de la red de ordenadores. Hay un ordenador por cada nodo de G y un enlace de comunicación por cada arista de G. Inicialmente, cada ordenador sólo conoce a sus vecinos inmediatos en el grafo G; los ordenadores deben intercambiar mensajes entre sí para descubrir más sobre la estructura de G. Cada ordenador debe producir su propio color como salida.
  • El objetivo principal es coordinar el funcionamiento de un sistema distribuido arbitrario.

  Aunque el campo de los algoritmos paralelos tiene un enfoque diferente al de los algoritmos distribuidos, hay mucha interacción entre los dos campos. Por ejemplo, el algoritmo Cole-Vishkin para colorear grafos se presentó originalmente como un algoritmo paralelo, pero la misma técnica también puede utilizarse directamente como un algoritmo distribuido.

  Además, un algoritmo paralelo puede implementarse tanto en un sistema paralelo (utilizando memoria compartida) como en un sistema distribuido (utilizando paso de mensajes). La frontera tradicional entre los algoritmos paralelos y distribuidos (elegir una red adecuada frente a ejecutar en cualquier red) no se encuentra en el mismo lugar que la frontera entre los sistemas paralelos y distribuidos (memoria compartida frente a paso de mensajes).

  Medidas de complejidadEditar

  En los algoritmos paralelos, otro recurso además del tiempo y el espacio es el número de ordenadores. De hecho, a menudo hay un compromiso entre el tiempo de ejecución y el número de ordenadores: el problema puede resolverse más rápido si hay más ordenadores funcionando en paralelo (véase speedup). Si un problema de decisión puede resolverse en tiempo polilogarítmico utilizando un número polinómico de procesadores, se dice que el problema pertenece a la clase NC. La clase NC puede definirse igualmente bien utilizando el formalismo PRAM o los circuitos booleanos: las máquinas PRAM pueden simular circuitos booleanos de forma eficiente y viceversa.

  En el análisis de los algoritmos distribuidos, se suele prestar más atención a las operaciones de comunicación que a los pasos computacionales. Tal vez el modelo más sencillo de computación distribuida sea un sistema síncrono en el que todos los nodos operan a la par. Este modelo se conoce comúnmente como modelo LOCAL. Durante cada ronda de comunicación, todos los nodos en paralelo (1) reciben los últimos mensajes de sus vecinos, (2) realizan cálculos locales arbitrarios y (3) envían nuevos mensajes a sus vecinos. En estos sistemas, una medida de complejidad central es el número de rondas de comunicación sincrónicas necesarias para completar la tarea.

  Esta medida de complejidad está estrechamente relacionada con el diámetro de la red. Sea D el diámetro de la red. Por un lado, cualquier problema computable puede resolverse de forma trivial en un sistema distribuido síncrono en aproximadamente 2D rondas de comunicación: basta con reunir toda la información en un lugar (D rondas), resolver el problema e informar a cada nodo sobre la solución (D rondas).

  Por otro lado, si el tiempo de ejecución del algoritmo es mucho menor que D rondas de comunicación, entonces los nodos de la red deben producir su salida sin tener la posibilidad de obtener información sobre partes distantes de la red. En otras palabras, los nodos deben tomar decisiones globalmente consistentes basadas en la información disponible en su vecindad D local. Se conocen muchos algoritmos distribuidos con un tiempo de ejecución muy inferior a D rondas, y entender qué problemas pueden ser resueltos por dichos algoritmos es una de las cuestiones centrales de investigación en este campo. Típicamente, un algoritmo que resuelve un problema en tiempo polilogarítmico en el tamaño de la red se considera eficiente en este modelo.

  Otra medida comúnmente utilizada es el número total de bits transmitidos en la red (cf. complejidad de la comunicación). Las características de este concepto se suelen capturar con el modelo CONGEST(B), que se define de forma similar al modelo LOCAL pero en el que los mensajes individuales sólo pueden contener B bits.

  Otros problemasEditar

  Los problemas computacionales tradicionales adoptan la perspectiva de que el usuario hace una pregunta, un ordenador (o un sistema distribuido) procesa la pregunta, luego produce una respuesta y se detiene. Sin embargo, también hay problemas en los que se requiere que el sistema no se detenga, incluyendo el problema de los filósofos comedores y otros problemas similares de exclusión mutua. En estos problemas, se supone que el sistema distribuido coordina continuamente el uso de los recursos compartidos para que no se produzcan conflictos o bloqueos.

  También hay retos fundamentales que son exclusivos de la computación distribuida, por ejemplo los relacionados con la tolerancia a fallos. Algunos ejemplos de problemas relacionados son los problemas de consenso, la tolerancia a fallos bizantina y la autoestabilización.

  Mucha investigación se centra también en la comprensión de la naturaleza asíncrona de los sistemas distribuidos:

  • Se pueden utilizar sincronizadores para ejecutar algoritmos síncronos en sistemas asíncronos.
  • Los relojes lógicos proporcionan una ordenación causal de eventos «happened-before».
  • Los algoritmos de sincronización de relojes proporcionan marcas de tiempo físicas globalmente consistentes.

  ElecciónEditorial

  La elección del coordinador (o elección del líder) es el proceso de designar un único proceso como organizador de alguna tarea distribuida entre varios ordenadores (nodos). Antes de comenzar la tarea, todos los nodos de la red desconocen qué nodo será el «coordinador» (o líder) de la tarea, o no pueden comunicarse con el coordinador actual. Sin embargo, después de ejecutar un algoritmo de elección de coordinador, cada nodo de la red reconoce a un nodo particular y único como coordinador de la tarea.

  Los nodos de la red se comunican entre sí para decidir cuál de ellos pasará al estado de «coordinador». Para ello, necesitan algún método para romper la simetría entre ellos. Por ejemplo, si cada nodo tiene identidades únicas y comparables, entonces los nodos pueden comparar sus identidades, y decidir que el nodo con la identidad más alta es el coordinador.

  La definición de este problema se atribuye a menudo a LeLann, que lo formalizó como un método para crear un nuevo token en una red de anillo de tokens en la que el token se ha perdido.

  Los algoritmos de elección de coordinador están diseñados para ser económicos en términos de bytes totales transmitidos, y de tiempo. El algoritmo sugerido por Gallager, Humblet y Spira para grafos no dirigidos generales ha tenido un fuerte impacto en el diseño de algoritmos distribuidos en general, y ganó el Premio Dijkstra por un artículo influyente en la computación distribuida.

  Se sugirieron muchos otros algoritmos para diferentes tipos de grafos de red, como anillos no dirigidos, anillos unidireccionales, grafos completos, rejillas, grafos de Euler dirigidos y otros. Un método general que desvincula la cuestión de la familia de grafos del diseño del algoritmo de elección del coordinador fue sugerido por Korach, Kutten y Moran.

  Para realizar la coordinación, los sistemas distribuidos emplean el concepto de coordinadores. El problema de la elección del coordinador consiste en elegir un proceso de entre un grupo de procesos en diferentes procesadores de un sistema distribuido para que actúe como coordinador central. Existen varios algoritmos de elección del coordinador central.

  Propiedades de los sistemas distribuidosEditar

  Hasta ahora se ha centrado la atención en el diseño de un sistema distribuido que resuelva un problema determinado. Un problema de investigación complementario es el estudio de las propiedades de un sistema distribuido dado.

  El problema de detención es un ejemplo análogo del campo de la computación centralizada: se nos da un programa de ordenador y la tarea es decidir si se detiene o se ejecuta para siempre. El problema de detención es indecidible en el caso general, y naturalmente entender el comportamiento de una red de ordenadores es al menos tan difícil como entender el comportamiento de un ordenador.

  Sin embargo, hay muchos casos especiales interesantes que son decidibles. En particular, es posible razonar sobre el comportamiento de una red de máquinas de estado finito. Un ejemplo es decir si una red dada de máquinas de estado finito que interactúan (asíncronas y no deterministas) puede llegar a un punto muerto. Este problema es PSPACE-completo, es decir, es decidible, pero no es probable que exista un algoritmo eficiente (centralizado, paralelo o distribuido) que resuelva el problema en el caso de redes grandes.