Computación distribuída

Un sistema distribuido es un sistema cuyos componentes están ubicados en diferentes computadoras en red, las cuales se comunican y coordinan sus acciones pasando mensajes entre sí desde cualquier sistema. La computación distribuida es un campo de la informática que estudia los sistemas distribuidos.

Los componentes de un sistema distribuido interactúan entre sí para lograr un objetivo común. Tres desafíos importantes de los sistemas distribuidos son: mantener la concurrencia de los componentes, superar la falta de un reloj global y gestionar la falla independiente de los componentes. Cuando falla un componente de un sistema, no falla todo el sistema. Los ejemplos de sistemas distribuidos varían desde sistemas basados en SOA hasta juegos en línea multijugador masivos y aplicaciones punto a punto.

Un programa de computadora que se ejecuta dentro de un sistema distribuido se denomina programa distribuido, y programación distribuida es el proceso de escribir dichos programas. Hay muchos tipos diferentes de implementaciones para el mecanismo de paso de mensajes, incluidos HTTP puro, conectores tipo RPC y colas de mensajes.

Computación distribuida también se refiere al uso de sistemas distribuidos para resolver problemas computacionales. En la computación distribuida, un problema se divide en muchas tareas, cada una de las cuales es resuelta por una o más computadoras, que se comunican entre sí mediante el paso de mensajes.

Introducción

La palabra distribuido en términos como "sistema distribuido", "programación distribuida" y "algoritmo distribuido" originalmente se refería a las redes de computadoras donde las computadoras individuales estaban distribuidas físicamente dentro de un área geográfica. Los términos se usan hoy en día en un sentido mucho más amplio, incluso se refieren a procesos autónomos que se ejecutan en la misma computadora física e interactúan entre sí mediante el paso de mensajes.

Si bien no existe una definición única de un sistema distribuido, las siguientes propiedades definitorias se usan comúnmente como:

• Hay varias entidades computacionales autónomas (computadoras o nodos), cada uno de los cuales tiene su propia memoria local.
• Las entidades se comunican entre sí por mensaje que pasa.

Un sistema distribuido puede tener un objetivo común, como resolver un gran problema computacional; el usuario entonces percibe la colección de procesadores autónomos como una unidad. Alternativamente, cada computadora puede tener su propio usuario con necesidades individuales, y el propósito del sistema distribuido es coordinar el uso de recursos compartidos o brindar servicios de comunicación a los usuarios.

Otras propiedades típicas de los sistemas distribuidos incluyen las siguientes:

• El sistema tiene que tolerar fallos en computadoras individuales.
• La estructura del sistema (topología de red, latencia de red, número de computadoras) no se conoce con antelación, el sistema puede consistir en diferentes tipos de ordenadores y enlaces de red, y el sistema puede cambiar durante la ejecución de un programa distribuido.
• Cada ordenador tiene una visión limitada e incompleta del sistema. Cada ordenador puede conocer sólo una parte de la entrada.

Computación paralela y distribuida

a), b): un sistema distribuido.
c): un sistema paralelo.

Los sistemas distribuidos son grupos de computadoras en red que comparten un objetivo común para su trabajo. Los términos "computación concurrente", "computación paralela" y "computación distribuida" tienen mucha superposición, y no existe una distinción clara entre ellos. El mismo sistema puede caracterizarse tanto como "paralelo" y "distribuido"; los procesadores en un sistema distribuido típico se ejecutan simultáneamente en paralelo. La computación paralela puede verse como una forma particular estrechamente acoplada de computación distribuida, y la computación distribuida puede verse como una forma débilmente acoplada de computación paralela. Sin embargo, es posible clasificar aproximadamente los sistemas concurrentes como "paralelos" o "distribuido" utilizando los siguientes criterios:

• En computación paralela, todos los procesadores pueden tener acceso a una memoria compartida para intercambiar información entre procesadores.
• En el cálculo distribuido, cada procesador tiene su propia memoria privada (memoria distribuida). La información se intercambia por mensajes que pasan entre los procesadores.

