Από DistrSys
- 1o Πρόβλημα
- Με βάση το μοντέλο πρωτόκολλων πλυθησμών, απαντήστε στα ακόλουθα ερωτήματα:
- Έστω ο εξής εναλλακτικός ορισμός της δικαιοσύνης: "Όλες οι αλληλεπιδράσεις συμβαίνουν απέιρως συχνά". Επάγεται απο αυτόν τον ορισμό το ίδιο αποτέλεσμα με τον ορισμό της δικαιοσύνης που ορίσαμε? Αν ναι, εξηγείστε τους ισχυρισμούς σας. Αν όχι, δώστε αντιπαράδειγμα. Δώστε παράδειγμα δίκαιης εκτέλεσης όπου κάποια αλληλεπίδραση δεν συμβαίνει ποτέ. (Υπόδειξη: Χρησιμοποιείστε το leader election σε ένα πολύ απλό δίκτυο).
- Δώστε πρωτόκολλο υπολογισμού του κατηγορήματος: "Υπάρχει ζυγός αριθμός κόμβων με είσοδο 1;" όταν το αλφάβητο εισόδου είναι Χ={0,1} -- δηλαδή κάθε πράκτορας να δίνει τελικά έξοδο '1' όταν ο αριθμός των '1' στην είσοδο είναι ζυγός και έξοδο '0' στην αντίθετη περίπτωση. (Υπόδειξη: Χρησιμοποιείστε την ιδέα του live bit όπως αυτή παρουσιάστηκε στην Διαφάνεια 49).
- 2o Πρόβλημα
- Υλοποιείστε στο σύστημα Shawn τον σταθεροποιούμενο αλγόριθμο αμοιβαίου αποκλεισμού του Dijkstra για τοπολογίες δακτυλίου. Κατά την εκτέλεση του συστήματος, στον γύρο 3×δ, οι διεργασίες όπου id%AM==0 (το τελευταίο ψηφίο του AM σας + 1) λόγο σφαλμάτων αποκτούν μια τυχαία τιμή στην εσωτερική μεταβλητή του αλγορίθμου (στο διάστημα 0...k). Μελετήστε την συμπεριφορά του αλγόριθμου στις τοπολογίες που σας έχουν δοθεί. Μετρήστε τον χρόνο σταθεροποίησης του αλγορίθμου. Σχολιάστε την συμπεριφορά του αλγορίθμου.
|
Παράδοση:
- Η άσκηση είναι ατομική
- Η παράδοση γίνεται με την χρήση του εργαλείου submit-ds
- Η προθεσμία υποβολής είναι η
Παρασκευή 25 Φεβρουαρίου, ώρα 23:59 Παρασκευή 4 Μαρτίου, ώρα 23:59
- Σε περίπτωση που εντοπιστεί αντιγραφή, η άσκηση θα μηδενιστεί
Σχετικό υλικό:
Απαντήσεις:
| ΑΜ |
Βαθμός |
1 |
2 |
| 3518 | 1 | ✓ | ✓ |
| 3796 | 0.5 | ✓ | - |
| 3889 | 0.5 | ✓ | - |
| 3911 | 0.5 | ✓ | - |
| 3941 | 0.5 | ✓ | - |
| 3950 | 0.5 | ✓ | - |
| 3992 | 0.7 | ✓ | -0.3 |
| 3997 | 0.6 | -0.4 | ✓ |
| 3998 | 0.5 | ✓ | - |
| 4009 | 0.5 | ✓ | - |
| 4045 | 1 | ✓ | ✓ |
| 4053 | 0.5 | ✓ | - |
| 4060 | 0.5 | ✓ | - |
| 4082 | 0.5 | ✓ | - |
| 4112 | 0.5 | ✓ | - |
| 4116 | 0.6 | -0.2 | -0.2 |
| 4117 | 0.7 | -0.1 | -0.2 |
| 4129 | 1 | ✓ | ✓ |
| 4145 | 0.3 | -0.2 | - |
| 4182 | 0.8 | -0.1 | -0.1 |
| 4183 | 1 | ✓ | ✓ |
| 4188 | 0.9 | ✓ | -0.1 |
| 4200 | 0.3 | -0.2 | - |
| 4251 | 0.5 | - | ✓ |
| 4270 | 1 | ✓ | ✓ |
| 4288 | 0.8 | ✓ | -0.2 |
| 4387 | 0.5 | ✓ | - |
| 4397 | 0.5 | - | ✓ |
|
