Cálculo de predicados distribuidos en flujo de eventos

Question

Mi pregunta es en realidad una solicitud de trabajos, artículos, textos o libros sobre el problema que intento resolver en mi trabajo.

Estoy trabajando en un programa que calcula un valor de predicado (verdadero o falso) para un objeto determinado en un sistema distribuido en el que hay una secuencia de eventos que pueden cambiar los atributos del objeto y, en consecuencia, el valor del predicado.Siempre que el valor del predicado cambie, el programa debe enviar una notificación sobre este cambio.

Por ejemplo, considere que hay un objeto A que tiene un atributo llamado name y considera que hay un predicado P lo cual es cierto cuando el objeto name es igual a Jhon.Cada evento de la secuencia tiene una marca de tiempo y un valor para el nombre del atributo.Consideremos entonces la siguiente secuencia de acontecimientos:

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 2 }
e3 = { name: Peter, timestamp: 3 }
e4 = { name: Doug, timestamp: 4 }
e5 = { name: Jhon, timestamp: 5 }

En este problema los eventos tienen una relación de orden total:Si tienes dos eventos siempre puedes decir cuál es el más antiguo de ellos.

Ahora, los eventos no necesariamente aparecen en la transmisión en el orden correcto según su marca de tiempo.Cada evento es único para su marca de tiempo, por lo que no hay dos o más eventos con la misma marca de tiempo para el mismo objeto.Además, las marcas de tiempo no necesariamente forman una secuencia que siempre aumenta en uno:si vemos e1 con marca de tiempo 1 y e3 con marca de tiempo 3, no implica la existencia de e2 con marca de tiempo 2.No hay garantía de que se reciban todos los eventos ni de cuándo se recibirán.Es parte del problema que solo conocemos la existencia de los eventos que vemos en la transmisión.

El escenario real es aún peor:Hay varias computadoras procesando paralelamente este flujo de eventos.Sin embargo, para simplificar, iré más allá en este ejemplo considerando sólo una computadora.

Si los eventos llegan y se procesan en el orden descrito anteriormente, entonces las notificaciones enviadas deberían ser:

P(A) = true when e1 arrives
P(A) = false when e3 arrives
P(A) = true when e5 arrives.

Esa es la secuencia correcta de notificaciones porque respeta el orden de la marca de tiempo.Ahora imagina que la computadora recibe los eventos en el siguiente orden:

e1, e5, e2, e4, e3

Un algoritmo ingenuo que no considere la marca de tiempo del evento enviaría una secuencia incorrecta de notificaciones:

P(A) = true when e1 arrives
P(A) = false when e4 arrives

El algoritmo en el que estoy trabajando considera las marcas de tiempo e infiere cuándo debería haberse enviado una notificación pero no se envió.Así que cuando e3 llega se dará cuenta que la notificación P(A) = true para e5 no fue enviado.Esto se siente un poco como reinventar la rueda, aunque no conozco ninguna lectura sobre este problema.Me gustaría algunas referencias a este problema o algo similar, como algunos artículos que traten este tipo de problema.

El verdadero problema es bastante más complejo ya que implica almacenar el predicado $\veces$ Estado del objeto en una base de datos que funciona como un estado compartido entre las computadoras que procesan la transmisión y estoy hablando de miles de eventos que llegan por segundo, por lo que no es posible mantener todos los eventos almacenados en alguna base de datos.

¿Existe alguna literatura sobre el problema que he descrito?Si es así, ¿podrías darme enlaces?

Me gustaría ver un artículo o un texto que explique un algoritmo que resuelva este problema y sería aún mejor si dicho artículo proporcionara pruebas sobre el algoritmo (p. ej.exactitud).

Si dicho documento no existe (de hecho, creo que ese es el caso), aceptaría una respuesta que describa un algoritmo y proporcione un argumento o una prueba sobre su exactitud.

Para que este algoritmo sea correcto, siempre debe enviar la secuencia correcta de notificaciones sin importar el orden en que lleguen los eventos.Y el algoritmo no debería mantener todos los eventos recibidos en la memoria, porque el verdadero problema tiene que ver con demasiados eventos para guardarlos en la memoria o almacenarlos en una base de datos.Sería razonable mantener algunos eventos en la memoria, preferiblemente una cantidad fija.

Answer 1

Resultado de imposibilidad n.° 1:eventos eliminados

El problema no puede resolverse en general;no hay forma de garantizar que se cumplan sus requisitos si algunos eventos se eliminan (es decir, no se reciben).Consideremos primero esta corriente:

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 4 }

donde el algoritmo ve ambos eventos.A continuación, considere esta corriente:

e1' = { name: Jhon, timestamp: 1 }
e2' = { name: Pete, timestamp: 2 }
e3' = { name: Jhon, timestamp: 3 }
e4' = { name: Jhon, timestamp: 4 }

donde el algoritmo ve sólo los eventos e1',e4' (los demás eventos se pierden y nunca se reciben).Podrías notar que lo que ve el algoritmo en ambos casos es idéntico, por lo que sus resultados serán idénticos en ambos casos.Sin embargo, la respuesta correcta difiere en estos dos casos, por lo que no hay esperanza de que un algoritmo produzca siempre un resultado correcto.(La respuesta correcta en el primer caso es no presentar notificaciones;la respuesta correcta en el segundo caso es producir dos notificaciones, una para indicar que el predicado es falso después de recibirlo e2', y otro para indicar que el predicado es verdadero después de recibir e3'.)

No está claro cómo adaptar los requisitos para hacer frente a esta situación.La única solución plausible que veo es decir que las notificaciones que se produzcan deberían depender sólo de los eventos recibidos, no de los eventos que se envían.Esto equivale a especificar que los eventos no se pueden descartar.

Resultado de imposibilidad n.° 2:eventos reordenados

Usted afirma que debe poder manejar eventos reordenados, sin almacenar todos los eventos en la memoria y con un reordenamiento arbitrario.Sin embargo, estos requisitos son incompatibles:eso es imposible de lograr.Considere una larga secuencia de eventos con marcas de tiempo 2,4,6,8,10,12,...Al final de la larga secuencia de eventos, si llega un evento con una marca de tiempo impar, la única manera de estar seguro de poder manejarlo correctamente es almacenar el historial completo de eventos pasados ​​(o estados pasados ​​del objeto).

Por lo tanto, también tendrá que relajar el requisito de volver a realizar pedidos.Quizás esté dispuesto a almacenar todos los eventos en la memoria para siempre.(Si es así, tiene una solución). Quizás esté dispuesto a imponer un límite al reordenamiento, por ejemplo, ningún evento se retrasará más de 10 minutos.(Si es así, sólo tiene que almacenar el historial de los últimos 10 minutos y todo lo anterior se puede eliminar). Quizás algo más tenga más sentido en su situación particular.

Pero lo único que no es una opción es imponer todos los requisitos estrictos establecidos en su pregunta y exigir un algoritmo que siempre sea correcto.

---

No conozco ninguna literatura sobre esto y no veo ninguna razón para esperar que la haya.Es un conjunto de requisitos muy específico y me parece que la tarea resultante es trivial o imposible de resolver.Por lo general, estos no son el tipo de problemas que tienden a estudiarse en la literatura.Quizás te pueda interesar estructuras de datos persistentes, pero esa es sólo una forma elegante de almacenar el historial completo de eventos, lo cual dijiste que querías hacer;y no necesita una estructura de datos sofisticada para hacerlo en su situación particular.