La figura de la derecha ilustra la diferencia entre sistemas distribuidos y paralelos. La figura (a) es una vista esquemática de un sistema distribuido típico; el sistema se representa como una topología de red en la que cada nodo es una computadora y cada línea que conecta los nodos es un enlace de comunicación. La figura (b) muestra el mismo sistema distribuido con más detalle: cada computadora tiene su propia memoria local y la información se puede intercambiar solo al pasar mensajes de un nodo a otro utilizando los enlaces de comunicación disponibles. La figura (c) muestra un sistema paralelo en el que cada procesador tiene acceso directo a una memoria compartida.

La situación se complica aún más por los usos tradicionales de los términos algoritmo paralelo y distribuido que no coinciden con las definiciones anteriores de sistemas paralelos y distribuidos (ver más abajo para discusión más detallada). Sin embargo, como regla general, el cómputo paralelo de alto rendimiento en un multiprocesador de memoria compartida utiliza algoritmos paralelos, mientras que la coordinación de un sistema distribuido a gran escala utiliza algoritmos distribuidos.

Historia

El uso de procesos concurrentes que se comunican a través del paso de mensajes tiene sus raíces en las arquitecturas de sistemas operativos estudiadas en la década de 1960. Los primeros sistemas distribuidos generalizados fueron redes de área local como Ethernet, que se inventó en la década de 1970.

ARPANET, uno de los predecesores de Internet, se introdujo a fines de la década de 1960 y el correo electrónico de ARPANET se inventó a principios de la década de 1970. El correo electrónico se convirtió en la aplicación más exitosa de ARPANET, y es probablemente el primer ejemplo de una aplicación distribuida a gran escala. Además de ARPANET (y su sucesora, la Internet global), otras redes informáticas mundiales tempranas incluyeron Usenet y FidoNet de la década de 1980, las cuales se utilizaron para admitir sistemas de debate distribuidos.

El estudio de la computación distribuida se convirtió en su propia rama de la informática a fines de la década de 1970 y principios de la de 1980. La primera conferencia en el campo, el Simposio sobre Principios de Computación Distribuida (PODC), data de 1982, y su contraparte, el Simposio Internacional sobre Computación Distribuida (DISC), se llevó a cabo por primera vez en Ottawa en 1985 como el Taller Internacional sobre Algoritmos Distribuidos en Gráficos.

Arquitecturas

Se utilizan varias arquitecturas de hardware y software para la computación distribuida. En un nivel inferior, es necesario interconectar varias CPU con algún tipo de red, independientemente de si esa red está impresa en una placa de circuito o está formada por dispositivos y cables acoplados de forma flexible. En un nivel superior, es necesario interconectar los procesos que se ejecutan en esas CPU con algún tipo de sistema de comunicación.

La programación distribuida generalmente cae en una de varias arquitecturas básicas: cliente-servidor, tres niveles, n niveles o punto a punto; o categorías: acoplamiento flojo, o acoplamiento estrecho.

• Cliente-servidor: arquitecturas donde los clientes inteligentes contactan con el servidor para los datos y luego formatearlos y mostrarlos a los usuarios. La entrada en el cliente se compromete de nuevo al servidor cuando representa un cambio permanente.
• Tres niveles: arquitecturas que mueven la inteligencia del cliente a un nivel medio para que los clientes apátridas puedan ser utilizados. Esto simplifica el despliegue de aplicaciones. La mayoría de las aplicaciones web son de tres niveles.
• n-tier: arquitecturas que se refieren típicamente a aplicaciones web que promueven sus solicitudes a otros servicios empresariales. Este tipo de aplicación es el más responsable del éxito de los servidores de aplicaciones.
• Peer-to-peer: arquitecturas donde no hay máquinas especiales que proporcionan un servicio o gestionan los recursos de red. En cambio, todas las responsabilidades se dividen uniformemente entre todas las máquinas, conocidas como iguales. Peers puede servir tanto como clientes y como servidores. Ejemplos de esta arquitectura incluyen BitTorrent y la red bitcoin.

