Computación Distribuida

           La computación distribuida es un campo de la informática que estudia los sistemas distribuidos. Un sistema distribuido es un sistema de software en el que los componentes ubicados en equipos en red se comunican y coordinan sus acciones mediante paso de mensajes. Los componentes interactúan entre sí con el fin de lograr un objetivo común. Hay muchas alternativas para el mecanismo de paso de mensajes, incluyendo conectores RPC similares y colas de mensajes. Tres características importantes de los sistemas distribuidos son: la simultaneidad de los componentes, la falta de un reloj mundial, y el fracaso independiente de los componentes. Un objetivo importante y el desafío de los sistemas distribuidos es la transparencia ubicación. Ejemplos de sistemas distribuidos varían desde sistemas basados en SOA para juegos multijugador masivos en línea para aplicaciones de igual a igual.

        Un programa de ordenador que se ejecuta en un sistema distribuido se llama un programa distribuido, y la programación distribuida es el proceso de escribir dichos programas.

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

            La palabra distribuye en términos como "sistema distribuido", "programación distribuida", y "algoritmo distribuido" se refería originalmente a una red informática donde los ordenadores individuales se distribuyen físicamente dentro de un área geográfica. Los términos se utilizan hoy en día en un sentido mucho más amplio, incluso refiriéndose a los procesos autónomos que se ejecutan en el mismo equipo físico e interactúan entre sí mediante paso de mensajes. Aunque no existe una definición única de un sistema distribuido, las propiedades que lo definen se utilizan comúnmente:

• Hay varias entidades computacionales autónomas, cada una de las cuales tiene su propia memoria local.

• Las entidades que se comunican entre sí mediante paso de mensajes.

En este artículo, las entidades computacionales se llaman ordenadores o nodos.

Un sistema distribuido puede tener un objetivo común, tales como la solución de un gran problema computacional. Alternativamente, cada equipo puede tener su propio usuario con las necesidades individuales, y el propósito del sistema distribuido es coordinar el uso de los recursos compartidos o proporcionar servicios de comunicación a los usuarios.

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

• El sistema tiene que tolerar fallas en equipos individuales.
• La estructura del sistema no se conoce de antemano, el sistema puede constar de diferentes tipos de equipos y vínculos de red, y el sistema puede cambiar durante la ejecución de un programa distribuido.
• Cada equipo tiene sólo una visión incompleta limitada del sistema. Cada equipo puede conocer sólo una parte de la entrada.

LA COMPUTACIÓN PARALELA Y DISTRIBUIDA

Los sistemas distribuidos son grupos de ordenadores conectados en red, que tienen el mismo objetivo de su trabajo. Los términos "computación concurrente", "La computación en paralelo" y "computación distribuida" tienen una gran cantidad de 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 ser visto como una forma fuertemente acoplado particular de computación distribuida, y la informática distribuida puede ser visto como una forma de acoplamiento flexible de la computación en paralelo. Sin embargo, es posible clasificar casi sistemas concurrentes como "paralelo" o "distribuido" utilizando los siguientes criterios:

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

Historia

El uso de procesos concurrentes que se comunican mediante paso de mensajes tiene sus raíces en las arquitecturas de sistemas operativos estudió en la década de 1960. Los primeros sistemas distribuidos generalizadas fueron las redes de área local como Ethernet que se inventaron en la década de 1970.

ARPANET, el predecesor de Internet, se introdujo a finales de 1960, y ARPANET e-mail fue inventado en la década de 1970. E-mail 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 sucesor, el Internet, otras redes informáticas primeros en todo el mundo incluido Usenet y FidoNet de 1980, ambos de los cuales se utiliza para apoyar los sistemas distribuidos de discusión.

El estudio de la computación distribuida se convirtió en su propia rama de la informática a finales de 1970 y principios de 1980. La primera conferencia en el campo, Simposio sobre los principios de la computación distribuida, se remonta a 1982, y de su homólogo europeo Simposio Internacional de Computación Distribuida se celebró por primera vez en 1985.

Aplicaciones

Hay dos razones principales para el uso de sistemas distribuidos y la computación distribuida. En primer lugar, la propia naturaleza de la aplicación puede requerir el uso de una red de comunicaciones que conecta varios ordenadores. Por ejemplo, los datos se produce en una ubicación física y que se necesita en otro lugar.

En segundo lugar, hay muchos casos en los que el uso de un único equipo sería posible en principio, pero el uso de un sistema distribuido es beneficioso por razones prácticas. Por ejemplo, puede ser más rentable para obtener el nivel deseado de rendimiento mediante el uso de un grupo de varios equipos de gama baja, en comparación con un solo equipo de gama alta. Un sistema distribuido puede ser más fiable que un sistema no distribuido, ya que no hay ningún punto único de fallo. Por otra parte, un sistema distribuido puede ser más fácil de ampliar y gestionar de un sistema de un procesador monolítico.

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

