Perbandingan DAG yang efisien melalui jaringan

Dalam sistem kontrol versi terdistribusi (seperti Mercurial dan Git ) ada kebutuhan untuk secara efisien membandingkan grafik asiklik terarah (DAG). Saya adalah pengembang Mercurial, dan kami akan sangat tertarik untuk mendengar tentang karya teoretis yang membahas kompleksitas waktu dan jaringan membandingkan dua DAG.

DAGs yang dimaksud dibentuk oleh revisi yang direkam. Revisi diidentifikasi secara unik oleh nilai hash. Setiap revisi bergantung pada nol (komit awal), satu (komit normal) atau lebih (gabungan komit) dari revisi sebelumnya. Berikut adalah contoh di mana revisi ake edilakukan satu demi satu sama lain:

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

Perbandingan grafik muncul ketika seseorang hanya memiliki sebagian dari sejarah dan ingin mengambil bagian yang hilang. Bayangkan saya harus ake cdan membuat xdan yberdasarkan c:

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

Di Mercurial, saya akan melakukan hg pulldan mengunduh ddan e:

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

Tujuannya adalah untuk mengidentifikasi ddan eefisien ketika grafik memiliki banyak (katakanlah, lebih dari 100.000) node. Efisiensi menyangkut keduanya

• kompleksitas jaringan: jumlah byte yang ditransfer dan jumlah perjalanan pulang-pergi jaringan yang diperlukan
• kompleksitas waktu: jumlah perhitungan yang dilakukan oleh dua server yang bertukar perubahan

Grafik khas akan sempit dengan beberapa trek paralel seperti di atas. Ada juga akan biasanya hanya segelintir node daun (kami menyebutnya kepala di Mercurial) seperti edan ydi atas. Akhirnya, ketika server pusat digunakan, klien akan sering memiliki beberapa set perubahan yang tidak ada di server, sementara server dapat memiliki 100+ perubahan baru untuk klien, tergantung pada siapa yang dulu klien terakhir menarik dari server. . Sebuah solusi asimetris disukai: server terpusat harus melakukan sedikit perhitungan dibandingkan dengan klien.

Dalam konteks ini, simpul grafik memiliki semacam pengidentifikasi unik (hash atau checksum), bukan? Jadi Anda tidak perlu melakukan semacam tes isomorfisme subgraph, Anda hanya perlu daftar node yang berbeda antara dua versi Anda, dan ujung-ujungnya tidak benar-benar berguna sama sekali untuk langkah ini. Makalah SIGCOMM 2011 saya " Apa bedanya? Rekonsiliasi set efisien tanpa konteks sebelumnya"(dengan Goodrich, Uyeda, dan Varghese) mempertimbangkan dengan tepat masalah ini: ternyata Anda dapat menentukan identitas node yang dipegang oleh satu tetapi tidak keduanya dari dua server yang berkomunikasi, menggunakan sejumlah komunikasi yang hanya proporsional ke jumlah node yang diubah dan hanya menggunakan satu perjalanan pulang pergi. Setelah Anda memiliki informasi itu, mudah untuk menarik perubahan itu sendiri dalam perjalanan pulang-pergi kedua, sekali lagi dengan komunikasi yang optimal.

Dalam solusi yang kami terapkan untuk Mercurial, kekhawatiran lain adalah asimetri: beban server harus diminimalkan untuk bandwidth keluar dan waktu CPU, dengan biaya beban klien.

Kedengarannya seperti proses dua langkah bagi saya.

1. tanyakan semua klien apakah mereka memiliki komitmen di mana induknya c
2. jika demikian, temukan semua anak c

Tugas 1. Saya pikir sebagian besar diproses di sisi klien, dan semua klien membutuhkan hash komit melalui net.