Otro aspecto básico de la arquitectura informática distribuida es el método de comunicación y coordinación del trabajo entre procesos concurrentes. A través de varios protocolos de paso de mensajes, los procesos pueden comunicarse directamente entre sí, normalmente en una relación maestro/esclavo. Alternativamente, un "centrado en la base de datos" La arquitectura puede permitir que la computación distribuida se realice sin ningún tipo de comunicación directa entre procesos, utilizando una base de datos compartida. La arquitectura centrada en la base de datos, en particular, proporciona análisis de procesamiento relacional en una arquitectura esquemática que permite la retransmisión del entorno en vivo. Esto permite funciones informáticas distribuidas tanto dentro como fuera de los parámetros de una base de datos en red.

Aplicaciones

Las razones para usar sistemas distribuidos y computación distribuida pueden incluir:

• La naturaleza misma de una solicitud puede necesidad el uso de una red de comunicación que conecta varias computadoras: por ejemplo, datos producidos en una ubicación física y requeridos en otra ubicación.
• Hay muchos casos en que el uso de una sola computadora sería posible en principio, pero el uso de un sistema distribuido es beneficios por razones prácticas. Por ejemplo:
  • Puede permitir un almacenamiento y memoria mucho más grande, un cálculo más rápido y un ancho de banda más alto que una sola máquina.
  • Puede proporcionar más fiabilidad que un sistema no distribuido, ya que no hay un solo punto de fracaso. Además, un sistema distribuido puede ser más fácil de expandir y gestionar que un sistema monolítico de uniprocesador.
  • Puede ser más rentable obtener el nivel de rendimiento deseado utilizando un clúster de varios ordenadores de gama baja, en comparación con un solo ordenador de alta gama.

Ejemplos

Ejemplos de sistemas distribuidos y aplicaciones de computación distribuida incluyen los siguientes:

• redes de telecomunicaciones:
  • redes telefónicas y redes celulares,
  • redes informáticas como Internet,
  • redes de sensores inalámbricos,
  • algoritmos de enrutamiento;
• aplicaciones de red:
  • World Wide Web and peer-to-peer networks,
  • masivo multijugador juegos en línea y comunidades de realidad virtual,
  • distribuyó bases de datos y distribuyó sistemas de gestión de bases de datos,
  • sistemas de archivos de red,
  • caché distribuido como buffers,
  • sistemas de procesamiento de información distribuidos, como sistemas bancarios y sistemas de reserva de líneas aéreas;
• control de proceso en tiempo real:
  • sistemas de control de aeronaves,
  • sistemas de control industrial;
• computación paralela:
  • computación científica, incluyendo computación de racimos, computación de rejillas, computación de nubes y varios proyectos de computación voluntaria,
  • renderizado en gráficos de ordenador.
• par-to-peer

Fundamentos teóricos

Modelos

Muchas tareas que nos gustaría automatizar usando una computadora son del tipo pregunta-respuesta: nos gustaría hacer una pregunta y la computadora debería producir una respuesta. En informática teórica, tales 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 respuestas deseadas a estas preguntas.

La informática teórica busca comprender qué problemas computacionales se pueden resolver mediante el uso de una computadora (teoría de la computabilidad) y con qué eficiencia (teoría de la complejidad computacional). Tradicionalmente, se dice que un problema se puede resolver usando una computadora si podemos diseñar un algoritmo que produzca una solución correcta para cualquier instancia dada. Dicho algoritmo se puede implementar como un programa de computadora que se ejecuta en una computadora de propósito general: el programa lee una instancia de problema de la entrada, realiza algunos cálculos y produce la solución como salida. Los formalismos como las máquinas de acceso aleatorio o las máquinas universales de Turing se pueden usar como modelos abstractos de una computadora secuencial de propósito general que ejecuta dicho algoritmo.