• Redes de telecomunicaciones:
  • Redes telefónicas y redes celulares.
  • Las redes de ordenadores como Internet.
  • Redes de sensores inalámbricos.
  • Los algoritmos de enrutamiento.
• Las aplicaciones de red:
  • World Wide Web y peer to peer.
  • Juegos multijugador masivos en línea y comunidades de realidad virtual.
  • Bases de datos y sistemas de gestión de bases de datos distribuidas distribuida.
  • Sistemas de archivos de red.
  • Sistemas de procesamiento de información distribuidos, como los sistemas bancarios y sistemas de reservas aéreas.
• Control de procesos en tiempo real:
  • Sistemas de control de aeronaves.
  • Sistemas de control industriales.
• Computación paralela:
• Computación científica, incluyendo la computación cluster y grid computing y varios proyectos de computación de voluntarios, ver la lista de proyectos de computación distribuida.
• Distributed rendering de gráficos por ordenador.

Fundamentos teóricos

MODELOS

Muchas de las tareas que nos gustaría para automatizar mediante el uso de una computadora son de tipo pregunta-respuesta: nos gustaría hacer una pregunta y el ordenador debe producir una respuesta. En ciencias de la computación teórica, estas tareas se denominan problemas de cálculo. Formalmente, un problema de cálculo consiste en casos junto con una solución para cada instancia. Las instancias son las preguntas que nos podemos preguntar, y las soluciones son las respuestas a estas preguntas se desee.

Ciencias de la computación teórica trata de comprender que los problemas informáticos se pueden resolver mediante el uso de una computadora y la eficiencia. Tradicionalmente, se dice que un problema puede ser resuelto mediante el uso de un ordenador si podemos diseñar un algoritmo que produce una solución correcta para cualquier caso dado. Dicho algoritmo puede ser implementado como un programa de ordenador que se ejecuta en un ordenador de propósito general: el programa lee un ejemplo de problema de entrada, realiza algún cálculo, y produce como salida la solución. Formalismos tales como máquinas de acceso aleatorio o máquinas de Turing universales se pueden utilizar como modelos abstractos de un ordenador de propósito general secuencial de la ejecución de un algoritmo tal.

El campo de concurrentes y distribuidos de computación estudios preguntas similares en el caso de cualquiera de varios equipos, o un equipo que ejecuta una red de procesos que interactúan: que los problemas informáticos se pueden resolver en este tipo de red y la eficiencia? Sin embargo, no está del todo claro lo que se entiende por "resolver un problema" en el caso de un sistema concurrente o distribuido: por ejemplo, ¿cuál es la tarea del diseñador de algoritmo, y lo que es el equivalente concurrente o distribuida de manera secuencial computadora de propósito general?

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

Tres puntos de vista son de uso común:

 Algoritmos paralelos en el modelo de memoria compartida

• Todas las computadoras tienen acceso a una memoria compartida. El diseñador algoritmo elige el programa ejecutado por cada equipo.
• Un modelo teórico es las máquinas de acceso aleatorio paralelas que se utilizan. Sin embargo, el modelo PRAM clásica asume acceso síncrono de la memoria compartida.
• Un modelo que se acerca más al comportamiento de los equipos con varios procesadores en el mundo real y que tenga en cuenta el uso de instrucciones de la máquina, tales como comparar y cambiar, es el de la memoria compartida asíncrona. Existe un amplio cuerpo de trabajo en este modelo, un resumen de lo que se puede encontrar en la literatura.

 Algoritmos paralelos en el modelo de paso de mensajes

• El diseñador algoritmo elige la estructura de la red, así como el programa ejecutado por cada equipo.
• Se utilizan modelos como circuitos booleanos y redes de clasificación. Un circuito booleano puede ser visto como una red de ordenadores: cada puerta es un ordenador que ejecuta un programa de ordenador extremadamente simple. Del mismo modo, una red de clasificación puede ser visto como una red de ordenadores: cada comparador es un ordenador.

 Algoritmos distribuidos en el modelo de paso de mensajes

• El diseñador algoritmo sólo elige el programa de ordenador. Todos los equipos ejecutan el mismo programa. El sistema debe funcionar correctamente, independientemente de la estructura de la red.
• El modelo utilizado es un gráfico con una máquina de estados finitos por nodo.

En el caso de los algoritmos distribuidos, problemas computacionales se relacionan generalmente con las gráficas. A menudo, la gráfica que describe la estructura de la red de ordenadores es la instancia de problema. Esto se ilustra en el siguiente ejemplo.

