¿Son reacciones en cadena pandemia confluentes? (vértice derrames de peso a los vecinos en el umbral, una vez)

Question

Son soluciones de la cadena de reacciones de orden independiente en el juego de mesa de la Pandemia? Más formalmente:

Estás dado un grafo no dirigido a $G = (V, E)$ y un vértice peso $w \colon V \to \{0, \ldots, 3\}$. Cada vértice se encuentra en un estado de $s \colon V \to \{\textsf{no outbreak}, \textsf{outbreak}\}$.

Para aumentar un vértice $v$:

• Si $s(v) = \textsf{outbreak}$ entonces no pasa nada.
• Otra cosa, si $w(v) < 3$$w(v) \gets w(v) + 1$.
• Otra cosa $s(v) \gets \textsf{outbreak}$ y aumentar todos los de $v$'s vecinos.

No se especifica que la orden de $v$'s vecinos, debería ser mayor. Es una especificación superfluo?

Observo que el establecimiento $s(v) \gets \textsf{outbreak}$ es esencialmente el mismo como la eliminación de $v$$G$. No sé cómo eso ayuda, aunque.

También, si entiendo lo de la confluencia de medios, creo que mi pregunta puede ser declaró: "es la siguiente reescritura del sistema confluentes?", donde cada elemento es una especificación de $w$ $s$ y un número de debido aumenta para cada vértice $v$, y cada uno de reescritura es un aumento de aproximadamente el $v$ (para el que un aumento es debido; también disminuye el número de aumentos debido para $v$).

Answer 1

Newman lema (véase también la Confluencia) establece que una reescritura del sistema es confluente si se está terminando y localmente confluentes. Voy a aplicar esto a mi pregunta.

Deje $w$ $s$ ser como en mi pregunta, y deje $q(v)$ el número de incrementos debido en $v$ ("cola").

El siguiente vuelve a escribir, a continuación, se permitirá por ningún $v$:

• $q(v) \gets q(v) - 1$ si $s(v) = \textsf{outbreak}$ $q(v) > 0$
• $w(v) \gets w(v) + 1$ $q(v) \gets q(v) - 1$ si $q(v) > 0$ $w(v) < 3$ $s(v) = \textsf{no outbreak}$
• $s(v) \gets \textsf{outbreak}$ $q(v) \gets q(v) - 1$ $\forall (v, u) \in E: q(u) \gets q(u) + 1$ si $q(v) > 0$ $w(v) = 3$ $s(v) = \textsf{no outbreak}$.

(Tenga en cuenta que al aplicar las reglas de la Pandemia, $s(v)$ es inicialmente $\textsf{no outbreak}$ $q(v)$ $0$ todos los $v$. No creo que esto es importante para la prueba.)

Para mostrar que esto se está terminando, considerar como una función de terminación de $t(s, w, s) = \left(\left|s^{-1}(\textsf{no outbreak})\right|, \Sigma_{\hspace{0.1em}v \in V} \hspace0.25em (3 - w(v)), \Sigma_{\hspace{0.1em}v \in V} \hspace 0.4em q(v)\right)$, es decir, un triple de 1. el número de verticies no en el brote de estado; 2. la capacidad en cada vértice para la absorción de aumentos sin romper; 3. el número de debido aumenta. (Los triples son ordenados lexicográficamente).

La primera regla reduce el tercer componente sin el aumento de cualquier otro. La segunda regla de baja el segundo componente sin el aumento de la primera. La tercera de las reglas disminuye el primero. Por lo tanto, la aplicación de cualquier regla conduce a una lexicográficamente menor valor de la triple a, y por lo tanto, la reescritura de proceso termina. (finalmente, la tercera no disminuya aún más, al punto que el segundo disminuye al menos una vez y la tercera toma cualquier valor; se repite, por lo tanto la segunda, eventualmente puede disminuir aún más, etc.).

A continuación, la confluencia, la definición de lo que es la "si $a \to b$ $a \to c$ $\exists \, d$ tal que $b \to^* d$$c \to^* d$", es decir, si puedo tomar el sistema de dos estados diferentes en un solo volver a escribir, no es un estado que se puede acceder desde cada una de las $b$ $c$ (con cero o más vuelve a escribir).

Tenga en cuenta que en mi sistema, el estado no permite la reescritura en $v$ con más de una regla-es decir, nunca hay dos condiciones de satisfacción al mismo tiempo; el solo paso de reescritura es determinista en cada vértice. Por lo tanto, si puedo volver a escribir a dos estados diferentes, debe ser por el aumento en dos diferentes vértices $v$$u$.