El campo de la computación concurrente y distribuida estudia preguntas similares en el caso de varias computadoras o una computadora que ejecuta una red de procesos interactivos: ¿qué problemas computacionales se pueden resolver en dicha red y con qué eficiencia? Sin embargo, no es del todo obvio lo que significa "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 una computadora secuencial de propósito general?

La discusión a continuación se centra en el caso de varias computadoras, aunque muchos de los problemas son los mismos para los procesos simultáneos que se ejecutan en una sola computadora.

Comúnmente se utilizan tres puntos de vista:

algoritmos paralelos en el modelo de memoria compartida

• Todos los procesadores tienen acceso a una memoria compartida. El diseñador de algoritmos elige el programa ejecutado por cada procesador.
• Un modelo teórico es las máquinas de acceso aleatorio paralelo (PRAM) que se utilizan. Sin embargo, el modelo clásico PRAM asume acceso sincronizado a la memoria compartida.
• Los programas de memoria compartida pueden ampliarse a sistemas distribuidos si el sistema operativo subyacente encapsula la comunicación entre los nodos y virtualmente unifica la memoria en todos los sistemas individuales.
• Un modelo que está más cerca del comportamiento de las máquinas multiprocesadoras del mundo real y tiene en cuenta el uso de instrucciones de la máquina, como Compare-and-swap (CAS), es el de memoria compartida asincrónica. Hay un amplio conjunto de trabajos sobre este modelo, un resumen de los cuales se puede encontrar en la literatura.

algoritmos paralelos en modelo de paso de mensajes

• El diseñador de algoritmos elige la estructura de la red, así como el programa ejecutado por cada ordenador.
• Se utilizan modelos como circuitos booleanos y redes de clasificación. Un circuito booleano se puede ver como una red informática: cada puerta es un ordenador que ejecuta un programa de computadora extremadamente simple. Análogamente, una red de clasificación puede considerarse como una red informática: cada comparador es un ordenador.

algoritmos distribuidos en el modelo de paso de mensajes

• El diseñador de algoritmos solo elige el programa informático. 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 gráfico con una máquina de estado finito por nodo.

En el caso de los algoritmos distribuidos, los problemas computacionales suelen estar relacionados con los gráficos. 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 ejemplo

Considere el problema computacional de encontrar una coloración de un gráfico dado G. Diferentes campos pueden adoptar los siguientes enfoques:

algoritmos centralizados

• El gráfico 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 gráfico, codifica la coloración como una cadena y produce el resultado.

algoritmos paralelos

• Otra vez, el gráfico G está codificado como una cadena. Sin embargo, múltiples ordenadores pueden acceder a la misma cadena en paralelo. Cada ordenador podría centrarse en una parte del gráfico y producir un colorante para esa parte.
• El foco principal es en la computación de alto rendimiento que explota el poder de procesamiento de múltiples ordenadores en paralelo.

algoritmos distribuidos

• El gráfico G es la estructura de la red informática. Hay una computadora para cada nodo de G y un enlace de comunicación para cada borde de G. Inicialmente, cada ordenador sólo sabe de sus vecinos inmediatos en el gráfico G; los ordenadores deben intercambiar mensajes entre sí para descubrir más sobre la estructura G. Cada ordenador debe producir su propio color como salida.
• El objetivo principal es coordinar el funcionamiento de un sistema distribuido arbitrariamente.

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

Además, un algoritmo paralelo se puede implementar en un sistema paralelo (usando memoria compartida) o en un sistema distribuido (usando el paso de mensajes). El límite tradicional entre algoritmos paralelos y distribuidos (elegir una red adecuada frente a ejecutar en cualquier red dada) no se encuentra en el mismo lugar que el límite entre sistemas paralelos y distribuidos (memoria compartida frente a paso de mensajes).

Medidas de complejidad

