Reto vinculado con el protocolo Chord

Trabajo individual, de carácter voluntario, que puede otorgar una nota de hasta 0,75 puntos, que se añadirían a la nota total de la asignatura sólo en caso de que ésta esté aprobada.

Plazo

Hasta el 31 de octubre.

Enunciado

Hace unos días te encontraste con un viejo conocido, Mr. Hype, y le hablaste del protocolo Chord, entregándole una copia de un artículo que lo describía. Días después, os reencontrasteis y te contó que había estudiado en detalle el protocolo y había detectado ciertas deficiencias en el mismo que pretendía solventar planteando públicamente una nueva versión del protocolo.

Te explicó que el déficit que había identificado en el protocolo es su falta de uniformidad a la hora de localizar recursos, puesto que en Chord el tiempo que se tarda en encontrar un recurso es generalmente mayor cuanto más lejos en el anillo se encuentran el nodo que realiza la búsqueda y el recurso a localizar. Dicho de otra forma, argumentó que un nodo tiene más información en sus tablas sobre nodos más cercanos que sobre aquéllos que están más lejanos.

Finalmente, con gran entusiasmo, te explicó su idea:

Según Mr. Hype, aunque este algoritmo tiene una eficiencia ligeramente peor en algunos casos, presenta un comportamiento más uniforme, no penalizándose las búsquedas que están más alejadas (por ejemplo, a distancias mayores de 180 grados), como ocurría en el algoritmo original.

a) Después de pensarlo un rato, le explicas a ese viejo conocido que su nueva propuesta no tiene ningún sentido y que su eficiencia es muy deficiente. ¿Te acuerdas cómo le argumentaste que su propuesta era descabellada? Una pista: Como sé que tienes mala memoria, te recuerdo que le mostraste cuál es el peor caso en el tiempo de búsqueda desde la posición 0 en un sistema con m bits para las dos versiones del protocolo, especificando cuál es la posición más costosa de localizar y cuántos saltos, como máximo, se requieren para alcanzarla (suponiendo la hipotética, e irreal, situación en la que todas las posiciones del anillo estén llenas).

ProtocoloPosición en el anilloNúmero de saltos
Chord--
Hype--
Tabla comparativa para m bits

Para dejárselo más claro, le mostraste la tabla para m igual a 64 bits.

ProtocoloPosición en el anilloNúmero de saltos
Chord--
Hype--
Tabla comparativa para 64 bits

Un poco picado, para mostrar a ese conocido tu maestría sobre Chord, te planteas desarrollar una fórmula que, dada una posición desde donde se inicia la búsqueda y una posición a buscar, determina cuántos saltos, como máximo, se requieren.

Vamos a empezar completando la siguiente tabla que corresponde a la posición 0 en un sistema con m bits y tal que la fila i muestra qué nodos, y cuántos, están a i saltos del nodo 0. Especifica la posición de cada nodo en binario, ya que eso nos va a ayudar a descubrir la fórmula (por ahora no es necesario rellenar los puntos suspensivos).

Distancia en saltosCuántos nodosQué nodos
1--
2--
.........
máxima--
Tabla de distancias

b) Revisando la tabla y fijándose en los valores binarios, intente desarrollar una fórmula para calcular cuántos saltos son necesarios, como máximo, para localizar una posición P desde la posición 0.

c) Si has conseguido desarrollar la fórmula, enhorabuena. ¿Serías capaz de generalizarla para que permita calcular cuántos saltos son necesarios, como máximo, para localizar una posición Q desde una P?

Entrega

La entrega de este trabajo se debe realizar en triqui. Para ello, se debe crear, en primer lugar, la siguiente jerarquía de directorios en el HOME de la cuenta de triqui:
        mkdir -p DATSI/SD/RETO2.2014a
En ese directorio debe incluir un fichero denominado memoria.pdf.

A continuación, debe entregar el trabajo ejecutando:

        entrega.sd reto2.2014a