La computación distribuida es un campo de la informática que estudia los sistemas distribuidos , definidos como sistemas informáticos cuyos componentes intercomunicados están ubicados en diferentes computadoras en red . [1] [2]
Los componentes de un sistema distribuido se comunican y coordinan sus acciones pasándose mensajes entre sí para alcanzar 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 el fallo independiente de los componentes. [1] Cuando un componente de un sistema falla, no falla todo el sistema. [3] Los ejemplos de sistemas distribuidos varían desde sistemas basados en SOA hasta microservicios , juegos en línea multijugador masivos y aplicaciones peer-to-peer . Los sistemas distribuidos cuestan significativamente más que las arquitecturas monolíticas, principalmente debido a las mayores necesidades de hardware adicional, servidores, puertas de enlace, cortafuegos, nuevas subredes, proxies, etc. [4] Además, los sistemas distribuidos son propensos a las falacias de la computación distribuida . Por otro lado, un sistema distribuido bien diseñado es más escalable, más duradero, más cambiante y más ajustado que una aplicación monolítica implementada en una sola máquina. [5]
Un programa informático que se ejecuta dentro de un sistema distribuido se denomina programa distribuido [6] , y la programación distribuida es el proceso de escribir dichos programas. [7] Hay muchos tipos diferentes de implementaciones para el mecanismo de paso de mensajes, incluidos HTTP puro, conectores tipo RPC y colas de mensajes . [8]
La 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, [9] que se comunican entre sí mediante el paso de mensajes. [10]
La palabra distribuido, en términos como "sistema distribuido", "programación distribuida" y " algoritmo distribuido ", se refería originalmente a redes informáticas en las que los ordenadores individuales estaban distribuidos físicamente dentro de un área geográfica. [11] Hoy en día, los términos se utilizan en un sentido mucho más amplio, incluso haciendo referencia a procesos autónomos que se ejecutan en el mismo ordenador físico e interactúan entre sí mediante el paso de mensajes. [10]
Si bien no existe una definición única de un sistema distribuido, [12] las siguientes propiedades definitorias se utilizan comúnmente como:
Un sistema distribuido puede tener un objetivo común, como resolver un gran problema computacional; [15] entonces el usuario percibe el conjunto 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 proporcionar servicios de comunicación a los usuarios. [16]
Otras propiedades típicas de los sistemas distribuidos incluyen las siguientes:
A continuación se presentan patrones arquitectónicos comunes utilizados para la computación distribuida: [20]
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. [21] El mismo sistema puede caracterizarse como "paralelo" y "distribuido"; los procesadores en un sistema distribuido típico funcionan simultáneamente en paralelo. [22] La computación paralela puede verse como una forma particularmente acoplada de computación distribuida, [23] y la computación distribuida puede verse como una forma débilmente acoplada de computación paralela. [12] Sin embargo, es posible clasificar a grandes rasgos los sistemas concurrentes como "paralelos" o "distribuidos" utilizando los siguientes criterios:
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 solo se puede intercambiar pasando mensajes de un nodo a otro mediante 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 exactamente con las definiciones anteriores de sistemas paralelos y distribuidos (véase más adelante un análisis más detallado). No obstante, como regla general, la computación paralela 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. [26]
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. [27] Los primeros sistemas distribuidos generalizados fueron las redes de área local como Ethernet , que se inventó en la década de 1970. [28]
ARPANET , uno de los predecesores de Internet , se introdujo a finales de los años 1960, y el correo electrónico ARPANET se inventó a principios de los años 1970. El correo electrónico se convirtió en la aplicación más exitosa de ARPANET, [29] 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 los años 1980, ambas utilizadas para dar soporte a sistemas de discusión distribuidos. [30]
El estudio de la computación distribuida se convirtió en una rama propia de la ciencia informática a finales de los años 1970 y principios de los años 1980. La primera conferencia en el campo, el Simposio sobre Principios de Computación Distribuida (PODC), se remonta a 1982, y su homólogo, el Simposio Internacional sobre Computación Distribuida (DISC), se celebró por primera vez en Ottawa en 1985 como el Taller Internacional sobre Algoritmos Distribuidos en Gráficos. [31]
Para la computación distribuida se utilizan diversas arquitecturas de hardware y software. 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 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 . [32]
El hecho de que estas CPU compartan recursos o no determina una primera distinción entre tres tipos de arquitectura:
La programación distribuida generalmente se clasifica en una de varias arquitecturas básicas: cliente-servidor , tres niveles , n niveles o peer-to-peer ; o categorías: acoplamiento flexible o acoplamiento estrecho . [33]
Otro aspecto básico de la arquitectura de computación 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 principal/secundaria. Alternativamente, una arquitectura "centrada en la base de datos" puede permitir que la computación distribuida se realice sin ninguna forma de comunicación directa entre procesos , utilizando una base de datos compartida . [36] 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 de computación distribuida tanto dentro como fuera de los parámetros de una base de datos en red. [37]
Las razones para utilizar sistemas distribuidos y computación distribuida pueden incluir:
Entre los ejemplos de sistemas distribuidos y aplicaciones de computación distribuida se incluyen los siguientes: [39]
Muchas tareas que nos gustaría automatizar mediante el uso de una computadora son del tipo pregunta-respuesta: nos gustaría hacer una pregunta y la computadora debería 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 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 mediante el uso de una computadora si podemos diseñar un algoritmo que produzca una solución correcta para cualquier instancia dada. Tal algoritmo se puede implementar como un programa de computadora que se ejecuta en una computadora de propósito general: el programa lee una instancia del problema desde la entrada , realiza algún cálculo y produce la solución como salida . Los formalismos como las máquinas de acceso aleatorio o las máquinas de Turing universales se pueden utilizar como modelos abstractos de una computadora secuencial de propósito general que ejecuta dicho algoritmo. [41] [42]
El campo de la computación concurrente y distribuida estudia cuestiones similares en el caso de múltiples computadoras o de una computadora que ejecuta una red de procesos que interactúan: ¿qué problemas computacionales se pueden resolver en dicha red y con qué eficiencia? Sin embargo, no resulta del todo obvio qué 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 del algoritmo y cuál es el equivalente concurrente o distribuido de una computadora secuencial de propósito general? [ cita requerida ]
El debate 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.
Se utilizan habitualmente tres puntos de vista:
En el caso de algoritmos distribuidos, los problemas computacionales suelen estar relacionados con grafos. A menudo, el grafo que describe la estructura de la red informática es la instancia del problema. Esto se ilustra en el siguiente ejemplo. [47]
Consideremos el problema computacional de encontrar una coloración de un gráfico dado G. Diferentes campos podrían adoptar los siguientes enfoques:
Si bien el campo de los algoritmos paralelos tiene un enfoque diferente al de los algoritmos distribuidos, existe mucha interacción entre ambos campos. Por ejemplo, el algoritmo Cole-Vishkin para la coloración de grafos [48] se presentó originalmente como un algoritmo paralelo, pero la misma técnica también se puede utilizar 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 paso de mensajes). [49] El límite tradicional entre algoritmos paralelos y distribuidos (elegir una red adecuada vs. ejecutar en una red dada) no se encuentra en el mismo lugar que el límite entre sistemas paralelos y distribuidos (memoria compartida vs. paso de mensajes).
En los algoritmos paralelos, otro recurso además del tiempo y el espacio es la cantidad de computadoras. De hecho, a menudo existe un equilibrio 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 una cantidad polinómica de procesadores, entonces se dice que el problema pertenece a la clase NC . [50] La clase NC se puede definir igualmente bien utilizando el formalismo PRAM o circuitos booleanos: las máquinas PRAM pueden simular circuitos booleanos de manera eficiente y viceversa. [51]
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 sea un sistema sincrónico donde todos los nodos operan en forma sincronizada. 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 central de complejidad es el número de rondas de comunicación sincrónica requeridas para completar la tarea. [52]
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 se puede resolver de manera trivial en un sistema distribuido sincrónico en aproximadamente 2 D rondas de comunicación: simplemente se reúne toda la información en una ubicación ( D rondas), se resuelve el problema y se informa 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 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 local D. Se conocen muchos algoritmos distribuidos con un tiempo de ejecución mucho menor que D rondas, y comprender qué problemas se pueden resolver con dichos algoritmos es una de las preguntas centrales de investigación en el campo. [53] 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 ). [54] Las características de este concepto se capturan típicamente con el modelo CONGEST(B), que se define de manera similar al modelo LOCAL, pero donde los mensajes individuales solo pueden contener B bits.
Los problemas computacionales tradicionales parten de la base de que el usuario formula una pregunta, un ordenador (o un sistema distribuido) procesa la pregunta, produce una respuesta y se detiene. Sin embargo, también hay problemas en los que se requiere que el sistema no se detenga, como el problema de los filósofos que cenan y otros problemas similares de exclusión mutua . En estos problemas, se supone que el sistema distribuido debe coordinar continuamente el uso de los recursos compartidos para que no se produzcan conflictos ni bloqueos .
También existen desafíos fundamentales que son exclusivos de la computación distribuida, por ejemplo, aquellos relacionados con la tolerancia a fallas . Algunos ejemplos de problemas relacionados incluyen problemas de consenso , [55] tolerancia a fallas bizantinas , [56] y autoestabilización . [57]
Mucha investigación también se centra en comprender la naturaleza asincrónica de los sistemas distribuidos:
Tenga en cuenta que en los sistemas distribuidos, la latencia debe medirse a través del "percentil 99" porque "mediana" y "promedio" pueden ser engañosos. [61]
La 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 se inicie la tarea, todos los nodos de la red desconocen qué nodo actuará como "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 un nodo particular y único como coordinador de la tarea. [62]
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 que rompa la simetría entre ellos. Por ejemplo, si cada nodo tiene identidades únicas y comparables, los nodos pueden comparar sus identidades y decidir que el nodo con la identidad más alta es el coordinador. [62]
La definición de este problema se atribuye a menudo a LeLann, quien 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. [63]
Los algoritmos de elección de coordinadores están diseñados para ser económicos en términos de total de bytes transmitidos y tiempo. El algoritmo sugerido por Gallager, Humblet y Spira [64] para grafos 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 han sugerido muchos otros algoritmos para diferentes tipos de grafos de red , como anillos no dirigidos, anillos unidireccionales, grafos completos, cuadrículas, grafos de Euler dirigidos y otros. Korach, Kutten y Moran sugirieron un método general que desvincula la cuestión de la familia de grafos del diseño del algoritmo de elección del coordinador. [65]
Para llevar a cabo la coordinación, los sistemas distribuidos emplean el concepto de coordinadores. El problema de elección de coordinadores 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 de coordinador central. [66]
Hasta ahora, el enfoque se ha centrado 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 determinado. [67] [68]
El problema de la detención es un ejemplo análogo en el campo de la computación centralizada: se nos da un programa de computadora y la tarea es decidir si se detiene o se ejecuta indefinidamente. El problema de la detención es indecidible en el caso general y, naturalmente, comprender el comportamiento de una red de computadoras es al menos tan difícil como comprender el comportamiento de una computadora. [69]
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 determinar si una red dada de máquinas de estados finitos que interactúan (asincrónicas y no deterministas) puede llegar a un punto muerto. Este problema es PSPACE-completo , [70] 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.
Los sistemas constan de una serie de componentes distribuidos físicamente que funcionan de forma independiente utilizando su almacenamiento privado, pero que también se comunican de vez en cuando mediante el paso explícito de mensajes. Estos sistemas se denominan sistemas distribuidos.
Los programas distribuidos son descripciones abstractas de sistemas distribuidos. Un programa distribuido consiste en una colección de procesos que funcionan simultáneamente y se comunican mediante el paso explícito de mensajes. Cada proceso puede acceder a un conjunto de variables que son distintas de las variables que pueden ser modificadas por cualquier otro proceso.
{{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