UN EJEMPLO

Considere el problema computacional de encontrar un color de un determinado gráfico G. diferentes campos puedan tener 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 de ordenador encuentra una coloración de la gráfica, codifica la coloración como una cadena, y envía el resultado.

 Algoritmos paralelos

• Una vez más, el grafo G se codifica como una cadena. Sin embargo, varios ordenadores pueden acceder a la misma cadena en paralelo. Cada equipo puede centrarse en una parte de la gráfica y producen una coloración para esa parte.
• La atención se centra en el cálculo de alto rendimiento que aprovecha la potencia de procesamiento de varios equipos en paralelo.

 Algoritmos distribuidos

• El gráfico G es la estructura de la red informática. Hay un ordenador para cada nodo de G y un enlace de comunicación para cada borde de G. Inicialmente, cada equipo sólo sabe acerca de sus vecinos inmediatos en el gráfico G; los equipos deben intercambiar mensajes entre sí para descubrir más acerca de la estructura de T . Cada equipo debe producir su propio color como salida.
• La atención se centra en la coordinación de la operación de un sistema distribuido arbitraria.

Mientras que el campo de los algoritmos paralelos tiene un enfoque diferente que el campo de los algoritmos distribuidos, hay una gran cantidad de interacción entre los dos campos. Por ejemplo, el algoritmo de Cole-Vishkin para la coloración de grafos se presentó originalmente como un algoritmo paralelo, pero la misma técnica también se puede utilizar directamente como un algoritmo distribuido.

Por otra parte, un algoritmo paralelo puede ser implementado ya sea en un sistema en paralelo o en un sistema distribuido. El límite tradicional entre algoritmos paralelos y distribuidos no reside en el mismo lugar que el límite entre los sistemas paralelos y distribuidos.

MEDIDAS COMPLEJIDAD

En los algoritmos paralelos, sin embargo, otro recurso además del tiempo y el espacio es el número de ordenadores. De hecho, a menudo existe un trade-off entre el tiempo de funcionamiento y el número de equipos: el problema se puede resolver más rápido si hay más equipos que ejecutan en paralelo. Si un problema de decisión puede ser resuelto en el tiempo polilogarítmico mediante el uso de un número polinómico de procesadores, entonces el problema se dice que es en la clase de Carolina del Norte. La clase NC puede ser definido igualmente bien mediante el uso de la PRAM formalismo o circuitos booleanos - máquinas PRAM pueden simular circuitos booleanos de manera eficiente y viceversa.

En el análisis de algoritmos distribuidos, más atención se paga generalmente en las operaciones de comunicación de pasos de cálculo. Tal vez el modelo más simple de computación distribuida es un sistema síncrono, donde todos los nodos funcionan de manera unísono. Durante cada ronda de comunicación, todos los nodos en paralelo reciben los últimos mensajes de sus vecinos, realizan cálculos locales de su elección, y enviar nuevos mensajes a sus vecinos. En tales sistemas, una medida de complejidad central es el número de rondas de comunicación sincrónica necesarios para completar la tarea.

Esta medida de complejidad está estrechamente relacionado con el diámetro de la red. Sea D el diámetro de la red. Por un lado, cualquier problema puede ser resuelto computables trivialmente en un sistema distribuido en las rondas de comunicación síncrona aproximadamente 2D: simplemente reunir toda la información en un solo lugar, resolver el problema, e informar a cada nodo sobre la solución.

Por otro lado, si el tiempo de ejecución del algoritmo es mucho menor que D rondas de comunicación, a continuación, los nodos de la red deben producir su salida sin tener la posibilidad de obtener información acerca de las partes distantes de la red. En otras palabras, los nodos deben tomar decisiones coherentes a nivel mundial sobre la base de la información que está disponible en su vecindad local. Muchos algoritmos distribuidos se conocen con el tiempo de funcionamiento mucho más pequeño que rondas D, y la comprensión que los problemas pueden resolverse por tales algoritmos es una de las preguntas de investigación centrales del campo.

Otras medidas comúnmente utilizados son el número total de bits transmitidos en la red.

OTROS PROBLEMAS

Problemas computacionales tradicionales toman la perspectiva de que hacemos una pregunta, una computadora procesa la pregunta por un tiempo, y luego se produce una respuesta y se detiene. Sin embargo, también hay problemas en los que no queremos que el sistema deje nunca. Ejemplos de tales problemas incluyen el problema filósofos comedor y otros problemas de exclusión mutua similares. En estos problemas, el sistema distribuido se supone que coordine continuamente el uso de los recursos compartidos de modo que no se producen conflictos o bloqueos.

