Comparação eficiente de DAG em uma rede

Nos sistemas de controle de versão distribuído (como Mercurial e Git ), é necessário comparar eficientemente os gráficos acíclicos direcionados (DAGs). Sou desenvolvedor da Mercurial e gostaríamos muito de ouvir sobre o trabalho teórico que discute a complexidade de tempo e rede da comparação de dois DAGs.

Os DAGs em questão são formados pelas revisões registradas. As revisões são identificadas exclusivamente por um valor de hash. Cada revisão depende de zero (confirmação inicial), uma (confirmação normal) ou mais (confirmação de mesclagem) das revisões anteriores. Aqui está um exemplo onde as revisões apara eforam feitos um após o outro:

a --- b --- c --- d --- e

A comparação do gráfico aparece em cena quando alguém tem apenas parte da história e deseja recuperar a parte que está faltando. Imagine que eu tinha apara ce fez xe ycom base em c:

a --- b --- c --- x --- y

No Mercurial, eu faria hg pulle faria o download de e:

a --- b --- c --- x --- y
              \
                d --- e

O objetivo é identificar de eeficientemente quando o gráfico tiver muitos (digamos, mais de 100.000) nós. A eficiência diz respeito tanto a

• complexidade da rede: o número de bytes transferidos e o número de viagens de ida e volta à rede necessárias
• complexidade do tempo: a quantidade de computação feita pelos dois servidores que trocam conjuntos de alterações

Os gráficos típicos serão estreitos, com poucas trilhas paralelas, como acima. Há também será tipicamente apenas um punhado de nós folha (nós os chamamos de cabeças em Mercurial) como ee yacima. Finalmente, quando um servidor central é usado, o cliente geralmente possui alguns conjuntos de alterações que não estão no servidor, enquanto o servidor pode ter mais de 100 novos conjuntos de alterações para os clientes, dependendo de quem há muito tempo o último cliente retirou do servidor . Uma solução assimétrica é a preferida: um servidor centralizado deve fazer pouco cálculo em comparação com seus clientes.

Nesse contexto, os nós do gráfico têm algum tipo de identificador exclusivo (um hash ou soma de verificação), certo? Portanto, você não precisa fazer nenhum tipo de teste de isomorfismo de subgráfico, apenas precisa de uma lista dos nós que diferem entre suas duas versões, e as bordas não são realmente úteis para esta etapa. Meu documento do SIGCOMM 2011 " Qual é a diferença? Reconciliação eficiente de conjuntos sem contexto anterior"(com Goodrich, Uyeda e Varghese) considera exatamente esse problema: acontece que você pode determinar as identidades dos nós mantidos por um, mas não pelos dois servidores de comunicação, usando uma quantidade de comunicação que é proporcional apenas ao número de nós alterados e usando apenas uma única viagem de ida e volta.Uma vez que você tiver essas informações, é fácil fazer as próprias alterações em uma segunda viagem de ida e volta, novamente com a comunicação ideal.

Na solução que implementamos para o Mercurial, outra preocupação era a assimetria: a carga do servidor deveria ser minimizada tanto pela largura de banda de saída quanto pelo tempo da CPU, ao custo da carga do cliente.

Parece um processo em duas etapas para mim.

1. pergunte a todos os clientes se eles têm confirmações onde o pai é c
2. Nesse caso, encontre todos os filhos de c

A tarefa 1. Acho que é processada principalmente no lado do cliente, e todo o cliente precisa do hash de confirmação na rede.