Hispanopedia Wiki
Articulo de referencia

computación distribuida

La computación distribuida es un campo de la ciencia informática que estudia los sistemas distribuidos , definidos como sistemas informáticos cuyos componentes que se comunican ...

Hispanopedia WikiContenido en espanolLectura gratuita

La computación distribuida es un campo de la ciencia informática que estudia los sistemas distribuidos , definidos como sistemas informáticos cuyos componentes que se comunican entre sí se encuentran en diferentes computadoras en red . [ 1 ] [ 2 ]

Los componentes de un sistema distribuido se comunican y coordinan sus acciones mediante el intercambio de mensajes para alcanzar un objetivo común. Tres desafíos 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 falla un componente de un sistema, no falla todo el sistema. [ 3 ] Ejemplos de sistemas distribuidos abarcan desde sistemas basados ​​en SOA hasta microservicios , juegos multijugador masivos en línea y aplicaciones peer-to-peer . Los sistemas distribuidos son más costosos que las arquitecturas monolíticas, principalmente debido a la mayor necesidad de hardware adicional, servidores, gateways, firewalls, nuevas subredes, proxies, etc. [ 4 ] Los sistemas distribuidos también pueden sufrir las falacias de la computación distribuida . Por el contrario, un sistema distribuido bien diseñado es más escalable, más duradero, más adaptable y más preciso que una aplicación monolítica implementada en una sola máquina. [ 5 ] Según Marc Brooker: "un sistema es escalable en el rango donde el costo marginal de la carga de trabajo adicional es casi constante". Las tecnologías sin servidor se ajustan a esta definición, pero se debe considerar el costo total de propiedad, y no solo el costo de la infraestructura. [ 6 ]

Un programa informático que se ejecuta dentro de un sistema distribuido se denomina programa distribuido , [ 7 ] y la programación distribuida es el proceso de escribir dichos programas. [ 8 ] Existen muchos tipos de implementaciones para el mecanismo de paso de mensajes, incluyendo HTTP puro, conectores tipo RPC y colas de mensajes . [ 9 ]

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, [ 10 ] que se comunican entre sí mediante el paso de mensajes. [ 11 ]

Introducción

El término «distribuido», en expresiones como «sistema distribuido», «programación distribuida» y « algoritmo distribuido », se refería originalmente a redes informáticas donde los ordenadores individuales estaban distribuidos físicamente dentro de un área geográfica determinada. [ 12 ] Actualmente, estos términos se utilizan en un sentido mucho más amplio, incluso refiriéndose a procesos autónomos que se ejecutan en el mismo ordenador físico e interactúan entre sí mediante el paso de mensajes . [ 11 ]

No existe una única definición de sistema distribuido, [ 13 ] pero generalmente se citan dos propiedades comunes:

  • Hay varias entidades computacionales autónomas ( computadoras o nodos ), cada una de las cuales tiene su propia memoria local . [ 14 ]
  • Las entidades se comunican entre sí mediante el paso de mensajes. [ 15 ]

Un sistema distribuido puede tener un objetivo común, como resolver un problema computacional complejo; [ 16 ] 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. [ 17 ]

Otras propiedades típicas de los sistemas distribuidos son:

  • El sistema debe tolerar fallos en ordenadores individuales. [ 18 ]
  • La estructura del sistema (topología de la red, latencia de la red, número de ordenadores) no se conoce de antemano.
  • El sistema puede constar de diferentes tipos de ordenadores y enlaces de red.
  • El sistema puede cambiar durante la ejecución de un programa distribuido. [ 19 ]
  • Cada ordenador tiene una visión limitada e incompleta del sistema.
  • Cada computadora puede conocer solo una parte de la entrada. [ 20 ]

Patrones

Aquí se muestran patrones arquitectónicos comunes utilizados para la computación distribuida: [ 21 ]

Eventos vs. Mensajes

En los sistemas distribuidos, los eventos representan un hecho o un cambio de estado (por ejemplo, OrderPlaced ) y normalmente se transmiten de forma asíncrona a múltiples consumidores, lo que promueve el acoplamiento flexible y la escalabilidad. Si bien los eventos generalmente no esperan una respuesta inmediata, los mecanismos de confirmación suelen implementarse a nivel de infraestructura (por ejemplo, desplazamientos de confirmación de Kafka, estados de entrega de SNS) en lugar de ser una parte inherente del patrón de evento en sí. [ 22 ] [ 23 ]

En cambio, los mensajes desempeñan un papel más amplio, abarcando comandos (p. ej., ProcessPayment ), eventos (p. ej., PaymentProcessed ) y documentos (p. ej., DataPayload ). Tanto los eventos como los mensajes pueden admitir diversas garantías de entrega, incluyendo al menos una vez, como máximo una vez y exactamente una vez, según la pila tecnológica y la implementación. Sin embargo, la entrega exactamente una vez se suele lograr mediante mecanismos de idempotencia en lugar de una semántica de entrega exactamente una vez a nivel de infraestructura. [ 22 ] [ 23 ]