También hay retos fundamentales que son únicos para la computación distribuida. El primer ejemplo es retos que están relacionados con la tolerancia a fallos. Ejemplos de problemas relacionados incluyen problemas de consenso, la tolerancia a fallos bizantinos, y auto-estabilización.

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

• Sincronizador pueden ser utilizadas para ejecutar algoritmos sincrónicos en sistemas asíncronos.
• Relojes lógicos proporcionan una causal pasado-antes de ordenar los acontecimientos.
• Algoritmos de sincronización de reloj proporcionan sellos globalmente consistentes tiempo físico.

PROPIEDADES DE LOS SISTEMAS DISTRIBUIDOS

Hasta ahora, la atención se ha centrado en el diseño de un sistema distribuido que resuelve un problema dado. Un problema de investigación complementaria está estudiando las propiedades de un sistema distribuido dado.

El problema de la parada es un ejemplo similar en el campo de la computación centralizada: se nos da un programa de ordenador y la tarea consiste en decidir si se detiene o se queda para siempre. El problema de la parada es indecidible en el caso general, y la comprensión de forma natural el comportamiento de una red de ordenadores es por lo menos tan fuerte como la comprensión del comportamiento de un ordenador.

Sin embargo, hay muchos decidible, pero no es probable que exista un algoritmo eficiente que resuelve el problema en el caso de redes de gran tamaño.

Elección Coordinador

Para llevar a cabo la coordinación, los sistemas distribuidos emplean el concepto de coordinadores. El problema coordinador de elección es elegir un proceso de entre un grupo de procesos en diferentes procesadores en un sistema distribuido para actuar como el coordinador central. Existen varios algoritmos electorales coordinador central.

ALGORITMO BULLY

Cuando se utiliza el algoritmo de Bully, cualquier proceso envía un mensaje a la actual coordinador. Si no hay respuesta dentro de un plazo determinado, el proceso trata de elegir como líder.

CHANG Y ROBERTS ALGORITMO

El algoritmo de Chang y Roberts es un algoritmo de elección basado en anillo usado para encontrar un proceso con el mayor número de identificación único.

Arquitecturas

Varios arquitecturas de hardware y software se utilizan para la computación distribuida. En un nivel inferior, es necesario interconectar varias CPU con algún tipo de red, independientemente de si la red que se imprime sobre una placa de circuito o compuestos de dispositivos y cables de acoplamiento flexible. En un nivel superior, es necesario interconectar los procesos que se ejecutan en las CPUs con algún tipo de sistema de comunicación.

Programación distribuida normalmente cae en una de las varias arquitecturas básicas o categorías: cliente-servidor, la arquitectura de 3 capas, una arquitectura n-tier, objetos distribuidos, acoplamiento débil o estrecho acoplamiento.

• Cliente-servidor: cliente inteligente de código contacta con el servidor de datos y formatea y lo muestra al usuario. Entrada en el cliente se compromete al servidor cuando representa un cambio permanente.
• Arquitectura de 3 capas: tres sistemas de nivel mover la inteligencia de cliente a un nivel medio para que los clientes apátridas pueden ser utilizados. Esto simplifica la implementación de aplicaciones. La mayoría de las aplicaciones web son de 3 niveles.
• arquitectura n-tier: n-tier se refiere por lo general a las aplicaciones web que más adelante sus solicitudes a otros servicios de la empresa. Este tipo de aplicación es el más responsable para el éxito de servidores de aplicaciones.
• altamente acoplado: se refiere típicamente a un grupo de máquinas que trabajan estrechamente juntos, se ejecuta un proceso compartido en paralelo. La tarea se divide en partes que se realizan de forma individual por cada uno de ellos y luego poner de nuevo juntos para que el resultado final.
• Intercambio de archivos: una arquitectura donde no hay máquina o máquinas que proporcionan un servicio o administrar los recursos de red especial. En cambio todas las responsabilidades se dividen de manera uniforme entre todas las máquinas, conocidas como pares. Los compañeros pueden servir a la vez como clientes y servidores.
• Espacio sede: se refiere a una infraestructura que crea la ilusión de un espacio de direcciones único. Los datos se replican de forma transparente de acuerdo con las necesidades de aplicación. Desacoplamiento en tiempo, espacio y referencia se logra.

Otro aspecto básico de la arquitectura de computación distribuida es el método de comunicación y la coordinación de trabajo entre los procesos concurrentes. A través de diversos protocolos de paso de mensajes, los procesos pueden comunicarse directamente entre sí, por lo general en una relación maestro/esclavo. Alternativamente, una arquitectura de "base de datos-centric" puede permitir a computación distribuida que hacer sin ningún tipo de comunicación directa entre procesos, mediante la utilización de una base de datos compartida.