En los algoritmos paralelos, otro recurso además del tiempo y el espacio es la cantidad de computadoras. De hecho, a menudo hay una compensación entre el tiempo de ejecución y la cantidad de computadoras: el problema se puede resolver más rápido si hay más computadoras ejecutándose en paralelo (ver aceleración). Si un problema de decisión se puede resolver en tiempo polilogarítmico utilizando un número polinomial de procesadores, se dice que el problema es de clase NC. La clase NC se puede definir igualmente bien utilizando el formalismo PRAM o los circuitos booleanos: las máquinas PRAM pueden simular circuitos booleanos de manera eficiente y viceversa.

En el análisis de algoritmos distribuidos, se suele prestar más atención a las operaciones de comunicación que a los pasos computacionales. Quizás el modelo más simple de computación distribuida es un sistema síncrono en el que todos los nodos funcionan al unísono. Este modelo se conoce comúnmente como el 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 tales sistemas, una medida de complejidad central es el número de rondas de comunicación sincrónica requeridas 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 trivialmente en un sistema distribuido sincrónico en aproximadamente 2 rondas de comunicación D: simplemente reúna toda la información en una ubicación (rondas D), resolver el problema e informar a cada nodo sobre la solución (rondas D).

Por otro lado, si el tiempo de ejecución del algoritmo es mucho más pequeño que las rondas de comunicación D, entonces los nodos en 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 que está disponible en su vecindario D local. Se conocen muchos algoritmos distribuidos con un tiempo de ejecución mucho más pequeño que las rondas D, y comprender qué problemas pueden resolver dichos algoritmos es una de las preguntas centrales de investigación en este campo. Normalmente, 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 generalmente se capturan con el modelo CONGEST(B), que se define de manera similar al modelo LOCAL, pero donde los mensajes individuales solo pueden contener bits B.

Otros problemas

Los problemas computacionales tradicionales toman la perspectiva de que el usuario hace una pregunta, una computadora (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, incluido 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 ni puntos muertos.

También existen desafíos fundamentales que son exclusivos de la computación distribuida, por ejemplo, los relacionados con la tolerancia a fallas. Los ejemplos de problemas relacionados incluyen problemas de consenso, tolerancia a fallas bizantinas y autoestabilización.

Gran parte de la investigación también se centra en comprender la naturaleza asincrónica de los sistemas distribuidos:

• Los sincronizadores se pueden utilizar para ejecutar algoritmos sincronizados en sistemas asincrónicos.
• Los relojes lógicos proporcionan una causal antes de ordenar eventos.
• Los algoritmos de sincronización del reloj proporcionan sellos de tiempo físico globalmente consistentes.

Elección

Elección de coordinador (o elección de líder) es el proceso de designar un único proceso como organizador de alguna tarea distribuida entre varios ordenadores (nodos). Antes de que comience la tarea, todos los nodos de la red desconocen qué nodo servirá como "coordinador" (o líder) de la tarea, o incapaz de comunicarse con el coordinador actual. Sin embargo, después de ejecutar un algoritmo de elección de coordinador, cada nodo de la red reconoce un nodo único y particular como coordinador de la tarea.

Los nodos de la red se comunican entre sí para decidir cuál de ellos entrará en el "coordinador" Expresar. Para eso, 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 a menudo se atribuye a LeLann, quien lo formalizó como un método para crear un nuevo token en una red token ring en la que se ha perdido el token.

Los algoritmos de elección de coordinadores están diseñados para ser económicos en términos de bytes totales transmitidos y tiempo. El algoritmo sugerido por Gallager, Humblet y Spira para gráficos generales no dirigidos 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 computación distribuida.

Se sugirieron muchos otros algoritmos para diferentes tipos de gráficos de red, como anillos no dirigidos, anillos unidireccionales, gráficos completos, cuadrículas, gráficos de Euler dirigidos y otros. Korach, Kutten y Moran sugirieron un método general que separa el problema de la familia de grafos del diseño del algoritmo de elección del coordinador.

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

Propiedades de los sistemas distribuidos

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

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

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 estados finitos. Un ejemplo es saber si una red determinada 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.