Los patrones de entrega para eventos y mensajes incluyen publicación/suscripción (uno a muchos) y punto a punto (uno a uno). Si bien la solicitud/respuesta es técnicamente posible, se asocia más comúnmente con patrones de mensajería que con sistemas puramente basados ​​en eventos. Los eventos destacan en la propagación de estado y las notificaciones desacopladas, mientras que los mensajes son más adecuados para la ejecución de comandos, la orquestación de flujos de trabajo y la coordinación explícita. [ 22 ] [ 23 ]

Las arquitecturas modernas suelen combinar ambos enfoques, aprovechando los eventos para las notificaciones de cambios de estado distribuidos y los mensajes para la ejecución de comandos específicos y flujos de trabajo estructurados basados ​​en requisitos específicos de tiempo, orden y entrega. [ 22 ] [ 23 ]

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" se superponen en gran medida y no existe una distinción clara entre ellos. [ 24 ] Un mismo sistema puede caracterizarse como "paralelo" y "distribuido"; los procesadores en un sistema distribuido típico se ejecutan concurrentemente en paralelo. [ 25 ] La computación paralela puede considerarse una forma particularmente acoplada de computación distribuida, [ 26 ] y la computación distribuida puede considerarse una forma débilmente acoplada de computación paralela. [ 13 ] Sin embargo, es posible clasificar aproximadamente los sistemas concurrentes como "paralelos" o "distribuidos" utilizando los siguientes criterios:

  • En la computación paralela, todos los procesadores pueden tener acceso a una memoria compartida para intercambiar información entre ellos. [ 27 ]
  • En la computación distribuida, cada procesador tiene su propia memoria privada ( memoria distribuida ). La información se intercambia mediante el paso de mensajes entre los procesadores. [ 28 ]

