Διάδοση εμπιστοσύνης με μεθόδους βασισμένες στη φυσική

Abstract

Τα τελευταία χρόνια παρατηρείται ταχύτατη διάδοση των Peer to Peer (P2P) δικτύων και η χρήση τους επεκτείνεται συνεχώς σε νέους τομείς, με πιο γνωστή την χρήση τους για διακίνηση αρχείων. Τα δίκτυα αυτά, σε αντίθεση με την καθιερωμένη αρχιτεκτονική πελάτη - εξυπηρετητή (client-server), όπου υπάρχει ένας κεντρικός εξυπηρετητής με τον οποίο επικοινωνούν όλοι οι πελάτες, αποτελούνται από υπολογιστές, που λέγονται peers και δρουν ταυτόχρονα ως πελάτες και ως εξυπηρετητές. Κάθε χρήστης, ως πελάτης παράγει αιτήσεις, με κάποιο ρυθμό, τις οποίες διαχωρίζει ("σπάει") στους υπόλοιπους εξυπηρετητές. Ως εξυπηρετητής κάθε χρήστης εξυπηρετεί τις εισερχόμενες αιτήσεις βάσει μιας πολιτικής προτεραιοτήτων. ϊ. Ένα βασικό κριτήριο απόδοσης των δικτύων αυτών είναι η μέση καθυστέρηση απόκτησης ενός αρχείου, η οποία εξαρτάται από τον διαχωρισμό των αιτήσεων στους κόμβους άλλα και από την πολιτική εξυπηρέτησης κάθε εξυπηρετητή. Σκοπός της εργασίας αυτής είναι η λύση του προβλήματος ελαχιστοποίησης της μέσης βεβαρημένης καθυστέρησης στο δίκτυο, όπου η καθυστέρηση κάθε χρήστη εκφράζεται είτε ως η μέση καθυστέρηση του χρήστη στο σύστημα είτε ως η το μέγιστο εκ των καθυστερήσεων σε κάποιο εξυπηρετητή. Η πρώτη περίπτωση είναι μια συνηθισμένη μετρική απόδοσης στην οποία θα χρησιμοποιήσουμε τον ομ rule για τον καθορισμό των προτεραιοτήτων από τους εξυπηρετητές. Η δεύτερη εκφράζει την περίπτωση παράλληλης εξυπηρέτησης από τους διάφορους εξυπηρετητές και μελετούμε αν ισχύει ο ομ rule. Για την εύρεση του βέλτιστου τρόπου διαχωρισμού των αιτήσεων παρουσιάζουμε έναν κατανεμημένο αλτρουιστικό αλγόριθμο, όπου κάθε χρήστης ελαχιστοποιεί μια έκφραση που συμπεριλαμβάνει και τις καθυστερήσεις των κόμβων μικρότερης προτεραιότητας. Ο αλγόριθμος αυτός βασίζεται στην τεχνική του waterfilling και παρουσιάζουμε τον τρόπο με τον οποίο είναι δυνατή η υλοποίησή του με κατανεμημένο τρόπο και με ελάχιστη ανταλλαγή μηνυμάτων ανάμεσα στους κόμβους. Η εργασία οργανώνεται ως εξής. Στο κεφάλαιο 1 κάνουμε μια εισαγωγή στα P2P δίκτυα παρουσιάζοντας τα κύρια χαρακτηριστικά και εφαρμογές τους. Στο κεφάλαιο 2 παρουσιάζουμε προηγούμενες εργασίες για τα δίκτυα αυτά. Στο κεφάλαιο 3 περιγράφουμε το μοντέλο του συστήματος. Τα κεφάλαια 4 και 5 περιλαμβάνουν την περιγραφή και ανάλυση των προτεινόμενων αλγορίθμων για τον υπολογισμό της καθυστέρησης ως ο μέσος όρος ή το μέγιστο της καθυστέρησης σε κάθε εξυπηρετητή αντίστοιχα . Τέλος, στο κεφάλαιο 6 αναφέρονται τα συμπεράσματα από την παρούσα εργασία.