MIT 18.996
Aula 6 | 13 de março de 2002
Segundo Trimestre 2002
_______________________________________________________________________________
MIT 18.996: Tópicos da Teoria da Ciência da Computação: Problemas de Pesquisa na
Internet – Segundo Trimestre 2002
Aula 6 | 13 de março de 2002
Palestrante: Bobby Kleinberg ([email protected])
Redator: Laura McCann
6.1 O Modelo
Vamos considerar um conjunto de itens (ex.: objetos da Web armazenados em cache), um
conjunto de caches (ex.: servidores) e um conjunto de diferentes exibições (ex.: clientes em
diferentes partes da rede).
Let I = {itens} com |I| = N
Let C = {caches} COM |C| = M
Let V = exibições (views) com |V| = V
com |Vi |
Obs.: N deve ser muito grande e, em geral, só demonstraremos resultados para N grande.
Lembre-se de que a maioria dos protocolos usados para localização de objetos contém
estas propriedades.
•
•
•
Localidade
Escalabilidade
Equilíbrio de carga
Uma função hash com faixas (RHF, ranged hash function) é um mapa que obtém uma
exibição e um item e armazena -os em um cache em que é possível encontrar esse item.
Uma família hash com faixas (ranged hash family) é um conjunto finito de funções hash com
faixas.
Uma função hash com faixas aleatórias é uma amostra uniforme de um conjunto desse tipo.
As propriedades de uma RHF aleatória “satisfatória” estão em um ambiente de cache
distribuído:
1.
Equilíbrio de carga (média de todas as exibições)
2.
Localidade (no nosso modelo, distância não é uma variável na função; por isso,
optamos por retirá-la)
3.
Suavidade (a função não deve mudar muito quando as entradas não mudarem muito)
4.
Redundância/Difusão
5.
Cálculo Eficiente
6.
Representação Eficiente
7.
Invertível (não necessariamente desejado)
6-1
MIT 18.996
Aula 6 | 13 de março de 2002
Segundo Trimestre 2002
_______________________________________________________________________________
6.1.1
Equilíbrio de Carga
número de
para algum
Neste caso, usamos a variável b porque estamos exibindo-a como compartimentos. Esse é
um número de itens que será armazenado em um compartimento específico.
6.1.2 Equilíbrio
Equilíbrio é diferente de equilíbrio de carga. Gostaríamos que cada exibição fosse a mais
equilibrada possível, de modo que o oposto de uma exibição não consiga sobrecarregar
facilmente um cache.
Com
de alta probabilidade, atribui a fração
a b.
com alta probabilidade, o número de
0 se
se
6.1.3 Suavidade
A suavidade é determinada por quanto uma função hash muda quando a exibição muda.
?(V 1,V 2) = número de itens combinados para diferentes valores de cache.
?(V 1,V 2) = número de
6.1.4
Difusão
σ(i) = número de
Representa o número máximo de caches que ele consegue combinar.
6.2
RHF aleatória simples
Agora temos que fornecer uma RHF aleatória simples. Normalmente, uma sugestão é
escolha
aleatoriamente.
Essa fórmula funciona?
NÃO! Ela possui propriedades de difusão inválidas.
E que tal uma outra opção óbvia, escolhendo o número de caches em uma exibição?
Essa opção funciona muito bem para equilíbrio, mas não para suavidade. Vamos dar uma
olhada em um exemplo simples de uma difusão inválida.
1
a
a
X
2
b
b
X
3
c
a
X
4
a
b
X
5
b
a
X
6
c
b
7
a
a
8
b
b
9
c
a
Nesse caso, existe uma alteração esperada de 2/3, o que fica ainda pior para números
maiores. Vamos tentar outro exemplo.
Escolha uma permutação
aleatório.
,
1
1
2
3
4
5
1
4
2
3
2
5
3
1
4
3
2
1
5
2
4
4
5
3
1
uniformemente e independentemente de modo
3
2
4
5
6-2
MIT 18.996
Aula 6 | 13 de março de 2002
Segundo Trimestre 2002
_______________________________________________________________________________
Dado (V,i), hash essa expressão para
minimizando
.
Essa fórmula equaciona para a escolha do primeiro na lista (a partir da esquerda) que seja
membro do conjunto V.
Suponha que V = {2, 4, 5}.
Então, escolheríamos 5, 5, 5, 4.
Obs.: o exemplo dado em aula não foi fornecido com um gerador de números aleatórios e
não contém um tamanho de amostragem suficiente para demonstrar as propriedades
realmente válidas dessa RHF aleatória. Por isso, não devemos esperar receber 3 números 5
e um número 4.
Teorema auxiliar: com a probabilidade
Evidência: a função hash obviamente contém um bias do lado esquerdo da linha. Queremos
provar que cada exibição, V, faz interseção com 1 das primeiras colunas σ no quadro com
alta probabilidade.
Teorema auxiliar: com probabilidade
Exibições cujo tamanho seja
de modo que cada compartimento receberia uma carga
de
. Essa fórmula informa que o fator que ela excede o perfeito é logarítmico e é
um termo 0(1).
Prova: coloque
Com probabilidade
, alguma exibição está separada de
para algum i.
Para qualquer compartimento b e item i Pr[b está nas primeiras colunas σ′ da linha i] =
E[número de linhas para que isso ocorre] =
Aplicamos a vinculação de Chernoff para obter a instrução “com alta probabilidade”.
Obs.: as vinculações de Chernoff mostram que a soma não pode ser muito maior do que o
esperado.
Temas: comparada com uma função hash sem faixas, a difusão e carga são apenas
logaritmicamente piores.
Advertência: (vinculação com suavidade) Com
6.3
de alta probabilidade
Uma RHF melhor
obtém um ponto
de modo uniforme e independente aleatoriamente.
obtém um conjunto de pontos k log m de modo uniforme e independente
aleatoriamente.
6-3
MIT 18.996
Aula 6 | 13 de março de 2002
Segundo Trimestre 2002
_______________________________________________________________________________
Dado um item (V,i), mapeie-o para o primeiro compartimento
horário começando por ri .
Precisamos dos pontos
que encontrar no sentido
do círculo de unidade onde K é uma constante.
6.4
Aplicações
Árvores Aleatórias e Hashing Consistente – Karger, L, L, L, L, P
{itens}, C = {caches}
um servidor de origem s(i)
Navegador: para
, árvore d-nary com nós |V|. Mapeie cada nó da árvore para um cache
usando uma função hash consistente e fixa, em que o termo “fixa” indica que cada
navegador deve usar a mesma árvore hash consistente.
Ao solicitar um objeto i, escolha um randomleaf dessa árvore.
Identifique o caminho para a raiz e apresente a solicitação para o cache nessa folha,
indicando o caminho inteiro.
Cache: mantenha um contador
, que é aumentado a cada solicitação para i. Se i
estiver em cache, distribua-o. Encaminhe -o para o sucessor e armazene o objeto em cache
quando o contador chegar a q (um parâmetro otimizável).
O servidor de origem serve o objeto.
6.5
CHORD
Não-hierárquico: cada nó conhece apenas um fator logarítmico do cache. Siga o ponteiro
que leva ao local mais próximo ao ponto. Procure pela chave ou por uma maneira de chegar
mais perto dela. Você espera até que alguém tenha um link direto.
O número de hops é o logaritmo do número de caches.
6.6
Problema de atribuição de difusão mínima
Suponha que tenhamos n itens e m caches.
Os itens têm cargas
e os caches têm capacidades
.
Objetivo: encontrar a atribuiçã o com o menor número de pontas possível.
Uma atribuição fracional é uma matriz, A = (a ij ) que satisfaz a
i.
ii.
iii.
Difusão =
Nosso objetivo é minimizar a difusão.
Fato: o problema da atribuição da difusão mínima é NP-hard.
Prova: considere o caso de 2 servidores, ρ 1 = ρ 2 = 1 e
Dividimos as cargas em dois subconjuntos com somas iguais. Esse é o problema de
partição.
6-4
MIT 18.996
Aula 6 | 13 de março de 2002
Segundo Trimestre 2002
_______________________________________________________________________________
Fato: existe uma aproximação 2 determinística para o problema de atribuição de difusão
mínima.
Prova: suponha que solicitemos do maior para o menor ρ i
.
Colocamos µ i no início deles. µ n deve terminar com algum ρ. Vamos supor que seja com o
enésimo k, ρ k.
O número de arcos é igual ao número de sub-intervalos. Contamos um para o final de todos
os N µs e os K ρ s.
Sendo assim, a difusão é
.
Agora compare com o algoritmo ideal. OPT usa, pelo menos, N pontas. K é igual ao número
mínimo de k pontas. OPT obtém ≥ MAX [N,k]
N + k ≤ 2MAX[N,k]
Pergunta em aberto: é possível obter uma aproximação 1+ ∈ para qualquer ∈ < 1 ou
?
6.7
Problema de atribuição de round-robin de difusão mínima
Uma atribuição é um round-robin se satisfizer a todas as afirmações descritas em i-iii e:
iv.
Dentro de cada linha A, as entradas diferentes de zero forem iguais.
Problema: suponha que # itens >> que # caches. Dada uma instância de problema,
determine se existe uma atribuição round-robin.
Se você dividi-la em três partes iguais, elas terão que passar por diferentes servidores. Não
estamos considerando apenas divisões racionais; elas devem ser
.
Problema: suponha que exista uma atribuição round-robin; é possível obter uma
aproximação de fator constante para a atribuição de difusão mínima?
Um algoritmo aleatório para a atribuição round-robin de difusão mínima.
Suponha que ρ 1 = ρ 2 = ... = ρ m
µ 1 < µ 2 < ... < µn
Suponha que ρ m(1 + ∈ 1)µ
Etapa 0: escolha uma permutação aleatória para todo i. Inicialize a atribuição
Etapa (1 ≤ i ≤ N): redistribua a carga µ i igualmente entre os primeiros servidores d em πi ,
escolhendo o menor de modo que a carga em cada servidor continue sendo < ρ.
Teorema 6.1. O algoritmo termina com uma atribuição round-robin da difusão 1 + ∈ 2 com
probabilidade > 1 – ∈ 3 desde que N seja grande o suficiente.
Prova: compare com um “algoritmo de referência” em que na etapa i redistribua toda a
carga para p 1(1).
Mostre que nosso algoritmo coincide com o “algoritmo de referência” nas etapas 1, 2, ..., N0,
onde
Deixe
ser a carga no servidor j na etapa i do o algoritmo de referência.
é um martingale.
Um martingale contém
Use a desigualdade de Azuma. Nenhum servidor fica sobrecarregado.
6-5
MIT 18.996
Aula 6 | 13 de março de 2002
Segundo Trimestre 2002
_______________________________________________________________________________
6.8
Questões em Aberto
1. Melhore a vinculação inferior em N no teorema
2. Trabalhe com capacidades distintas ?s.
3. Trabalhe com gráficos de duas partes não completos.
4. Use capacidades e cargas multidimensionais.
5. Encontre outras instâncias de algoritmos cujos resultados sejam quase independentes da
entrada.
6-6