La figura de la derecha ilustra la diferencia entre sistemas distribuidos y paralelos. La figura (a) muestra un esquema de un sistema distribuido típico; este se representa como una topología de red en la que cada nodo es un ordenador y cada línea que conecta los nodos es un enlace de comunicación. La figura (b) muestra el mismo sistema distribuido con mayor detalle: cada ordenador tiene su propia memoria local, y la información solo se puede intercambiar mediante el envío de 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 (véase más adelante para 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. [ 29 ]

Historia

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

ARPANET , uno de los precursores de Internet , se introdujo a finales 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, [ 32 ] y es probablemente el primer ejemplo de una aplicación distribuida a gran escala . Además de ARPANET (y su sucesor, Internet global), otras redes informáticas mundiales tempranas incluyeron Usenet y FidoNet de la década de 1980, ambas utilizadas para dar soporte a sistemas de discusión distribuidos. [ 33 ]

El estudio de la computación distribuida se convirtió en una rama independiente de la informática a finales de la década de 1970 y principios de la de 1980. La primera conferencia en este 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 celebró por primera vez en Ottawa en 1985 como el Taller Internacional sobre Algoritmos Distribuidos en Grafos. [ 34 ]

Arquitecturas de computación distribuida

Para la computación distribuida se utilizan diversas arquitecturas de hardware y software. A un nivel inferior, es necesario interconectar múltiples CPU mediante algún tipo de red, ya sea impresa en una placa de circuitos o compuesta por dispositivos y cables conectados de forma flexible. A un nivel superior, es necesario interconectar los procesos que se ejecutan en esas CPU mediante algún tipo de sistema de comunicación . [ 35 ]

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 enmarca en una de varias arquitecturas básicas: cliente-servidor , de tres niveles , de n niveles o punto a punto ; o en categorías: acoplamiento débil o acoplamiento fuerte . [ 36 ]

Otro aspecto fundamental de la arquitectura de computación distribuida es el método de comunicación y coordinación del trabajo entre procesos concurrentes. Mediante diversos protocolos de paso de mensajes, los procesos pueden comunicarse directamente entre sí, generalmente en una relación principal/secundaria . Alternativamente, una arquitectura "centrada en la base de datos" permite realizar computación distribuida sin ningún tipo de comunicación directa entre procesos , mediante el uso de una base de datos compartida . [ 39 ] La arquitectura centrada en la base de datos, en particular, proporciona análisis de procesamiento relacional en una arquitectura esquemática que permite la transmisión en tiempo real. Esto habilita funciones de computación distribuida tanto dentro como fuera de los parámetros de una base de datos en red. [ 40 ]

Arquitectura basada en células

La arquitectura basada en celdas es un enfoque de computación distribuida en el que los recursos computacionales se organizan en unidades autónomas llamadas celdas. Cada celda opera de forma independiente, procesando solicitudes y manteniendo la escalabilidad, el aislamiento de fallos y la disponibilidad. [ 41 ] [ 42 ] [ 43 ]

Una celda generalmente consta de múltiples servicios o componentes de aplicación y funciona como una unidad autónoma. Algunas implementaciones replican conjuntos completos de servicios en varias celdas, mientras que otras distribuyen las cargas de trabajo entre ellas. En los modelos replicados, las solicitudes pueden redirigirse a una celda operativa si otra experimenta una falla. Este diseño busca mejorar la resiliencia del sistema al reducir el impacto de las fallas localizadas. [ 44 ] [ 45 ] [ 46 ]

Algunas implementaciones emplean disyuntores dentro y entre celdas. Dentro de una celda, los disyuntores pueden usarse para prevenir fallas en cascada entre servicios, mientras que los disyuntores entre celdas pueden aislar las celdas con fallas y redirigir el tráfico a las que permanecen operativas. [ 47 ] [ 48 ] [ 49 ]

La arquitectura basada en celdas se ha adoptado en algunos sistemas distribuidos a gran escala, particularmente en entornos nativos de la nube y de alta disponibilidad, donde el aislamiento de fallos y la redundancia son consideraciones de diseño clave. Su implementación varía según los requisitos del sistema, las limitaciones de la infraestructura y los objetivos operativos. [ 50 ] [ 51 ] [ 52 ]

Aplicaciones

Entre las razones para utilizar sistemas distribuidos y computación distribuida se incluyen:

  • La propia naturaleza de una aplicación puede requerir el uso de una red de comunicación que conecte varios ordenadores: por ejemplo, datos generados en una ubicación física y necesarios en otra.
  • Existen muchos casos en los que, en principio, sería posible utilizar un único ordenador, pero el uso de un sistema distribuido resulta beneficioso por razones prácticas. Por ejemplo:
    • Permite una capacidad de almacenamiento y memoria mucho mayor, una computación más rápida y un mayor ancho de banda que una sola máquina.
    • Puede proporcionar mayor fiabilidad que un sistema no distribuido, ya que no existe un único punto de fallo . Además, un sistema distribuido puede ser más fácil de ampliar y gestionar que un sistema monolítico de un solo procesador. [ 53 ]
    • Puede resultar más rentable obtener el nivel de rendimiento deseado utilizando un clúster de varios ordenadores de gama baja, en comparación con un único ordenador de gama alta.

Ejemplos

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

Sistemas distribuidos reactivos

Según el Manifiesto Reactivo, los sistemas distribuidos reactivos son receptivos, resilientes, elásticos y se basan en mensajes. Por consiguiente, los sistemas reactivos son más flexibles, están menos acoplados y son escalables. Para que sus sistemas sean reactivos, se recomienda implementar los Principios Reactivos. Estos principios y patrones ayudan a que tanto las aplicaciones nativas de la nube como las aplicaciones nativas de borde sean más reactivas. [ 56 ]

Fundamentos teóricos

Modelos

Muchas tareas que deseamos automatizar mediante una computadora son del tipo pregunta-respuesta: formulamos una pregunta y la computadora debe proporcionar 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. Las instancias son preguntas que podemos formular, y las soluciones son las respuestas deseadas a estas preguntas.

La informática teórica busca comprender qué problemas computacionales pueden resolverse mediante una computadora ( teoría de la computabilidad ) y con qué eficiencia ( teoría de la complejidad computacional ). Tradicionalmente, se dice que un problema puede resolverse mediante una computadora si se puede 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 una computadora de propósito general: el programa lee una instancia del problema como 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 una computadora secuencial de propósito general que ejecuta dicho algoritmo. [ 57 ] [ 58 ]

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 interactivos: ¿qué problemas computacionales pueden resolverse 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 de algoritmos y cuál es el equivalente concurrente o distribuido de un ordenador secuencial de propósito general?

El análisis que sigue se centra en el caso de varios ordenadores, aunque muchos de los problemas son los mismos para los procesos concurrentes que se ejecutan en un solo ordenador.

Se suelen utilizar tres puntos de vista:

Algoritmos paralelos en el 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 son las máquinas de acceso aleatorio paralelo (PRAM) que se utilizan. [ 59 ] Sin embargo, el modelo PRAM clásico supone 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 más cercano al comportamiento de las máquinas multiprocesador reales y que considera el uso de instrucciones de máquina, como Compare-and-swap (CAS), es el de memoria compartida asíncrona . Existe una amplia bibliografía sobre este modelo, cuyo resumen se puede encontrar en la literatura. [ 60 ] [ 61 ]
Algoritmos paralelos en el 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 circuitos booleanos y redes de ordenación . [ 62 ] Un circuito booleano puede considerarse una red informática: cada puerta es un ordenador que ejecuta un programa informático extremadamente simple. De manera similar, una red de ordenación puede considerarse una red informática: cada comparador es un ordenador.
Algoritmos distribuidos en el modelo de paso de mensajes
  • El diseñador del algoritmo 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 grafo con una máquina de estados finitos por nodo.

En el caso de los 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. [ 63 ]

Un ejemplo

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

Algoritmos centralizados [ 63 ]
  • El grafo G se codifica como una cadena de caracteres, y esta cadena se introduce en un ordenador. El programa informático encuentra una coloración del grafo, la codifica como una cadena de caracteres y muestra el resultado.
Algoritmos paralelos
  • Nuevamente, el grafo G se codifica como una cadena de caracteres. Sin embargo, varias computadoras pueden acceder a la misma cadena en paralelo. Cada computadora podría centrarse en una parte del grafo y generar un color para esa parte.
  • El enfoque principal se centra en la computación de alto rendimiento que aprovecha la capacidad de procesamiento de múltiples computadoras en paralelo.
Algoritmos distribuidos
  • El grafo G representa la estructura de la red informática. Existe un ordenador por cada nodo de G y un enlace de comunicación por cada arista de G. Inicialmente, cada ordenador solo 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 generar su propio color como salida.
  • El enfoque principal está en coordinar el funcionamiento de un sistema distribuido arbitrario. [ 63 ]

Si bien el campo de los algoritmos paralelos tiene un enfoque diferente al de los algoritmos distribuidos, existe mucha interacción entre ambos. Por ejemplo, el algoritmo de Cole-Vishkin para la coloración de grafos [ 64 ] 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 (usando memoria compartida) como en un sistema distribuido (usando paso de mensajes). [ 65 ] La frontera 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 la frontera 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 el número de ordenadores. De hecho, a menudo existe una relación de compromiso entre el tiempo de ejecución y el número de ordenadores: el problema se puede resolver más rápido si hay más ordenadores ejecutándose en paralelo (véase 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 pertenece a la clase NC . [ 66 ] La clase NC se puede definir igualmente bien utilizando el formalismo PRAM o circuitos booleanos: las máquinas PRAM pueden simular circuitos booleanos de forma eficiente y viceversa. [ 67 ]

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 síncrono donde todos los nodos operan de 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 síncronas necesarias para completar la tarea. [ 68 ]

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 D rondas de comunicación: simplemente se recopila 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 pueden resolver dichos algoritmos es una de las preguntas centrales de la investigación en el campo. [ 69 ] 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 ). [ 70 ] 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.

Otros problemas

Los problemas computacionales tradicionales parten de la premisa de que el usuario formula una pregunta, un ordenador (o un sistema distribuido) la procesa, genera una respuesta y finaliza su ejecución. Sin embargo, también existen problemas en los que se requiere que el sistema no se detenga, como el problema de los filósofos comensales y otros problemas similares de exclusión mutua . En estos problemas, se espera que el sistema distribuido coordine continuamente el uso de los recursos compartidos para evitar conflictos o bloqueos .

También existen desafíos fundamentales propios de la computación distribuida, por ejemplo, los relacionados con la tolerancia a fallos . Algunos ejemplos de problemas relacionados incluyen problemas de consenso , [ 71 ] tolerancia a fallos bizantinos [ 72 ] y autoestabilización . [ 73 ]

Gran parte de la investigación también se centra en comprender la naturaleza asíncrona de los sistemas distribuidos:

Tenga en cuenta que en los sistemas distribuidos, la latencia debe medirse mediante el "percentil 99" porque la "mediana" y el "promedio" pueden resultar engañosos. [ 77 ]

Elección

La elección del coordinador (o líder ) es el proceso de designar un único proceso como organizador de una tarea distribuida entre varios ordenadores (nodos). Antes de que comience la tarea, todos los nodos de la red desconocen qué nodo actuará como coordinador (o líder) de la misma, o bien no pueden comunicarse con el coordinador actual. Sin embargo, tras ejecutar un algoritmo de elección de coordinador, cada nodo de la red reconoce un nodo específico y único como coordinador de la tarea. [ 78 ]

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 les permita romper 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. [ 78 ]

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. [ 79 ]

Los algoritmos de elección de coordinador están diseñados para ser económicos en términos de bytes transmitidos y tiempo. El algoritmo propuesto por Gallager, Humblet y Spira [ 80 ] para grafos no dirigidos generales ha tenido un gran 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 propusieron 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 propusieron un método general que desacopla la cuestión de la familia de grafos del diseño del algoritmo de elección del coordinador. [ 81 ]

Para llevar a cabo la coordinación, los sistemas distribuidos emplean el concepto de coordinadores. El problema de la elección del coordinador consiste en seleccionar 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 para la elección del coordinador central. [ 82 ]

Propiedades de los sistemas distribuidos

Hasta ahora, el enfoque se ha centrado en diseñar un sistema distribuido que resuelva un problema dado. Un problema de investigación complementario es el estudio de las propiedades de un sistema distribuido dado. [ 83 ] [ 84 ]

El problema de la parada es un ejemplo análogo del campo de la computación centralizada: se nos da un programa informático y la tarea consiste en decidir si se detiene o se ejecuta indefinidamente. El problema de la parada 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 un solo ordenador. [ 85 ]

Sin embargo, existen 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 interactuantes (asíncronas y no deterministas) puede llegar a un punto muerto. Este problema es PSPACE-completo , [ 86 ] es decir, es decidible, pero es poco probable que exista un algoritmo eficiente (centralizado, paralelo o distribuido) que lo resuelva en el caso de redes grandes.

Otros temas

Linealizabilidad

Véase también

Notas

  1. 1 2 Tanenbaum, Andrew S.; Steen, Maarten van (2002). Sistemas distribuidos: principios y paradigmas . Upper Saddle River, NJ: Pearson Prentice Hall. ISBN 0-13-088893-1Archivado del original el 12 de agosto de 2020. Consultado el 28 de agosto de 2020 .
  2. ↑ «Programas distribuidos». Textos en Ciencias de la Computación . Londres: Springer London. 2010. págs. 373–406 . doi : 10.1007/978-1-84882-745-5_11 . ISBN  978-1-84882-744-8ISSN 1868-0941 . Los sistemas constan de varios componentes distribuidos físicamente que funcionan de forma independiente utilizando su almacenamiento privado, pero que también se comunican periódicamente mediante el paso explícito de mensajes. Dichos sistemas se denominan sistemas distribuidos. 
  3. ↑ Dusseau y Dusseau 2016 , págs. 1-2.
  4. ↑ Ford, Neal (3 de marzo de 2020). Fundamentos de la arquitectura de software: un enfoque de ingeniería (1.ª ed.). O'Reilly Media. págs. 146–147 . ISBN   978-1-4920-4345-4.
  5. ↑ De monolito a microservicios: Patrones evolutivos para transformar su monolito . O'Reilly Media. ISBN 978-1-4920-4781-0.
  6. ↑ Creación de aplicaciones sin servidor en Knative . O'Reilly Media. ISBN 978-1-0981-4204-9.
  7. ↑ «Programas distribuidos». Textos en Ciencias de la Computación . Londres: Springer London. 2010. págs. 373–406 . doi : 10.1007/978-1-84882-745-5_11 . ISBN  978-1-84882-744-8ISSN 1868-0941 . Los programas distribuidos son descripciones abstractas de sistemas distribuidos. Un programa distribuido consiste en un conjunto de procesos que trabajan concurrentemente 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. 
  8. ↑ Andrews (2000) . Dolev (2000) . Ghosh (2007) , p. 10.
  9. ↑ Magnoni, L. (2015). "Mensajería moderna para sistemas distribuidos (sic)" . Journal of Physics: Conference Series . 608 (1) 012038. Bibcode : 2015JPhCS.608a2038M . doi : 10.1088/1742-6596/608/1/012038 . ISSN 1742-6596 . 
  10. ↑ Godfrey (2002) .
  11. 1 2 Andrews (2000) , pág. 291–292. Dolev (2000) , pág. 5.
  12. ↑ Lynch (1996) , pág. 1.
  13. 1 2 Ghosh (2007) , pág. 10.
  14. ↑ Andrews (2000) , págs. 8–9, 291. Dolev (2000) , pág. 5. Ghosh (2007) , pág. 3. Lynch (1996) , pág. xix, 1. Peleg (2000) , pág. xv.
  15. ↑ Andrews (2000) , pág. 291. Ghosh (2007) , pág. 3. Peleg (2000) , pág. 4.
  16. ↑ Ghosh (2007) , pág. 3–4. Peleg (2000) , pág. 1.
  17. ↑ Ghosh (2007) , pág. 4. Peleg (2000) , pág. 2.
  18. ↑ Ghosh (2007) , pág. 4, 8. Lynch (1996) , pág. 2–3. Peleg (2000) , pág. 4.
  19. ↑ Lynch (1996) , pág. 2. Peleg (2000) , pág. 1.
  20. ↑ Ghosh (2007) , pág. 7. Lynch (1996) , pág. xix, 2. Peleg (2000) , pág. 4.
  21. ↑ Fundamentos de la arquitectura de software: Un enfoque de ingeniería . O'Reilly Media. 2020. ISBN 978-1-4920-4345-4.
  22. 1 2 3 4 Kleppmann, Martin (2017). Diseño de aplicaciones con gran cantidad de datos: Las grandes ideas detrás de sistemas fiables, escalables y mantenibles . O'Reilly Media. ISBN 978-1-4493-7332-0.
  23. 1 2 3 4 Creación de microservicios basados ​​en eventos: aprovechamiento de los datos organizacionales a gran escala . ISBN 978-1-4920-5789-5.
  24. ↑ Ghosh (2007) , pág. 10. Keidar (2008) .
  25. ↑ Lynch (1996) , pág. xix, 1–2. Peleg (2000) , pág. 1.
  26. ↑ Peleg (2000) , pág. 1.
  27. ↑ Papadimitriou (1994) , Capítulo 15. Keidar (2008) .
  28. ↑ Véanse las referencias en la Introducción .
  29. ↑ Bentaleb, A.; Yifan, L.; Xin, J.; et al. (2016). "Algoritmos paralelos y distribuidos" (PDF) . Universidad Nacional de Singapur. Archivado (PDF) del original el 26 de marzo de 2017. Recuperado el 20 de julio de 2018 . 
  30. ↑ Andrews (2000) , pág. 348.
  31. ↑ Andrews (2000) , pág. 32.
  32. ↑ Peter (2004) , La historia del correo electrónico Archivado el 15 de abril de 2009 en Wayback Machine .
  33. ↑ Banks, M. (2012). En el camino a la web: La historia secreta de Internet y sus fundadores . Apress. pp. 44–5 . ISBN  978-1-4302-5074-6Archivado del original el 20 de enero de 2023. Consultado el 20 de julio de 2018 .
  34. ↑ Tel, G. (2000). Introducción a los algoritmos distribuidos . Cambridge University Press. págs. 35–36 . ISBN  978-0-521-79483-1Archivado del original el 20 de enero de 2023. Consultado el 20 de julio de 2018 .
  35. ↑ Ohlídal, M.; Jaroš, J.; Schwarz, J.; et al. (2006). «Diseño evolutivo de esquemas de comunicación OAB y AAB para redes de interconexión». En Rothlauf, F.; Branke, J.; Cagnoni, S. (eds.). Aplicaciones de la computación evolutiva . Springer Science & Business Media. pp. 267–278 . ISBN   978-3-540-33237-4.
  36. ↑ "Sistemas de computación en tiempo real y distribuidos" (PDF) . ISSN 2278-0661 . Archivado del original (PDF) el 10 de enero de 2017. Consultado el 9 de enero de 2017 . {{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  37. ↑ Vigna P, Casey MJ. La era de las criptomonedas: cómo Bitcoin y la cadena de bloques desafían el orden económico mundial. St. Martin's Press, 27 de enero de 2015. ISBN 9781250065636
  38. ↑ Quang Hieu Vu; Mihai Lupu; Beng Chin Ooi (2010). Computación peer-to-peer: principios y aplicaciones . Heidelberg: Springer. pág. 16. ISBN  978-3-642-03513-5OCLC 663093862​​ 
  39. ↑ Lind P, Alm M (2006), "Un sistema de química virtual centrado en bases de datos", J Chem Inf Model , 46 (3): 1034– 9, doi : 10.1021/ci050360b , PMID 16711722 . 
  40. ↑ Chiu, G (1990). "Un modelo para la asignación óptima de bases de datos en sistemas de computación distribuida". Actas. IEEE INFOCOM'90: Novena Conferencia Anual Conjunta de las Sociedades de Computación y Comunicaciones del IEEE .
  41. ↑ Newman, Sam (2015-02-20). Building Microservices . O'Reilly Media. ISBN 978-1-4919-5035-7.
  42. ↑ Richardson, Chris (2019). Patrones de microservicios: con ejemplos en Java . Shelter Island, NY: Manning Publications. ISBN 978-1-61729-454-9.
  43. ↑ Christudas, Binildas (2019). Patrones arquitectónicos prácticos de microservicios: Microservicios Java basados ​​en eventos con Spring Boot y Spring Cloud . Berkeley, CA: Apress LP ISBN 978-1-4842-4501-9.
  44. ↑ Newman, Sam (2015-02-20). Building Microservices . O'Reilly Media. ISBN 978-1-4919-5035-7.
  45. ↑ Richardson, Chris (2019). Patrones de microservicios: con ejemplos en Java . Shelter Island, NY: Manning Publications. ISBN 978-1-61729-454-9.
  46. ↑ Christudas, Binildas (2019). Patrones arquitectónicos prácticos de microservicios: Microservicios Java basados ​​en eventos con Spring Boot y Spring Cloud . Berkeley, CA: Apress LP ISBN 978-1-4842-4501-9.
  47. ↑ Newman, Sam (2015-02-20). Building Microservices . O'Reilly Media. ISBN 978-1-4919-5035-7.
  48. ↑ Richardson, Chris (2019). Patrones de microservicios: con ejemplos en Java . Shelter Island, NY: Manning Publications. ISBN 978-1-61729-454-9.
  49. ↑ Christudas, Binildas (2019). Patrones arquitectónicos prácticos de microservicios: Microservicios Java basados ​​en eventos con Spring Boot y Spring Cloud . Berkeley, CA: Apress LP ISBN 978-1-4842-4501-9.
  50. ↑ Newman, Sam (2015-02-20). Building Microservices . O'Reilly Media. ISBN 978-1-4919-5035-7.
  51. ↑ Richardson, Chris (2019). Patrones de microservicios: con ejemplos en Java . Shelter Island, NY: Manning Publications. ISBN 978-1-61729-454-9.
  52. ↑ Christudas, Binildas (2019). Patrones arquitectónicos prácticos de microservicios: Microservicios Java basados ​​en eventos con Spring Boot y Spring Cloud . Berkeley, CA: Apress LP ISBN 978-1-4842-4501-9.
  53. ^ Elmasri y Navathe (2000) , Sección 24.1.2.
  54. ^ Andrews (2000) , pág. 10–11. Ghosh (2007) , pág. 4–6. Lynch (1996) , pág. xix, 1. Peleg (2000) , pág. xv. Elmasri y Navathe (2000) , Sección 24.
  55. ↑ Haussmann, J. (2019). "Procesamiento paralelo rentable de problemas con estructura irregular en entornos de computación en la nube". Journal of Cluster Computing . 22 (3): 887– 909. doi : 10.1007/s10586-018-2879-3 . S2CID 54447518 . 
  56. ↑ Desarrollo de aplicaciones reactivas . Manning. 2018. ISBN 978-1-63835-581-6.
  57. ↑ Toomarian, NB; Barhen, J.; Gulati, S. (1992). "Redes neuronales para aplicaciones robóticas en tiempo real" . En Fijany, A.; Bejczy, A. (eds.). Sistemas de computación paralela para robótica: algoritmos y arquitecturas . World Scientific. pág. 214. ISBN  978-981-4506-17-5Archivado del original el 1 de agosto de 2020. Consultado el 20 de julio de 2018 .
  58. ↑ Savage, JE (1998). Models of Computation: Exploring the Power of Computing . Addison Wesley. p. 209. ISBN  978-0-201-89539-1.
  59. ↑ Cormen, Leiserson & Rivest (1990) , Sección 30.
  60. ↑ Herlihy y Shavit (2008) , capítulos 2–6.
  61. ↑ Lynch (1996)
  62. ↑ Cormen, Leiserson & Rivest (1990) , Secciones 28 y 29.
  63. 1 2 3 TULSIRAMJI GAIKWAD-PATIL Facultad de Ingeniería y Tecnología, Nagpur Departamento de Tecnología de la Información Introducción a los Sistemas Distribuidos
  64. ↑ Cole y Vishkin (1986) . Cormen, Leiserson y Rivest (1990) , Sección 30.5.
  65. ↑ Andrews (2000) , pág. ix.
  66. ↑ Arora y Barak (2009) , sección 6.7. Papadimitriou (1994) , Sección 15.3.
  67. ↑ Papadimitriou (1994) , Sección 15.2.
  68. ↑ Lynch (1996) , págs. 17-23.
  69. ↑ Peleg (2000) , Secciones 2.3 y 7. Linial (1992) . Naor y Stockmeyer (1995) .
  70. ↑ Schneider, J.; Wattenhofer, R. (2011). "Comercializando la complejidad temporal, de mensajes y de bits de los algoritmos distribuidos" . En Peleg, D. (ed.). Computación distribuida . Springer Science & Business Media. pp. 51–65 . ISBN  978-3-642-24099-7Archivado del original el 1 de agosto de 2020. Consultado el 20 de julio de 2018 .
  71. ↑ Lynch (1996) , Secciones 5–7. Ghosh (2007) , Capítulo 13.
  72. ↑ Lynch (1996) , págs. 99–102. Ghosh (2007) , págs. 192–193.
  73. ↑ Dolev (2000) . Ghosh (2007) , Capítulo 17.
  74. ↑ Lynch (1996) , Sección 16. Peleg (2000) , Sección 6.
  75. ↑ Lynch (1996) , Sección 18. Ghosh (2007) , Secciones 6.2–6.3.
  76. ↑ Ghosh (2007) , Sección 6.4.
  77. ↑ Kamburugamuve, Supun; Ekanayake, Saliya (2021). Fundamentos de aplicaciones intensivas en datos: Análisis de datos a gran escala: El funcionamiento interno . John Wiley & Sons. ISBN 978-1-119-71301-2.
  78. 1 2 Haloi, S. (2015). Apache ZooKeeper Essentials . Packt Publishing Ltd. pp. 100–101 . ISBN  978-1-78439-832-3Archivado del original el 20 de enero de 2023. Consultado el 20 de julio de 2018 .
  79. ↑ LeLann, G. (1977). "Sistemas distribuidos: hacia un enfoque formal". Procesamiento de la información . 77 : 155·160 – vía Elsevier.
  80. ↑ RG Gallager , PA Humblet y PM Spira (enero de 1983). «Un algoritmo distribuido para árboles de expansión de peso mínimo» ( PDF) . ACM Transactions on Programming Languages ​​and Systems . 5 (1): 66–77 . doi : 10.1145/357195.357200 . S2CID 2758285. Archivado (PDF) del original el 26 de septiembre de 2017. {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
  81. ↑ Korach, Ephraim; Kutten, Shay ; Moran, Shlomo (1990). "Una técnica modular para el diseño de algoritmos eficientes de búsqueda de líderes distribuidos" ( PDF) . ACM Transactions on Programming Languages ​​and Systems . 12 (1): 84–101 . CiteSeerX 10.1.1.139.7342 . doi : 10.1145/77606.77610 . S2CID 9175968. Archivado (PDF) del original el 18 de abril de 2007.  
  82. ↑ Hamilton, Howard. "Algoritmos distribuidos" . Archivado del original el 24 de noviembre de 2012. Consultado el 3 de marzo de 2013 .
  83. ↑ "¿Principales problemas sin resolver en sistemas distribuidos?" . cstheory.stackexchange.com . Archivado del original el 20 de enero de 2023 . Consultado el 16 de marzo de 2018 .
  84. ↑ "Cómo el big data y los sistemas distribuidos resuelven los problemas tradicionales de escalabilidad" . theserverside.com . Archivado del original el 17 de marzo de 2018. Consultado el 16 de marzo de 2018 .
  85. ↑ Svozil, K. (2011). «Indeterminismo y aleatoriedad a través de la física» . En Hector, Z. (ed.). Aleatoriedad a través de la computación: algunas respuestas, más preguntas . World Scientific. pp. 112–113 . ISBN  978-981-4462-63-1Archivado del original el 1 de agosto de 2020. Consultado el 20 de julio de 2018 .
  86. ↑ Papadimitriou (1994) , Sección 19.3.

Referencias

Libros
Artículos
  • Cole, Richard; Vishkin, Uzi (1986), "Lanzamiento de moneda determinista con aplicaciones a la clasificación óptima de listas paralelas", Information and Control , 70 (1): 32– 53, doi : 10.1016/S0019-9958(86)80023-7.
  • Keidar, Idit (2008), "Columna 32 sobre computación distribuida: resumen del año" , ACM SIGACT News , 39 (4): 53– 54, CiteSeerX 10.1.1.116.1285 , doi : 10.1145/1466390.1466402 , S2CID 7607391 , archivado del original el 16 de enero de 2014 , recuperado el 20 de agosto de 2009.  .
  • Linial, Nathan (1992), "Localidad en algoritmos de grafos distribuidos", SIAM Journal on Computing , 21 (1): 193–201 , CiteSeerX 10.1.1.471.6378 , doi : 10.1137/0221015 .
  • Naor, Moni ; Stockmeyer, Larry (1995), "¿Qué se puede calcular localmente?" (PDF) , SIAM Journal on Computing , 24 (6): 1259–1277 , CiteSeerX 10.1.1.29.669 , doi : 10.1137/S0097539793254571 , archivado (PDF) del original el 8 de enero de 2013 .
sitios web
  • Godfrey, Bill (2002). "Una introducción a la computación distribuida" . Archivado del original el 13 de mayo de 2021. Recuperado el 13 de mayo de 2021 .
  • Peter, Ian (2004). "Historia de Internet de Ian Peter" . Archivado del original el 20 de enero de 2010. Recuperado el 4 de agosto de 2009 .

Lecturas adicionales

Libros
  • Attiya, Hagit y Jennifer Welch (2004), Computación distribuida: fundamentos, simulaciones y temas avanzados , Wiley-InterscienceISBN 0-471-45324-2.
  • Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Introducción a la programación distribuida segura y confiable (2.  ed.), Springer, Bibcode : 2011itra.book.....C , ISBN 978-3-642-15259-7
  • Coulouris, George; et  al. (2011), Sistemas distribuidos: conceptos y diseño (5.ª edición) , Addison-WesleyISBN 0-132-14301-1.
  • Faber, Jim (1998), Java Distributed Computing , O'Reilly, archivado del original el 24 de agosto de 2010 , consultado el 29 de septiembre de 2010.Java Distributed Computing, de Jim Faber, 1998. Archivado el 24 de agosto de 2010 en Wayback Machine.
  • Garg, Vijay K. (2002), Elementos de computación distribuida , Wiley-IEEE PressISBN 0-471-03600-5.
  • Tel, Gerard (1994), Introducción a los algoritmos distribuidos , Cambridge University Press
  • Chandy, Mani ; et  al. (1988), Diseño de programas paralelos , Addison-WesleyISBN 0201058669
  • Dusseau, Remzi H.; Dusseau, Andrea (2016). Sistemas operativos: tres piezas fáciles, capítulo 48 Sistemas distribuidos (PDF) . Archivado del original (PDF) el 31 de agosto de 2021. Recuperado el 8 de octubre de 2021 .
Artículos
  • Keidar, Idit; Rajsbaum, Sergio, eds. (2000–2009), "Columna sobre computación distribuida" , ACM SIGACT News , archivado del original el 16 de enero de 2014 , recuperado el 16 de agosto de 2009..
  • Birrell, AD; Levin, R.; Schroeder, MD; Needham, RM (abril de 1982). "Grapevine: Un ejercicio de computación distribuida" ( PDF) . Communications of the ACM . 25 (4): 260– 274. doi : 10.1145/358468.358487 . S2CID 16066616. Archivado (PDF) del original el 30 de julio de 2016. 
Artículos de conferencia
  • Rodríguez, Carlos; Villagra, Marcos; Baran, Benjamin (2007). "Algoritmos de equipo asíncronos para la satisfacibilidad booleana". 2007 2nd Bio-Inspired Models of Network, Information and Computing Systems . pp. 66– 69. doi : 10.1109/BIMNICS.2007.4610083 . S2CID 15185219 .  
  • Logotipo de Wikimedia CommonsContenido multimedia relacionado con la computación distribuida en Wikimedia Commons.
Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Una computadora humana.ComputadoraComputadoras y dispositivos informáticos de diferentes épocas, de izquierda a derecha y de arriba a abajo: Computadora de tubo de vacío temprana ( ...Red de computadorasRed de computadorasUna red informática es un conjunto de computadoras que comparten recursos ubicados en nodos de red o provistos por ellos . Las computadoras utiliza...Paso de mensajesPaso de mensajesEn informática , el paso de mensajes es una técnica para invocar un comportamiento (es decir, ejecutar un programa ) en una computadora . El progra...Concurrencia (informática)Concurrencia (informática)En informática , la concurrencia es la capacidad de diferentes partes o unidades de un programa , algoritmo o problema de ejecutarse fuera de orden...Sincronización de relojSincronización de relojLa sincronización de relojes es un tema de la ciencia informática y la ingeniería que tiene como objetivo coordinar relojes que de otro modo serían...