Saltar gráfico

El algoritmo de búsqueda para grafos de salto es casi idéntico al algoritmo de búsqueda para listas de salto, pero se modifica para ejecutarse en un sistema distribuido. Las búsquedas comienzan en el nivel superior y recorren la estructura. En cada nivel, la búsqueda recorre la lista hasta que el siguiente nodo contiene una clave mayor. Cuando se encuentra una clave mayor, la búsqueda pasa al siguiente nivel y continúa hasta que se encuentra la clave o se determina que no está contenida en el conjunto de nodos. Si la clave no está contenida en el conjunto de nodos, se devuelve el mayor valor menor que la clave de búsqueda.

Cada nodo de una lista tiene los siguientes campos:

key

El valor del nodo.

neighbor[R/L][level]

Un array que contiene punteros al vecino derecho e izquierdo en el nodo doblemente enlazado en el nivel i.

buscar(searchOp, startNode, searchKey, level) si (v.key = searchKey) entonces enviar (foundOp, v) a startNode si (v.key < searchKey) entonces mientras level ≥ 0 si (v.neighbor[R][level].key ≤ searchKey) entonces enviar (searchOp, startNode, searchKey, level) a v.neighbor[R][level] romper sino nivel = nivel - 1 De lo contrario, mientras nivel ≥ 0, si ((v.neighbor[L][nivel]).key ≥ searchKey) entonces envía (searchOp, startNode, searchKey, nivel) a v.neighbor[L][nivel] salir de lo contrario nivel = nivel - 1 Si (nivel < 0) entonces envía (notFoundOp, v) a startNode

El análisis realizado por William Pugh muestra que, en promedio, una lista de saltos y, por extensión, un gráfico de saltos contiene${\displaystyle O\left({\frac {\log n}{\log(1/p)}}\right)}$niveles para un valor fijo de p . ^{[ 3 ]} Dado que como máximo${\displaystyle {\frac {1}{1-p}}}$Los nodos se buscan en promedio por nivel, el número total esperado de mensajes enviados es${\displaystyle O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)}$y el tiempo previsto para la búsqueda es${\displaystyle O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)}$. ^{[ 2 ]} Por lo tanto, para un valor fijo de p , se espera que la operación de búsqueda tome O (log n ) tiempo usando O (log n ) mensajes. ^{[ 2 ]}

La inserción se realiza en dos fases y requiere que un nuevo nodo u conozca algún nodo introductor v ; el nodo introductor puede ser cualquier otro nodo actualmente en el grafo de salto. En la primera fase, el nuevo nodo u usa el nodo introductor v para buscar su propia clave; se espera que esta búsqueda falle y devuelva el nodo s con la clave más grande menor que u . En la segunda fase, u se inserta en cada nivel hasta que sea el único elemento en una lista en el nivel superior. ^{[ 2 ]} La inserción en cada nivel se realiza usando operaciones estándar de lista doblemente enlazada; el puntero siguiente del vecino izquierdo se cambia para que apunte al nuevo nodo y el puntero anterior del vecino derecho se cambia para que apunte al nodo.

insertar() buscar s L = 0 mientras sea verdadero Insertar u en el nivel L desde s. Recorrer el nivel L para encontrar s' tal que tenga un vector de pertenencia que coincida con el vector de pertenencia de u para los primeros L + 1 caracteres si no existe s'. salida de lo contrario s = s' L = L + 1

De forma similar a la búsqueda, la operación de inserción requiere O (log n ) mensajes y O (log n ) tiempo. Con un valor fijo de p, se espera que la operación de búsqueda en la fase 1 requiera O (log n ) tiempo y mensajes. En la fase 2, en cada nivel L ≥ 0, u se comunica con un promedio de 1/ p nodos para localizar s ', lo que requerirá O (1/ p ) tiempo y mensajes, resultando en O (1) tiempo y mensajes para cada paso en la fase 2. ^{[ 2 ]}

Los nodos pueden eliminarse en paralelo en cada nivel en un tiempo O (1) y O (log n ) mensajes. ^{[ 2 ]} Cuando un nodo desea abandonar el grafo, debe enviar mensajes a sus vecinos inmediatos para reorganizar sus punteros siguiente y anterior. ^{[ 2 ]}

delete() para L = 1 hasta el nivel máximo, en paralelo elimina u de cada nivel. Elimina u del nivel 0.

El grafo de salto contiene un promedio de O (log n ) niveles; en cada nivel, u debe enviar 2 mensajes para completar una operación de eliminación en una lista doblemente enlazada. Dado que las operaciones en cada nivel pueden realizarse en paralelo, la operación de eliminación puede finalizarse en un tiempo de O (1) y con un número esperado de O (log n ) mensajes.

Los grafos de salto son altamente resistentes a fallas aleatorias. Al mantener información sobre el estado de los vecinos y utilizar enlaces redundantes para evitar vecinos que fallen, las operaciones normales pueden continuar incluso con una gran cantidad de fallas de nodos. Mientras que el número de nodos que fallan es menor que${\displaystyle O\left({\frac {1}{\log n}}\right)}$El grafo de salto puede seguir funcionando con normalidad. ^{[ 2 ]} Las simulaciones realizadas por James Aspnes muestran que un grafo de salto con 131072 nodos pudo tolerar que hasta el 60% de sus nodos fallaran antes de que los nodos supervivientes fueran aislados. ^{[ 2 ]} Si bien otras estructuras de datos distribuidas pueden alcanzar niveles más altos de resiliencia, tienden a ser mucho más complejas.

Es difícil simular fallos adversarios en una red grande, ya que resulta difícil encontrar patrones de fallos en el peor de los casos. ^{[ 2 ]} El análisis teórico muestra que la resiliencia depende de la relación de expansión de vértices del grafo, definida de la siguiente manera. Para un conjunto de nodos A en el grafo G, el factor de expansión es el número de nodos que no están en A pero que son adyacentes a un nodo en A dividido por el número de nodos en A. Si los grafos de salto tienen una relación de expansión suficientemente grande de${\displaystyle \Omega \left({\frac {1}{\log n}}\right)}$entonces como máximo${\displaystyle O(f\log n)}$Los nodos pueden separarse, incluso si se buscan específicamente hasta f fallos. ^{[ 2 ]}