Σπιτάκι

Πριν από μερικούς μήνες κάποιοι υπολογίσαν ότι το BitTorrent ευθύνεται για το ένα τρίτο της δραστηριότητας στο διαδίκτυο.

Ήταν και στο Slashdot, οπότε κάποιοι θα το έχετε ήδη δει, αλλά τώρα η Microsoft Research δημιούργησε το Avalanche, το οποίο είναι κάτι σα BitTorrent, βασισμένο όμως σε network coding. Το paper των Γκαντζίδης και Rodriguez εξηγεί την ιδέα με λεπτομέρεια.

Η ιδέα γενικά είναι η εξής. Αν θέλω να σου πω τις τιμές δέκα αριθμών, μπορώ είτε να σου δώσω τους δέκα αριθμούς, είτε να σου δώσω δέκα linearly independent γραμμικούς συνδιασμούς τους. Με δέκα εξισώσεις, μετά μπορείς να τις λύσεις μόνος σου και να βρεις τους δέκα αριθμούς.

Το πλεονέκτημα του να κάνουμε κάτι τέτοιο είναι ότι οι δέκα πληροφορίες που θα σου δώσω δεν είναι συγκεκριμένες. Αν σου πω τους αριθμούς, είναι συγκεκριμένα αυτά που πρέπει να μαζέψεις. Αν σου δώσω γραμμικούς συνδιασμούς, τότε είσαι εντάξει με οποιουσδήποτε δέκα γραμμικά ανεξάρτητους συνδιασμούς.

Αν μιλάμε ένας προς έναν, προφανώς δεν υπάρχει μεγάλη διαφορά. Αλλά αν ένα άτομο θέλει να δώσει την πληροφορία σε εκατοντάδες, καλό είναι η απουσία ενός μέρος του παζλ να μην είναι deal-breaker. (Σα το #12, εκείνη την τύπισα ντυμένη στα μωβ, που την έβλεπες κάπως από πίσω να κοιτάει προς τα δεξιά, και έλλειπε σε όλους από τα Snorkles άλμπουμ μας στο δημοτικό, και αναγκάστηκα να ζητήσω από τον παππού μου, στη Θεσσαλονίκη, να μου το αγοράσει από την Panini.) Aν ο server φύγει σε κάποια φάση, και φύγουν και αρκετοί seeds που έχουν ένα σπάνιο κομμάτι, με κάτι σα το BitTorrent μπορεί η ολοκλήρωση του αρχείου να είναι αδύνατη. Αν όμως, με network coding, ο server δώσει 150 γραμμικούς συνδιασμούς 100 πραγμάτων πριν φύγει, είναι δύσκολο να χαθούν τα 51 κομμάτια.

Η ιστορία δεν είναι μόνο στον server όμως, εξού και το network στο όνομα. Όταν ζητήσει ο ένας client από τον άλλον ένα κομμάτι, δε θα πάρει έναν από τους γραμμικούς συνδιασμούς που έδωσε ο server, μα ένα νέο γραμμικό συνδιασμό όλων των κομματιών που έχει ο άλλος client. Αυτό είναι το network coding, ότι coding κάνουν όλοι οι κόμβοι, και γενικά βοηθάει πολύ σε διάφορες καταστάσεις, πχ. στο να συνεχίζουν να βρίσκουν ενδιαφέροντα οι γρήγοροι τα πακέτα των αργών.

Διαβάζοντας το άρθρο σκεφτόμουν πως καλά όλα αυτά, για την ακρίβεια πολύ καλά, αλλά υπάρχει και το θέμα του security. Όταν παίρνεις ένα μεγάλο αρχείο με εκατό κομμάτια, μπορεί ο server να σου δώσει και ένα hash για το καθένα. (Για την ακρίβεια, αυτό νομίζω είναι ένα μεγάλο κομμάτι των .torrent files.) Αν όμως υπάρχουν πρακτικά άπειροι γραμμικοί συνδιασμοί (2^16 αναφέρει πχ. το άρθρο), τότε πως ακριβώς κάνεις hash τον καθένα; Και αν δεν τους κάνεις hash, τότε μπορεί να μπει ο καθένας, να αλλάξει κανά δυό coefficients, και να χαλάσει το αρχείο για όλο το swarm. Ακόμα χειρότερα, δε θα ξέρεις καν ποιός γραμμικός συνδιασμός φταίει για να τον πετάξεις. Και δε μιλάμε μόνο για κακούς users, μιλάμε και για λάθη δικτύου.

Το θέμα το αναφέρουν μόνο στην τελευταία τους παράγραφο, και συζητάνε κάτι “homomorphic collision-resistant hash functions … that survive network coding operations and consume very little computational resources.” Σα να λέμε blah blah blah. : ) Το understanding μου κάπου εδώ με εγκαταλείπει. Πάντως αν δε καταφέρουν να φτιάξουν το συγκεκριμένο πρόβλημα με έναν καλό τρόπο, το BitTorrent δε θα το ρίξουνε.

Επίσης, η MSFT είχε πρόσφατα ένα “meet the hackers day.” Το ενδιαφέρον άρθρο στο c|net.