PDF de programación - Temas sobre informática teórica - Problemas de investigación en Internet - Clase 6

MIT 18.996: Temas sobre informática teórica: problemas de investigación en

Internet



primavera de 2002
Clase 6—13 de marzo de 2002

Profesor: Bobby Kleinberg ([email protected])



Copista: Lauren McCann

6.1 El modelo

Pensemos en un conjunto de elementos (objetos de una web cacheados), un grupo de

cachés (ej. servidores) y un conjunto de vistas distintas (ej. clientes de distintas partes

de la red).

Sea I = {elementos}donde | I | = N.

Sea C = {cachés} donde | C | = M.

Sea V = vistas donde | V | = V.

donde



Nota: N debería ser bastante grande, y a menudo demostraremos cosas sólo para un N

que sea grande.

Recuerde que la mayoría de los protocolos para ubicar objetos poseen las siguientes

características:

• Localidad

• Escalabilidad

• Balance de carga

Una función de hash en cadena (función de dispersión en cadena) (RHF) es un mapa

que toma una vista y un elemento, y lo asigna a un caché en el que usted puede

encontrar ese elemento.



Una familia de hash en cadena es un conjunto finito de funciones de hash en cadena.

MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



Una función de hash en cadena aleatoria es una muestra invariable tomada de ese

conjunto.

Propiedades de una “buena” RHF aleatoria en un entorno de caché distribuido:

1. Balance de carga (media por encima de todas las vistas)

2. Localidad (en nuestro modelo, la distancia no es una variable de la función, así

que la borramos)

3. Fluidez (la función no debería cambiar demasiado cuando las funciones no

cambian mucho)

4. Redundancia / Difusión

5. Cálculo eficiente

6. Representación eficaz

7. Invertibilidad (no necesariamente requerida)


6.1.1 Balance de carga

número de

para cualquier



En este caso debemos utilizar la variable b, ya que los estamos considerando como

cubos. Se trata del número de elementos que se asignarán a un determinado cubo.
6.1.2 Balance

El balance es distinto al balance de carga. Nos gustaría que cada vista fuese lo más

equilibrada posible, de manera que el adversario de una vista no pudiese fácilmente

sobrecargar una caché.

Con una alta probabilidad,

asigna a b la fracción

.

con una alta probabilidad, el número de



MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



6.1.3 Fluidez



La fluidez viene determinada por cuánto cambia una función de hash cuando la vista

cambia.



número de elementos que se asignan a diferentes valores de caché.

número de



6.1.4 Difusión

número de



Esto representa el número máximo de cachés con el que éste se corresponde.


6.2 Una RHF simple aleatoria

Se nos pide que propongamos una RHF simple aleatoria. Una sugerencia común podría

ser: ∀(V, i) selecciona al azar a b ∈ V.

¿Funciona?

¡NO! Ésta tiene malas propiedades de difusión.¿Y qué le parece otra opción obvia,

como la elección del operador mod para dividir el número de cachés de una vista? Esto

funciona perfectamente en el balance, pero no resulta muy fluido. Veámos un ejemplo

sencillo de mala difusión:

1 2 3 4 5 6 7 8 9



MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



a b c a b c a b c

a b a b a b a b a

X X X X X

En este caso hay un cambio esperado de 2/3, e incluso empeora con números más

largos. Probemos con otro ejemplo.

Seleccione una permutación ∀ i, πi: CC al azar, uniforme e independientemente.

1 2 3 4 5

1 5 2 4 1 3

2 3 1 5 4 2

3 1 5 3 2 4

4 4 2 1 3 5

Sea (V,i), asígnelo a b ∈ V minimizando



Esto equivale a escoger el primero de la lista (de la izquierda) que sea un miembro del

conjunto V.

Suponga que V= {2, 4, 5}

Luego elegiríamos 5, 5, 5, 4

Nota: el ejemplo que se dio en clase no se facilitó con un generador de número aleatorio

y no posee un tamaño de muestra suficiente para demostrar las buenas propiedades

reales de esta RHF aleatoria. De modo que, un resultado de tres 5 y un 4 no es lo que

debíamos esperar.

Lema: con probabilidad



Prueba: la función de hash posee una propensión obvia hacia el lado izquierdo de la

fila. Queremos probar que cada vista, V, interseca 1 de las primeras columnas σ del

cuadro con probabilidad alta.



MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



Lema: con probabilidad



Las vistas tienen un tamaño de

, de modo que cada cubo obtendría una carga de

.

Esto nos indica que el factor que excede al perfecto es logarítmico y es un término 0 (1).

Prueba: ponga



Con probabilidad

, alguna vista se ha separado de

para cualquier

.

Para cualquier cubo b y elemento i, la Pr[ b esté en las primeras columnas

de la fila

]



E [número de filas en las que esto se da]



