Τμήμα
Πληροφορικής,
Χειμερινό Εξάμηνο Ακ. Έτους 2004-05
Η/Υ Ε07: Κατανεμημένα Συστήματα
Μάθημα
Επιλογής
Γενικά | Ανακοινώσεις | Ημερολόγιο | Project | Διαφάνειες Διαλέξεων & Άλλο Υλικό
Aνακοίνωση
Το project σας είναι
διαθέσιμο.
Προθεσμίες: Μέρος Α: 17 Δεκεμβρίου 2004
Μέρος Β: 14 Ιανουαρίου 2004
Δείτε link Project για περισσότερες πληροφορίες.
Διδάσκουσα:
Παναγιώτα Φατούρου
Γραφείο:
26 (Α’ ορόφου)
Ώρες Γραφείου:
Τρίτη: 12:00 – 13:00, Τετάρτη, 12:00-13:00
Ηλεκτρονική Διεύθυνση:
Τηλέφωνο:
(26510) 98808
Ηλεκτρονική
Διεύθυνση Μαθήματος:
Ηλεκτρονική Διεύθυνση Λίστας Μαθήματος:
Τρίτη,
15:00-18:00, στην αίθουσα Ι4.
Το μάθημα θα εστιάσει στη μελέτη της βασικής θεωρίας των κατανεμημένων συστημάτων. Πιο συγκεκριμένα, θα μελετηθούν διάφορα μοντέλα κατανεμημένου υπολογισμού, ένα μεγάλο σύνολο κατανεμημένων αλγόριθμων και κατανεμημένων δομών δεδομένων, ενώ θα αναλυθούν ζητήματα συγχρονισμού, ζητήματα ανοχής σε σφάλματα, καθώς και ζητήματα απόδοσης των κατανεμημένων συστημάτων.
Βιβλία
q H. Attiya and J. Welch, “Distributed Computing, Fundamentals, Simulations and Advanced Topics”, Mc Graw Hill, England, 1998.
q
q
q
q G. Coulouris, J. Dollimore and T. Kindberg, “Distributed Systems, Concepts and Design”, Addison-Wesley, 1994.
q
A.
S.
Tanenbaum,
“Σύγχρονα Λειτουργικά Συστήματα”, Prentice-Hall
International,
Κλειδάριθμος, Αθήνα.
Οι
διαφάνειες του μαθήματος μαζί με τις
σημειώσεις που μπορείτε να κρατάτε κατά την
παράδοση και οποιοδήποτε άλλο υλικό σας
δοθεί θα σας βοηθήσουν να διεκπεραιώσετε
επιτυχώς το μάθημα.
1η
εβδομάδα |
Εισαγωγή, Χαρακτηρισμός, Στόχοι, Ζητήματα Σχεδίασης |
2η
εβδομάδα |
Βασικοί Αλγόριθμοι σε Κατανεμημένα Συστήματα Μεταβίβασης Μηνυμάτων |
3η
εβδομάδα |
Αλγόριθμοι Επιλογής Αρχηγού |
4η
εβδομάδα |
Αλγόριθμοι Επιλογής Αρχηγού |
5η
εβδομάδα |
Αμοιβαίος Αποκλεισμός |
6η
εβδομάδα |
Αμοιβαίος Αποκλεισμός |
7η
εβδομάδα |
Αμοιβαίος Αποκλεισμός |
8η
εβδομάδα |
Concurrent Objects and Linearizability |
9η
εβδομάδα |
Concurrent Objects and Linearizability |
10η
εβδομάδα |
Κατανεμημένες Ουρές, στοίβες, λίστες & άλλες δομές δεδομένων |
11η εβδομάδα |
Causality and Time |
12η εβδομάδα | Κατανεμημένες Δοσοληψίες |
13η
εβδομάδα |
Άλλα βασικά ζητήματα |
Κατά τη διάρκεια του εξαμήνου θα δοθούν κάποιες θεωρητικές σειρές ασκήσεων και 1 προγραμματιστική εργασία. Ο προγραμματισμός θα γίνει σε γλώσσα C ή σε Java, ενώ ενδέχεται να χρησιμοποιηθούν διάφορα εργαλεία και περιβάλλοντα για να επιτευχθεί επικοινωνία μεταξύ διεργασιών. Κάθε εργασία θα πρέπει να επιστρέφεται πριν από την αναγραφόμενη ημερομηνία και ώρα. Καθυστερημένες σειρές ασκήσεων ή εργασίες γίνονται δεκτές με μείωση βαθμού 5 μονάδων (στις 100) για κάθε μέρα καθυστέρησης. Καθυστερημένες σειρές ασκήσεων ή εργασίες δεν γίνονται δεκτές μετά την εξέτασή τους. Οι ασκήσεις και η εργασία ενδέχεται να εξεταστούν γραπτώς (ή προφορικώς).
Ο
προγραμματισμός, όπως και η έκθεση, είναι
μια ιδιαίτερα ατομική εργασία. Καθένας
πρέπει ατομικά να κατανοήσει το πρόβλημα
και να σκιαγραφήσει μια πιθανή λύση του. Οι
λύσεις των ασκήσεων, καθώς και τα
προγράμματα που θα σας ζητηθούν πρέπει να
είναι αποτέλεσμα προσωπικής σας δουλειάς.
Είναι επίσης σημαντικό να μπορεί καθένας να
διαβάσει τον κώδικά σας. Οι αντιγραφές
απαγορεύονται αυστηρά και θα τιμωρούνται
με μείωση ή μηδένιση βαθμού. Είναι καλύτερα
να παραδώσετε μια ημιτελή εργασία παρά μια
παραλλαγμένη αντιγραφή.
Μπορείτε
να χρησιμοποιήσετε οποιονδήποτε
υπολογιστή για την προγραμματιστική σας
εργασία. Για τη
βαθμολόγηση της όμως, το
πρόγραμμά σας θα εκτελείται στα μηχανήματα
κάποιου εργαστηρίου του Τμήματος. Στα
μηχανήματα αυτά θα είναι εγκατεστημένο και
το απαραίτητο λογισμικό για να κάνετε τις
εργασίες σας. Όσοι από εσάς επιθυμούν να
εργαστούν σε άλλα μηχανήματα θα πρέπει να
σιγουρευτούν ότι ο κώδικας τους τρέχει
σωστά και στα παραπάνω μηχανήματα.
Είστε
υπεύθυνοι για την κακή χρήση του
λογαριασμού σας. Το password σας θα
πρέπει να παραμείνει μυστικό και ο
λογαριασμός σας να χρησιμοποιείτε μόνο από
εσάς. Φροντίστε τέλος η προστασία του
καταλόγου στον οποίο βρίσκονται τα
προγράμματά σας να μην επιτρέπει ανάγνωση (ή
ακόμη χειρότερα εγγραφή) από άλλους (χρησιμοποιήστε
την εντολή chmod).
Η
τελική εξέταση θα γίνει με ανοιχτά βιβλία.
Στην τελική εξέταση θα πρέπει όλοι οι
εξεταζόμενοι φοιτητές να έχουν μαζί τους το
πάσο τους. Φοιτητές που δεν έχουν μαζί τους
το πάσο τους δεν θα γίνονται δεκτοί στην
εξέταση.
Ο
τελικός βαθμός θα εξαρτηθεί τόσο από τη
βαθμολογία των ασκήσεων, όσο και από την
επίδοση των φοιτητών στην τελική εξέταση,
ως εξής:
Σειρές
Ασκήσεων: 35%
Τελική
Εξέταση: 65%
Προκειμένου
ένας φοιτητής να περάσει το μάθημα πρέπει
να γράψει τουλάχιστον 4.5 στο τελικό
διαγώνισμα, ανεξάρτητα από το πόσο καλές
είναι οι εργασίες που έχει παραδώσει και θα
πρέπει να έχει βαθμό τουλάχιστον 4.0 στις
εργασίες του (ανεξάρτητα από το πόσο καλό θα
είναι το γραπτό του στην τελική εξέταση).
Ο ίδιος
αλγόριθμος για την διεξαγωγή της
βαθμολογίας ισχύει και στην εξέταση του
Σεπτεμβρίου.
Η
παρακολούθηση στις διαλέξεις αναμένεται,
αλλά δεν είναι υποχρεωτική. Ωστόσο, οι
φοιτητές θα πρέπει να γνωρίζουν οτιδήποτε
παρουσιάζεται ή αναφέρεται στην τάξη στην
τελική εξέταση. Το μεγαλύτερο ποσοστό της ύλης δεν
περιέχεται σε βιβλία ή παρουσιάζεται με
άλλη σειρά, για αυτό η παρακολούθηση
συνίσταται ισχυρά.
Συνίσταται ισχυρά να έχετε διεκπεραιώσει με επιτυχία τα μαθήματα του «Προγραμματισμού σε C», των «Δομών Δεδομένων» και των «Λειτουργικών Συστημάτων». Επίσης, η γνώση «Βάσεων Δεδομένων», «Δικτύων Υπολογιστών» και «Σχεδίασης και Ανάλυσης Αλγορίθμων» θα βοηθούσε επίσης. Καλή γνώση της Αγγλικής γλώσσας θα διευκολύνει ουσιαστικά την επιτυχή διεκπεραίωση του μαθήματος.
§
Journal
of the ACM
§
SIAM
Journal on Computing
§
Distributed
Computing
§
Information
and Computation
§
IEEE
Transactions on Parallel and Distributed Systems
§
ACM
Transactions on Programming Languages and Systems
§
ACM
Transactions on Computer Systems
§
Journal
of Algorithms
§
Theory
of Computing Systems Journal
§
Algorithmica
§
Theoretical
Computer Science
§
Information
Processing Letters
§
Communications
of the ACM
§
Journal
of Computer and System Sciences
§
Acta
Informatica
§
Journal
of Computer and Systems Sciences
§
IEEE
Transactions on Computers
§
IEEE
Transactions on Software Engineering
§
Parallel
and Distributed Computing Practices
§
Parallel
Computing
§
Journal
of Parallel and Distributed Computing
§
Distributed
and Parallel Databases
§
International
Journal of High Speed Computing Networks
§
Cluster
Computing
§
Journal
of Supercomputing
§
The
International Journal of Supercomputer Applications and High
§
Performance
Computing
§
International
Journal of Parallel and Distributed Systems and
§
Networks
§
Parallel
Algorithms and Applications
§
Concurrency:
Practice and Experience
§
ACM
Symposium on Principles of Distributed Computing (PODC)
§
International
Symporium on DIStributed Computing (DISC)
§
IEEE
Symposium on Foundations of Computer Science (FOCS)
§
ACM
Symposium on Theory of Computing (STOC)
§
IEEE
Conference on Distributed Computing Systems
§
IPPS
& SPDP
§
S.
Dolev, Self-Stabilization, MIT Press, 2000.
§
M.
Raynal, Algorithms for Mutual Exclusion, MIT Press, 1986.
§
M.
Raynal, Networks and Distributed Computation: Concepts, Tools and Algorithms,
MIT Press, 1988.
§
Α.
Tanenbaum,
Computer Networks, Prentice-Hall, Inc., 1996.
§
G.
Tell, Introduction to Distributed Algorithms, Cambridge University Press,
1994.
E-mailing
Λίστα & Λογαριασμός Μαθήματος
Για το
μάθημα θα υπάρχει e-mailing
λίστα η οποία θα χρησιμοποιείται για την
αποστολή e-mail
σε όλους τους φοιτητές που έχουν δηλώσει το
μάθημα. Οι φοιτητές υποχρεούνται να
εγγραφούν στη λίστα το αργότερο μέχρι τις 15
Οκτωβρίου 2004. Για να εγγραφείτε στη λίστα
αρκεί να στείλετε ένα ηλεκτρονικό μήνυμα (e-mail)
στη διεύθυνση
με κενό
θέμα και σώμα:
subscribe <όνομα λίστας>
Η
e-mail
address
της λίστας είναι
.
Όλα τα e-mails
προς αυτή τη διεύθυνση θα λαμβάνονται από
όλους τους φοιτητές που έχουν εγγραφεί στη
λίστα.
Για
το μάθημα υπάρχει επίσης λογαριασμός με e-mail
address:
.
Το
e-mail
του λογαριασμού αυτού θα ελέγχεται συχνά.
Μπορείτε να στέλνετε e-mails
με απορίες τόσο στον λογαριασμό όσο και στη
λίστα. Τα e-mails σας θα πρέπει να απευθύνονται
προς τη λίστα μόνο αν πιστεύετε πως αυτά που
γράφετε ή ρωτάτε είναι χρήσιμα και
ενδιαφέροντα σε όλους τους συμφοιτητές σας.
Το Project είναι διαθέσιμο. Ημερομηνία Παράδοσης: Mέρος A, 17/12/2004, Μέρος Β: 14/1/2004. To project είναι υποχρεωτικό. Δείτε Διάφανειες Διαλέξεων και Άλλο Υλικό για περισσότερες πληροφορίες.
Οι σειρές ασκήσεων σας έχουν διορθωθεί. Μπορείτε να περάσετε από το γραφείο μου να τις πάρετε.
Η πρόοδος θα πραγματοποιηθεί την Τρίτη, 30/11 την ώρα του μαθήματος.
Το 2ο Σετ Ασκήσεων είναι διαθέσιμο. Ημερομηνία Παράδοσης: Δευτέρα, 22/11/2004. To σετ ασκήσεων αυτό είναι προαιρετικό.
Το 1ο Σετ Ασκήσεων είναι διαθέσιμο. Ημερομηνία Παράδοσης: Δευτέρα, 8/11/2004.
Το 1ο μάθημα θα γίνει την Τρίτη, 5 Οκτωβρίου 2004.
Δευτέρα | Τρίτη | Τετάρτη | Πέμπτη | Παρασκευή |
4/10
|
5/10
Εισαγωγή, Ζητήματα Σχεδιασμού, Μοντέλα Κατανεμημένου Υπολογισμού Μελέτη Υλικού που σας μοιράστηκε στο μάθημα & Διαφανειών Μαθήματος |
6/10
|
7/10
|
8/10
|
11/10
|
12/10 Syllabus & Ιntroduction. Μελέτη κεφαλαίου 1, Attiya & Welch Basic Algorithms in Message Passing Systems. Μελέτη κεφαλαίου 2, Attiya & Welch |
13/10
|
14/10
|
15/10
|
18/10
|
19/10
Leader Election in Rings. Μελέτη Ενοτήτων 3.1, 3.2, 3.3.1 και 3.3.2, Attiya & Welch
|
20/10
|
21/10
|
22/10
|
25/10
|
26/10
Leader Election in Rings. Μελέτη Ενότητας 3.4.1, Attiya & Welch. Shared Memory Systems - Mutual Exclusion. Μελέτη Ενοτήτων 4.1, 4.2, 4.3.1 και 4.3.2, Attiya & Welch 1η Άσκηση out |
27/10
|
28/10
|
29/10
|
1/11
|
2/11
Mutual Exclusion. Μελέτη Ενοτήτων 4.4.1, 4.4.2, 4.4.3 και 4.4.5, Attiya & Welch |
3/11
|
4/11
|
5/11
|
8/11
1η Άσκηση due |
9/11
Mutual Exclusion. Μελέτη Ενοτήτων 4.4.4 και 4.3.3, Attiya & Welch. Μελέτη Ενότητας 10.8, Nancy Lynch (φωτοτυπίες της ενότητας έχουν δοθεί για φωτοτύπηση). 2η Άσκηση out |
10/11
|
11/11
|
12/11
|
15/11
|
16/11
Mutual Exclusion. Μελέτη Ενοτήτων 4.4.4 και 4.3.3, Attiya & Welch. Μελέτη Ενότητας 10.8, Nancy Lynch (φωτοτυπίες της ενότητας έχουν δοθεί για φωτοτύπηση). |
17/11
|
18/11
|
19/11
|
22/11
2η Άσκηση due |
23/11
Consensus with link failures. Consensus with Process Failures. Μελέτη Ενοτήτων 5.1 και 6.7, Nancy Lynch (φωτοτυπίες των ενοτήτων έχουν δοθεί για φωτοτύπηση). |
24/11
|
25/11
|
26/11
|
29/11
|
30/11
Πρόοδος |
1/12
|
2/12
|
3/12
|
6/12
|
7/12 Consensus with Process Failures. Μελέτη Ενοτήτων 5.1, 5.3.1, Attiya & Welch. Μελέτη Ενοτήτων 12.2.1-12.2.4, και μελέτη Θεωρημάτων 6.31 και 6.32 (και αποδείξεις), Nancy Lynch (φωτοτυπίες των ενοτήτων έχουν δοθεί για φωτοτύπηση). |
8/12
|
9/12
|
10/12
|
13/12
|
14/12
Causality and Time. Μελέτη Ενοτήτων 6.1.1, 6.1.2, 6.1.3 (χωρίς παράγραφο 6.1.3.1), 6.1.4., 6.3.1-6.3.4. |
15/12
|
16/12
|
17/12
Project due |
20/12
|
21/12
Εξέταση Project |
Διακοπές Χριστουγέννων |
||
Διακοπές Χριστουγέννων |
||||
Διακοπές Χριστουγέννων |
||||
10/1
|
11/1
Εξέταση Project |
12/1
|
13/1
|
14/1
|
Προθεσμία
Παράδοσης
Μέρος Α: 17 Δεκεμβρίου 2004,
Όλο το project:
14 Ιανουαρίου 2004
Ανάθεση
Project
ανά Ομάδα
1.
Δρόσου
Μαρίνα – Τζώρτζης Γρηγόρης
a. Maged Michael, “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”, IEEE Transactions on Parallel and Distributed Systems, 2004.
b. Maged Michael and Michael Scott, “Simple, Fast and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”, ACM PODC.
2.
Καλλιμάνης
Νικόλαος
a. John Valois, “Lock-Free Linked Lists Using Compare-and-Swap”, ACM PODC 1995.
3.
Κοσμάς
Λευτέρης
a. Timothy Harris, “A pragmatic Implementation of Non-Blocking Linked-Lists”, DISC.
4.
Ντέτσικα
Μυρτώ
a. Yuh-Jzer Joung, “Asynchronous Group Mutual Exclusion”, PODC 1998.
5. Καλπακίδης Αλέξανδρος
a. Vassos Hadzilacos, “A note on group mutual exclusion”, PODC 2001.
6.
Κάννας
Χρίστος – Αθανασιάδης Θεόδωρος
a. M. Michael and M. Scott, “Fast Mutual Exclusion, Even with Contention”, TR 1993.
b. M. Choy and A. Singh, “Adaptive Solutions to the Mutual Exclusion Problem”, ACM PODC 1993.
7.
Αθανασόπουλος
Διονύσης – Φωτιάδου Κατερίνα
a. James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks. Journal of the Association for Computing Machinery 41(5):1020-1048, September 1994.
b. Marc D. Riedel and Jehoshua Bruck, “Tolerating Faults in Counting Networks”, http://citeseer.ist.psu.edu/102978.html
8. Καπόλος Χαράλαμπος
a. K. Chandy and J. Misra, “The Drinking Philosophers Problem”, ACM Transactions on Programming Languages and Systems, 1984.
9.
Λάππα Αλεξάνδρα
a. K. Mani Chandy and Leslie Lamport, “Distributed Snapshots: Determining Global States of Distributed Systems”, ACM Transactions on Computer Systems, 1985.
10.
Χριστοδουλίδου
Μαρία – Κουρή Φροσίνη
a. Υλοποίηση τεχνικών replication στο Chord.
b. A. Gupta, B. Liskov and R. Rodrigues, One Hop Lookups for P2P Overlays, USENIX.
ή
J. Aspnes and G. Shah, “Skip Graphs”, SODA.
11. Βόγκλης Απόστολος
a. M. Demmer and M. Herlihy, “The arrow distributed Directory Protocol”, pp.119-133, DISC 1998.
Περιγραφή
Project
Κάθε εργασία περιλαμβάνει την κατανόηση ενός (ή δύο) papers (ανάλογα με το αν έχετε ομάδα ή κάνετε το project μόνοι σας) και την υλοποίηση των αλγορίθμων που περιγράφονται σε αυτά. Η υλοποίηση θα γίνει σε C χρησιμοποιώντας POSIX threads ή το MPI (Message Passing Interface).
Μέρος
Α: Στο μέρος Α
θα πρέπει να μελετήσετε και να κατανοήσετε
τα papers του project
σας, να σχεδιάσετε τις υλοποιήσεις που θα
πρέπει να κάνετε και να παρουσιάσετε το paper
καθώς και τον σχεδιασμό σας. Θα πρέπει
επίσης να αποφασίσετε πως θα μοιραστεί η
δουλειά που πρέπει να γίνει στο project
ανάμεσα στα δύο άτομα της ομάδας.
Παραδοτέα
του 1ου μέρους είναι μια παρουσίαση
στην οποία θα περιγράψετε όλα τα παραπάνω.
Μέρος
Β: Αυτό είναι
το κύριο μέρος του project
στο οποίο θα πρέπει να υλοποιήσετε τους
αλγορίθμους που περιγράφονται στα papers του project σας.
Το παραδοτέο του μέρους αυτού είναι ο κώδικας και μια αναφορά για τον τρόπο που δουλέψατε.
Ανάθεση Project και Οδηγίες (projects.doc)
2ο Σετ Ασκήσεων (ds2004-hw2.doc)
1ο Σετ Ασκήσεων (ds2004-hw1.doc)
Γενικές Πληροφορίες για το μάθημα (distributed-systems-2004.doc)
Τελευταία
τροποποίηση:9/11/04
Κατασκευή και συντήρηση
σελίδων: Παναγιώτα
Φατούρου