Voy a demostrar que $\textsf{increase(v) then increase(u)}$ lleva al mismo estado como $\textsf{increase(u) then increase(v)}$ todos los $u$$v$.

Tenga en cuenta que las dos primeras reglas de reescritura sólo la actualización de $q$ $w$ en el vértice, siendo mayor. Por lo tanto, si la tercera regla se aplica a los ni $u$ ni $v$ luego de la reescritura en $u$ $v$ lleva al mismo estado, no importa el orden de las reescrituras. (Programadores: cuenta de la similitud con la (ausencia de) carreras de datos.)

Para asumir la tercera regla se aplica a $v$.

Si la tercera regla no se aplica a $u$ $u$ no es un vecino de $v$, una vez más, no la superposición de piezas de $(q, w, s)$ están siendo reescritos, y se puede hacer pedido de forma independiente.

Si la tercera regla no se aplica a $u$ $u$ es un vecino de $v$, $q(u)$ se incrementa en 1 (regla de 1 a $v$) y la disminución de la 1 (la regla 1 o 2 en $u$), que claramente desplazamientos; cualquier otro reescribe son que no se superponen.

Así que el último caso: la regla 3 se aplica tanto a $u$$v$.

Si no son los vecinos y no tienen compartido vecinos, una vez más, no la superposición de piezas de $q$, $w$ y $s$ son reescritos, que conmutan.

Si no son los vecinos, pero han mutuo vecinos, $x_i$ algunos $i$, entonces cada una de las $q(x_i)$ es dos veces mayor en 1; estas dos operaciones claramente viaje.

Si $u$ $v$ son vecinos y también han mutuo vecinos:

• $q(u)$ $q(v)$ son tanto el aumento y la disminución, la que viajes.
• $q(x_i)$ es el aumento de dos veces para cada vecino $x_i$, que los desplazamientos.
• todos los otros cambios que no se superponen.

Q. E. D.

Comentario: he visto que el $(\{0, \ldots, 3\}, \ge)$ $(\{\textsf{no outbreak}, \textsf{outbreak}\}, (x \mapsto \textsf{outbreak}))$ son semilattices. Un par de (número de aumento-por-1 operaciones, el número de disminución-por-1 operaciones) con pares de la suma como la combinación también forma un semilattice con un extraño pedido. En el lenguaje de CRDTs, estos son dos de incremento de sólo (limitado) de los contadores y un PN contador. Dado que Newman lema habla de combinaciones, creo que esto puede haber ayudado a evitar algunos de la complejidad. Trabajando en algunas de estructura de datos en un semilattice sugiere que es posible que desee buscar en la unión de los dos estados sucesores de $a$, pero no automáticamente probar esta $d$ a ser accesible a través de su conjunto de reglas de reescritura. Supongo que si hay una reescritura a partir de cada elemento para cada elemento superior de la prueba es trivial.

Answer 2

Esto puede ser discutido directamente, mediante la consideración de la DAG en $(V, E)$ que codifica todos los de la resultante de las actualizaciones (un borde dirigido a $(u, v)$ corresponde a un brote en $u$ que incrementa $w(v)$). El reclamo es que el orden de las actualizaciones siempre resultará en un DAG con el mismo grado en cada nodo (es decir, el mismo número de cubos agregar a cada ubicación).

Asumir por medio de la contradicción que dos órdenes diferentes resultados en dos de los Dag: $D_1 = (V, E_1)$ $D_2 = (V, E_2)$ donde $\deg^-_{D_1}(v) > \deg^-_{D_2}(v)$ (w.l.o.g) para algunos $v \in V$. Por lo tanto existe algún borde $e = (u, v)$ tal que $e \in E_1$ pero $e \not\in E_2$. Esto sólo puede suceder si el padre $u$ tenido un brote en $D_1$, pero no en $D_2$. Por lo tanto $\deg^-_{D_1}(u) > \deg^-_{D_2}(u)$. Este argumento se repite hasta que llegamos a la raíz del vértice de $D_1$ (ya que estamos recorriendo un camino en $D_1$). Pero el grado de la raíz vértice debe ser $0$ en ambos Dag, una contradicción. $\square$

Esto también podría ser convertido en una prueba inductiva a ser un poco más formal, pero tengo la sensación de que esto sería sólo de ocultar la intuición.

Answer 3

Creo que se puede demostrar

Sea alguna secuencia de procesamiento válida administrarse y ciudad $C$ la ciudad que va en brote como la ciudad $n$ en esta secuencia. Luego en cualquier otro proceso secuencia ciudad $C$ también pasará al brote en algún momento.

por inducción largo en $n$. Esto significa que cualquier dos secuencias poner las mismas ciudades en brote y por lo tanto aumentar otras ciudades por la misma cantidad.