Un sistema distribuido es un sistema cuyos componentes están ubicados en diferentes computadoras en red , que se comunican y coordinan sus acciones pasándose mensajes entre sí. [1] [2] 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 simultaneidad de los componentes, superar la falta de un reloj global y gestionar las fallas independientes de los componentes. [1] Cuando falla un componente de un sistema, no falla todo el sistema. [3] Los ejemplos de sistemas distribuidos varían desde sistemas basados en SOA hasta juegos en línea multijugador masivo y aplicaciones peer-to-peer .
Un programa de computadora que se ejecuta dentro de un sistema distribuido se llama programa distribuido , [4] y la programación distribuida es el proceso de escribir dichos programas. [5] Hay muchos tipos diferentes de implementaciones para el mecanismo de paso de mensajes, incluidos HTTP puro, conectores tipo RPC y colas de mensajes . [6]
La computación distribuida también se refiere al uso de sistemas distribuidos para resolver problemas computacionales. En la informática distribuida , un problema se divide en muchas tareas, cada una de las cuales es resuelta por una o más computadoras, [7] que se comunican entre sí mediante el paso de mensajes. [8]
La palabra distribuido en términos como "sistema distribuido", "programación distribuida" y " algoritmo distribuido " originalmente se refería a redes de computadoras donde las computadoras individuales estaban físicamente distribuidas dentro de algún área geográfica. [9] Los términos se utilizan hoy en día en un sentido mucho más amplio, incluso refiriéndose a procesos autónomos que se ejecutan en la misma computadora física e interactúan entre sí mediante el paso de mensajes. [8]
Si bien no existe una definición única de un sistema distribuido, [10] las siguientes propiedades definitorias se usan comúnmente como:
Un sistema distribuido puede tener un objetivo común, como resolver un gran problema computacional; [13] el usuario percibe entonces 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. [14]
Otras propiedades típicas de los sistemas distribuidos incluyen las siguientes:
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" se superponen mucho y no existe una distinción clara entre ellos. [18] El mismo sistema puede caracterizarse como "paralelo" y "distribuido"; Los procesadores en un sistema distribuido típico se ejecutan simultáneamente en paralelo. [19] La computación paralela puede verse como una forma de computación distribuida particularmente estrechamente acoplada, [20] y la computación distribuida puede verse como una forma de computación paralela débilmente acoplada. [10] Sin embargo, es posible clasificar aproximadamente 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 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 del todo con las definiciones anteriores de sistemas paralelos y distribuidos (ver más abajo para una discusión más detallada). Sin embargo, 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. [23]
El uso de procesos concurrentes que se comunican mediante el paso de mensajes tiene sus raíces en las arquitecturas de sistemas operativos estudiadas en la década de 1960. [24] Los primeros sistemas distribuidos generalizados fueron las redes de área local como Ethernet , que se inventó en la década de 1970. [25]
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 [26] y probablemente sea el primer ejemplo de una aplicación distribuida a gran escala . Además de ARPANET (y su sucesora, la Internet global), otras primeras redes informáticas mundiales incluyeron Usenet y FidoNet de la década de 1980, las cuales se utilizaron para respaldar sistemas de discusión distribuidos. [27]
El estudio de la computación distribuida se convirtió en su propia rama de la informática a finales de los años 1970 y principios de los 1980. La primera conferencia en este 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. [28]
Se utilizan diversas arquitecturas de hardware y software para la informática 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 formada por dispositivos y cables débilmente acoplados. En un nivel superior, es necesario interconectar los procesos que se ejecutan en esas CPU con algún tipo de sistema de comunicación . [29]
Que estas CPU compartan recursos o no determina una primera distinción entre tres tipos de arquitectura:
La programación distribuida normalmente se divide en una de varias arquitecturas básicas: cliente-servidor , de tres niveles , de n niveles o de igual a igual ; o categorías: acoplamiento flojo o acoplamiento apretado . [30]
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 principal/sub. Alternativamente, una arquitectura "centrada en la base de datos" puede permitir que la computación distribuida se realice sin ningún tipo de comunicación directa entre procesos , mediante la utilización de una base de datos compartida . [33] La arquitectura centrada en bases 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. [34]
Las razones para utilizar sistemas distribuidos y computación distribuida pueden incluir:
Ejemplos de sistemas distribuidos y aplicaciones de informática distribuida incluyen los siguientes: [36]
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 , estas tareas se denominan problemas computacionales . Formalmente, un problema computacional consta de instancias junto con una solución para cada instancia. Los ejemplos 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 utilizando 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 utilizando una computadora si podemos diseñar un algoritmo que produzca una solución correcta para un caso determinado. Un algoritmo de este tipo puede implementarse como un programa informático que se ejecuta en una computadora de uso general: el programa lee una instancia del problema desde la entrada , realiza algunos cálculos y produce la solución como salida . Formalismos como las máquinas de acceso aleatorio o las máquinas universales de Turing se pueden utilizar como modelos abstractos de una computadora secuencial de propósito general que ejecuta dicho algoritmo. [38] [39]
El campo de la computación concurrente y distribuida estudia cuestiones similares en el caso de varias computadoras o de 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 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 un sistema secuencial. computadora de uso general? [ cita necesaria ]
La discusión a continuación se centra en el caso de varias computadoras, aunque muchos de los problemas son los mismos para procesos simultáneos que se ejecutan en una sola computadora.
Generalmente se utilizan tres puntos de vista:
En el caso de los algoritmos distribuidos, los problemas computacionales suelen estar relacionados con gráficos. A menudo, el ejemplo del problema es el gráfico que describe la estructura de la red informática . Esto se ilustra en el siguiente ejemplo. [44]
Considere 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 campo de los algoritmos distribuidos, existe mucha interacción entre los dos campos. Por ejemplo, el algoritmo Cole-Vishkin para colorear gráficos [45] 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). [46] El límite tradicional entre algoritmos paralelos y distribuidos (elegir una red adecuada versus ejecutar en cualquier red determinada) no se encuentra en el mismo lugar que el límite entre sistemas paralelos y distribuidos (memoria compartida versus paso de mensajes).
En los algoritmos paralelos, otro recurso además del tiempo y el espacio es el número de ordenadores. De hecho, a menudo existe 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 funcionando en paralelo (consulte aceleración ). Si un problema de decisión se puede resolver en tiempo polilogarítmico utilizando un número polinomial de procesadores, entonces se dice que el problema es de la clase NC . [47] 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. [48]
En el análisis de algoritmos distribuidos, normalmente se presta 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 síncrono donde todos los nodos operan al unísono. 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 tales sistemas, una medida central de complejidad es el número de rondas de comunicación síncronas necesarias para completar la tarea. [49]
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 síncrono en aproximadamente 2 rondas de comunicación D : simplemente reúna toda la información en una ubicación ( D rondas), resuelva el problema e informe 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 vecindario D local . Se conocen muchos algoritmos distribuidos con un tiempo de ejecución mucho menor que las rondas D , y comprender qué problemas pueden resolverse mediante dichos algoritmos es una de las preguntas de investigación centrales en este campo. [50] Normalmente, en este modelo se considera eficiente un algoritmo que resuelve un problema en tiempo polilogarítmico en el tamaño de la red.
Otra medida comúnmente utilizada es el número total de bits transmitidos en la red (cf. complejidad de la comunicación ). [51] 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.
Los problemas computacionales tradicionales adoptan 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 comensales y otros problemas similares de exclusión mutua . En estos problemas, se supone que el sistema distribuido coordina continuamente el uso de 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 los relacionados con la tolerancia a fallas . Ejemplos de problemas relacionados incluyen problemas de consenso , [52] tolerancia a fallas bizantinas , [53] y autoestabilización . [54]
Gran parte de la investigación también se centra en comprender la naturaleza asincrónica de los sistemas distribuidos:
La elección de coordinador (o elección de líder ) es el proceso de designar un solo proceso como organizador de alguna tarea distribuida entre varias computadoras (nodos). Antes de que comience 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 único y particular como coordinador de tareas. [58]
Los nodos de la red se comunican entre sí para decidir cuál de ellos pasará al estado de "coordinador". Para eso necesitan algún método que rompa 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. [58]
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 el token se ha perdido. [59]
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 [60] 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 desacopla la cuestión de la familia de gráficos del diseño del algoritmo de elección del coordinador. [61]
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 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 del coordinador central. [62]
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 el estudio de las propiedades de un sistema distribuido determinado. [63] [64]
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. [sesenta y cinco]
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 estados finitos que interactúan (asincrónicas y no deterministas) puede llegar a un punto muerto. Este problema es PSPACE-completo , [66] 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 físicamente distribuidos que funcionan de forma independiente utilizando su almacenamiento privado, pero que también se comunican de vez en cuando mediante el paso de mensajes explícitos. Estos sistemas se denominan sistemas distribuidos.
Los programas distribuidos son descripciones abstractas de sistemas distribuidos. Un programa distribuido consta de una colección de procesos que funcionan simultáneamente y se comunican mediante el paso de mensajes explícitos. Cada proceso puede acceder a un conjunto de variables que son independientes de las variables que pueden ser modificadas por cualquier otro proceso.
{{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
