Tesis doctoral de Xavier Messeguer Peypoch
Presentamos un metodo que nos permite diseñar algoritmos distribuidos (asincronos) y masivamente paralelos (sincronos) sobre estructuras equilibradas, concretamente sobre las listas encadenadas «skip lists» y los arboles equilibrados de busqueda. Dicho metodo se basa en el conjunto de reglas locales que manipulan las estructuras, entendiendo por regla local cualquier algoritmo con un numero fijo de instrucciones (sin bucles) que acceden a un numero fijo de nodos vecinos. El metodo sugiere, en primer lugar, abordar el diseño del algoritmo distribuido en base a las reglas locales, y posteriormente abordar el diseño del algoritmo masivamente paralelo a partir de sincronizar de forma eficiente las reglas locales. De hecho los algoritmos masivamente paralelos pueden ser considerados como versiones optimas del algoritmo distribuido. hemos aplicado el metodo sobre las listas «skip lists» y sobre los arboles 2-3 y los arboles avl. Las listas han sido elegidas como representante de las estructuras equilibradas de forma aleatoria, y los arboles por estar manipulados por reglas locales muy diferentes y representar a una amplia gama de arboles equilibrados de busqueda tales como arboles 2-3-4, arboles b, arboles rojo-y-negros, etc. la aplicacion del metodo sobre las listas «skip lists» ha permitido el diseño del algoritmo masivamente paralelo y la creacion de una nueva estructura de arboles equilibrados denominada «skip trees» e isomorfa a las «skip lists». Los «skip trees» se equilibran de forma aleatoria y permiten paginar la estructura de forma mas eficiente. la aplicacion del metodo sobre los arboles 2-3 ha permitido el diseño de un algoritmo distribuido que permite de forma transitoria nodos con mas de dos llaves. la aplicacion del metodo sobre los arboles avl ha sugerido el diseño de un algoritmo distribuido de granularidad mas fina que la de los existentes (concretamente hemos separado las propagaciones de las rotacione
Datos académicos de la tesis doctoral «Algoritmos distribuidos y masivamente paralelos con reglas locales sobre arboles equilibrados de busqueda.«
- Título de la tesis: Algoritmos distribuidos y masivamente paralelos con reglas locales sobre arboles equilibrados de busqueda.
- Autor: Xavier Messeguer Peypoch
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 01/01/1997
Dirección y tribunal
- Director de la tesis
- Joaquim Gabarró Vallés
- Tribunal
- Presidente del tribunal: José Luis Balcazar Navarro
- Fernando Hurtado (vocal)
- Luc Bouge (vocal)
- Ricardo Baeza-yates (vocal)