Preguntas teóricas en computación distribuida
El campo de la computación distribuida se ha quedado lamentablemente corto en el desarrollo de una sola teoría matemática para describir algoritmos distribuidos. Existen varios 'modelos' y marcos de cómputo distribuido que simplemente no son compatibles entre sí. La gran explosión de propiedades...
La década de 1980 dio lugar a los modelos PRAM y BSP de cómputo paralelo. Parece que el apogeo de ambos modelos fue a finales de los 80 y principios de los 90. ¿Estas áreas aún están activas en términos de investigación para algoritmos paralelos? ¿Existen modelos más nuevos y sofisticados para la...
Inspirado por esta pregunta , ¿cuáles son los principales problemas y las soluciones existentes que necesitan mejoras en el dominio de sistemas distribuidos (teóricos). ¿Algo como protocolos de membresía, consistencia de
Esta pregunta se migró de Cross Validated porque se puede responder en el intercambio teórico de pila de informática. Migrado hace 8 años . Tengo un problema bastante único que resolver y espero que alguien aquí pueda darme una idea de cómo abordarlo mejor. Problema:...
En la informática distribuida, el problema del consenso parece ser uno de los temas centrales que ha atraído una investigación intensiva. En particular, el artículo "Imposibilidad de consenso distribuido con un proceso defectuoso" recibió el Premio de papel influyente PODC 2001 . Entonces, ¿por...
Esta pregunta está inspirada en un comentario que Jukka Suomela hizo sobre otra pregunta . ¿Cuáles son ejemplos de problemas de cálculo (y algoritmos) infinitamente grandes pero localmente finitos? En otras palabras, ¿cuáles son ejemplos de cálculos que se detienen en un tiempo finito, en el...
En este artículo de Kempe-Kleinberg-Tardos, los Autores proponen algoritmos codiciosos basados en funciones submodulares para determinar los nodos más influyentes en un gráfico, con aplicaciones a las redes sociales.kkk Básicamente, el algoritmo es el siguiente: S= e m p t y s e...
Estoy leyendo el documento "Fast Paxos" de Leslie Lamport y me quedo atascado con las pruebas de corrección de Paxos clásico y Fast Paxos. Por consistencia, el valor recogió por el coordinador en fase en la ronda debería satisfacer2 a ivvv2a2a2aiii CP(v,i):CP(v,i):CP(v,i): para cualquier ronda...
La semana pasada, estaba leyendo de nuevo el trasncrito de Leslie en Lamport de 1982 de una conferencia que dio sobre Problemas resueltos, Problemas no resueltos y No problemas en concurrencia . El documento es fácilmente legible, pero una de las cosas que me hizo pensar es la siguiente...
Hay dos tipos principales de fallas del procesador en los modelos de computación distribuida: (1) Fallos de bloqueo: un procesador se detiene y nunca más se inicia. (2) Fallos bizantinos: los procesadores se comportan de manera adversa, maliciosa. Mi pregunta es: ¿Cuáles son algunos otros...
El problema del chisme en los sistemas distribuidos es el siguiente. Tenemos un gráfico con n vértices. Cada vértice v tiene un mensaje m v que debe enviarse a todos los nodos.GGGnnnvvvmvmvm_v Ahora, mi pregunta está en el contexto del modelo de red ad-hoc (suponemos que un nodo no tiene ningún...
En los sistemas de control de versiones distribuidas (como Mercurial y Git ) existe la necesidad de comparar eficientemente los gráficos acíclicos dirigidos (DAG). Soy un desarrollador de Mercurial, y estaríamos muy interesados en escuchar sobre el trabajo teórico que discute la complejidad del...
Soy un estudiante de maestría enfocado en sistemas distribuidos pero también interesado en informática teórica. Me preguntaba si hay una representación formal de un sistema distribuido encima de una máquina de turing. Es decir, ¿es posible extender (hacer una variante) el concepto de una máquina de...
Deje ser un gráfico conectado no regular cuyo grado está acotado. Supongamos que cada nodo contiene un token único.G = ( V, E)G=(V,E)G= (V, E) ¿Quiero barajar uniformemente los tokens entre el gráfico usando solo intercambios locales (es decir, el intercambio de tokens entre dos nodos adyacentes)?...
Definiciones Sea y sea que d , r y g sean enteros positivos (con g > 2 r + 1 ).ϵ>0ϵ>0\epsilon > 0dddrrrgggg>2r+1g>2r+1g > 2r+1 Sea un gráfico finito simple, d- regular, no dirigido, con circunferencia de al menos g .G=(V,E)G=(V,E)G = (V,E)dddggg Deje ser un orden total en V...
David Rodríguez - dribeas escribió en un comentario en StackOverflow que "No todas las colecciones se pueden implementar sin bloqueos". No estoy seguro de si esto es cierto, y no puedo encontrar pruebas de ninguna manera. Esta declaración no es muy precisa, pero permítanme tratar de reformularla...
Antecedentes: el procesamiento de transacciones ha sido un tema de investigación tradicional en la teoría de bases de datos. Hoy en día, las transacciones distribuidas se popularizan por los sistemas de almacenamiento distribuido a gran escala que generalmente implican la partición de datos...
Una transacción de base de datos clásica simplificada se puede ver como: leyendo artículos M realizar algunos cálculos basados en esas lecturas escribir algunos resultados de N basados en estos cálculos, que pueden incluir los elementos leídos originalmente. Al realizar estas transacciones...
¿Qué documentos sobre el manejo de errores en sistemas distribuidos me
Los algoritmos distribuidos que son resistentes a las fallas pueden ser deterministas o probabilísticos. Tomemos, por ejemplo, el problema del consenso. Paxos es determinista en el sentido de que, dada la suposición que hace, siempre funciona. En contraste, el consenso aleatorio funciona con una...