2008-2009:Κατανεμημένα Συστήματα Ι:Ασκήσεις:Εξέταση Φεβρουαρίου

1^o Θέμα [40%]

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας. Για κάθε μια από τις παρακάτω προτάσεις απαντήστε στο κατά πόσο μπορούμε να δώσουμε μια ορθή αλγοριθμική λύση χωρίς να κάνουμε επιπλέον υποθέσεις για το μοντέλο υπολογισμού. Εξηγήστε την απάντηση σας.

1. Μπορούμε να καταμετρήσουμε τις διεργασίες του συστήματος αν οι διεργασίες δεν έχουν μοναδικές ταυτότητες και δεν έχουν πρόσβαση σε κάποια γεννήτρια τυχαίων αριθμών.
2. Μπορούμε να συγχρονίσουμε τα ρολόγια δυο διεργασιών ακόμα και αν σε οποιαδήποτε εκτέλεση του συστήματος μπορεί να συμβούν ε σφάλματα επικοινωνίας.
3. Μπορούμε να υπολογίσουμε τη διάμετρο του δικτύου ακόμα και αν σε οποιαδήποτε εκτέλεση του συστήματος το πολύ β διεργασίες μπορούν να παρουσιάσουν βυζαντινά σφάλματα.
4. Μπορούμε να μετατρέψουμε οποιοσδήποτε αλγόριθμο A σε σταθεροποιούμενο δεδομένου ενός ορθού αλγόριθμου συνεπών ολικών στιγμιοτύπων.

2^o Θέμα [30%]

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

3^o Θέμα [30%]

Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας, όπου κάθε διεργασία έχει μια μοναδική ταυτότητα αλλά δεν γνωρίζει το σύνολο των διεργασιών, ούτε την τοπολογία του δικτύου. Προτείνετε μια αλγοριθμική λύση που να επιτρέπει σε μια διεργασία u₀ να εντοπίσει την διεργασία με τον μέγιστο αριθμό γειτόνων (αν είναι περισσότερες από μια, εντοπίζει αυτή με την μικρότερη ταυτότητα). Περιγράψτε τον αλγόριθμό σας, αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.

Ως αλγοριθμική λύση θεωρούμε είτε έναν αλγόριθμο (από την βιβλιογραφία) είτε μια συλλογή αλγορίθμων (από την βιβλιογραφία) είτε έναν νέο αλγόριθμο. Κατά την περιγραφή της πρότασης σας, αναφέρετε ξεκάθαρα όποιες επιπλέον υποθέσεις πρέπει να γίνουν ως προς τον τρόπο λειτουργίας του συστήματος πέρα από αυτές που αναφέρονται σε κάθε ερώτημα.