Aplicamos la cota de Chernoff para obtener el enunciado “con alta probabilidad”



Nota: las cotas de Chernoff muestran que la suma no puede ser mucho mayor que la

expectativa.



MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



Disertación: si se compara con una función de hash que no esté en cadena, la

propagación y la carga serían peor sólo desde un punto de vista logarítmico.

Observación: (límite de fluidez). Con alta probabilidad
6.3 Una mejor RHF



∀i ∈ I selecciona un punto

al azar uniforme e independientemente.

∀b ∈C selecciona un conjunto de puntos k log m al azar uniforme e

independientemente.

Dado un elemento (V, i), hágalo corresponder con el primer cubo b ∈V que se encuentre

yendo en la dirección de las agujas del reloj, partiendo de



Nos hacen falta los puntos N + K m log m del círculo de la unidad donde K es una

constante.
6.4 Aplicaciones

Árboles aleatorios y dispersión coherente– Karger, L, L, L, L, P

I ∈ {elementos}, C = {cachés}

∀i ∈ I∃ un servidor de origen s (i)

Navegador: para i ∈ I, tome un árbol d binario equilibrado con nodos |V| . Haga

corresponder cada nodo del árbol con una caché, utilizando una función de hash fija y

coherente. Por fija entendemos que cada navegador utiliza el mismo árbol de hash

coherente.

Cuando solicite un objeto i, seleccione una hoja aleatoria de este árbol.

Facilite la ruta a la raíz y presente la petición al caché en esa hoja, indicando la ruta

completa.



MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



Caché: quédese con un contador ∀i ∈ I, que vaya aumentando en cada petición de i. Si i

está en la, entréguelo. De lo contrario, remita el objeto al sucesor y a la caché cuando el

contador llegue a q (un parámetro optimizable).

El servidor de origen entrega el objeto.


6.5 CHORD

Entre iguales: cada nodo únicamente conoce un factor logarítmico de la caché. Siga el

puntero que nos acerca más al punto. Pregunte allí por la clave o el modo de estar más

cerca de la clave.

Espere hasta que alguien tenga un enlace directo.

El número de saltos es algorítmico con el número de cachés.


6.6 El problema de asignación de difusión mínima

Suponga que tenemos n elementos y m cachés.

Los elementos tienen cargas

y las cachés poseen capacidad



Objetivo: encontrar la asignación con el menor número de aristas posibles.

Una asignación fraccional es una matriz,

que satisface:



propagación =



MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



Queremos minimizar la difusión.

Dato: El problema de asignación de difusión mínima es NP-duro.

Prueba: considere el caso de dos servidores,

y



Dividimos las cargas en dos subconjuntos con sumas iguales. Este es el problema de la

partición.

Dato: existe una aproximación-2 determinista al problema de asignación de difusión

mínima.

Prueba: suponga que dividimos la capacidad de la caché más grande en otras más

pequeñas



Luego, colocamos la carga

encima de éstas.

debería terminar encima de alguna

Digamos que es el Kth,



El número de arcos = el número de subintervalos. Contamos uno para el final de todas

las µ´s de N y las ρ’s de k.



Por tanto, la difusión =



Ahora compárelo con el algoritmo óptimo. OPT (Tecnología de protocolo abierto)

utiliza al menos N aristas. K= mínimo de aristas k. OPT consigue



Pregunta abierta: ¿puede obtener una aproximación 1 + ∈ para cualquier ∈ < 1 ó ∀∈ <

1?

MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



6.7 El problema de asignación round robin de difusión

mínima

Una asignación es round robin si satisface i-iii y:

iv. Dentro de cada fila A, las entradas no cero son iguales.

Problema: suponga que tenemos # elementos >> # cachés, y dado un problema ejemplo,

defina si existe una asignación round robin.

Si la divide en tres partes iguales, éstas deberán ir a servidores distintos. No estamos

simplemente considerando divisiones racionales, éstas deben ser



Problema: suponga que hay una asignación round robin; ¿puede usted obtener una

aproximación de factor constante a la asignación de difusión mínima?

Un algoritmo aleatorio para la asignación round robin de difusión mínima.

Suponga que



Suponga que



Paso 0: seleccione una permutación para todo i. Inicialice la asignación.



Paso

: Redistribuya la carga

uniformemente entre los primeros

servidores d de

, escogiendo el d más pequeño, de modo que la carga de cada

servidor siga siendo < ρ.




MIT 18.996 Lecture 6--13 de marzo de 2002 primavera de 2002



Teorema 6.1. El algoritmo acaba con una asignación round robin de difusión 1+

con probabilidad > 1 -

, dado que N es lo suficientemente grande.



Prueba: Compárela con un “algoritmo de referencia” que redistribuya toda la carga a

en el paso



Muestre que nuestro algoritmo coincide con el “algoritmo de referencia