Τμήμα Πληροφορικής, Εαρινό Εξάμηνο Ακ. Έτους 2005-06

Η/Υ Ε07: Κατανεμημένα Συστήματα

Μάθημα Επιλογής

Γενικά | Ανακοινώσεις | Ημερολόγιο | Project | Διαφάνειες Διαλέξεων & Άλλο Υλικό

Γενικές Πληροφορίες

Διδάσκουσα:                                       Παναγιώτα Φατούρου
Γραφείο:                                              26 (Α’ ορόφου)
Ώρες Γραφείου:                                  Πέμπτη: 11:00 – 12:00 & Τετάρτη, 11:00 - 12:00
Ηλεκτρονική Διεύθυνση:                    faturuATcs.uoi.gr
Τηλέφωνο:                                          (26510) 98808

Ηλεκτρονική Διεύθυνση Μαθήματος: cse07ATcs.uoi.gr
Ηλεκτρονική Διεύθυνση Λίστας Μαθήματος: cse07listATcs.uoi.gr

Ώρες και Αίθουσες Διδασκαλίας

Πέμπτη, 12:00-15:00, στην αίθουσα Ι4.

Σύνοψη Μαθήματος

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

Βιβλία

q H. Attiya and J. Welch, “Distributed Computing, Fundamentals, Simulations and Advanced Topics”, Mc Graw Hill, England, 1998.

q Nancy A. Lynch, "Distributed Algorithms", Morgan Kaufmann Publishers, Inc., 1996.

Το υλικό που θα σας δοθεί, και οι διαφάνειες του μαθήματος μαζί με τις σημειώσεις που μπορείτε να κρατάτε κατά την παράδοση θα σας βοηθήσουν να διεκπεραιώσετε επιτυχώς το μάθημα.

Πρόγραμμα

1^η εβδομάδα	Εισαγωγή, Χαρακτηρισμός, Στόχοι, Ζητήματα Σχεδίασης
2^η εβδομάδα	Βασικοί Αλγόριθμοι σε Κατανεμημένα Συστήματα Μεταβίβασης Μηνυμάτων
3^η εβδομάδα	Αλγόριθμοι Επιλογής Αρχηγού
4^η εβδομάδα	Αλγόριθμοι Επιλογής Αρχηγού
5^η εβδομάδα	Αμοιβαίος Αποκλεισμός
6^η εβδομάδα	Αμοιβαίος Αποκλεισμός
7^η εβδομάδα	Αμοιβαίος Αποκλεισμός
8^η εβδομάδα	Επίτευξη ομοφωνίας
9^η εβδομάδα	Επίτευξη ομοφωνίας
10^η εβδομάδα	Causality and Time
11η εβδομάδα	Ατομικά Αντικείμενα και γραμμικοποιησιμότητα
12η εβδομάδα	Κατανεμημένες Ουρές, στοίβες, λίστες & άλλες δομές δεδομένων

Εργασίες και Βαθμολόγηση

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

Η τελική εξέταση θα γίνει με ανοιχτά βιβλία. Στην τελική εξέταση θα πρέπει όλοι οι εξεταζόμενοι φοιτητές να έχουν μαζί τους το πάσο τους.

Ο τελικός βαθμός θα εξαρτηθεί τόσο από τη βαθμολογία των ασκήσεων, όσο και από την επίδοση των φοιτητών στην τελική εξέταση, ως εξής:

Σειρές Ασκήσεων & Εργασία: 35%

Τελική Εξέταση: 65%

Φοιτητές που δεν θα γράψουν τουλάχιστον 4 στο τελικό διαγώνισμα δεν θα περάσουν το μάθημα. Ο ίδιος αλγόριθμος για την διεξαγωγή της βαθμολογίας ισχύει και για την εξέταση του Σεπτεμβρίου.

Παρακολούθηση

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

Παρατήρηση

Συνίσταται ισχυρά να έχετε διεκπεραιώσει με επιτυχία τα μαθήματα των «Δομών Δεδομένων», των «Σχεδίασης και Ανάλυσης Αλγορίθμων» και των «Λειτουργικών Συστημάτων». Καλή γνώση της Αγγλικής γλώσσας θα διευκολύνει ουσιαστικά την επιτυχή διεκπεραίωση του μαθήματος.

E-mailing Λίστα & Λογαριασμός Μαθήματος

Για το μάθημα θα υπάρχει e-mailing λίστα η οποία θα χρησιμοποιείται για την αποστολή e-mail σε όλους τους φοιτητές που έχουν δηλώσει το μάθημα. Οι φοιτητές υποχρεούνται να εγγραφούν στη λίστα το αργότερο μέχρι τις 9 Μαρτίου 2006. Για να εγγραφείτε στη λίστα αρκεί να στείλετε ένα ηλεκτρονικό μήνυμα (e-mail) στη διεύθυνση

majordomoΑΤcs.uoi.gr

με κενό θέμα και σώμα:

subscribe cse07list

Η e-mail address της λίστας είναι cse07listΑΤcs.uoi.gr. Όλα τα e-mails προς αυτή τη διεύθυνση θα λαμβάνονται από όλους τους φοιτητές που έχουν εγγραφεί στη λίστα.

Για το μάθημα υπάρχει επίσης λογαριασμός με e-mail address: cse07ΑΤcs.uoi.gr. Το e-mail του λογαριασμού αυτού θα ελέγχεται συχνά. Μπορείτε να στέλνετε e-mails με απορίες τόσο στον λογαριασμό όσο και στη λίστα. Τα e-mails σας θα πρέπει να απευθύνονται προς τη λίστα μόνο αν πιστεύετε πως αυτά που γράφετε ή ρωτάτε είναι χρήσιμα και ενδιαφέροντα σε όλους τους συμφοιτητές σας.

Ανακοινώσεις

Περιγραφή Project (project-description.doc).

Οι διαφάνειες των διαλέξεων για το πρόβλημα του χρονισμού είναι διαθέσιμες (causality.pdf).
Οι διαφάνειες των διαλέξεων για το πρόβλημα της ομοφωνίας είναι διαθέσιμες (consensus.pdf).
To 2o μέρος της Σειράς Ασκήσεων είναι διαθέσιμο (ds2006-hw-part2.doc).
To 1o μέρος της Σειράς Ασκήσεων είναι διαθέσιμο (ds2006-hw1.doc).
Οι διαφάνειες των μέχρι τώρα διαλέξεων είναι διαθέσιμες (lecture1-2.pdf και mutual-exclusion.pdf).
Ένα μέρος του βιβλίου έχει δοθεί για φωτοτύπηση.
Το 1ο μάθημα θα γίνει την Πέμπτη, 23 Φεβρουαρίου 2005.

Ημερολόγιο

Δευτέρα

Τρίτη

Τετάρτη

Πέμπτη

Παρασκευή

20/2

21/2

22/2

23/2

Εισαγωγή, Ζητήματα Σχεδιασμού, Μοντέλα Κατανεμημένου Υπολογισμού

Μελέτη Υλικού που σας μοιράστηκε στο μάθημα & Διαφανειών Μαθήματος

24/2

27/2

28/2

1/3

2/3

Αργία

3/3

6/3

7/3

8/3

9/3

Syllabus & Ιntroduction. Μελέτη κεφαλαίου 1, Attiya & Welch

Basic Algorithms in Message Passing Systems. Μελέτη κεφαλαίου 2, Attiya & Welch

10/3

13/3

14/3

15/3

16/3

Leader Election in Rings. Μελέτη Ενοτήτων 3.1, 3.2, 3.3.1 και 3.3.2, Attiya & Welch

17/3

20/3

21/3

22/3

1st Homework out

23/3

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

24/3

27/3

28/3

Mutual Exclusion. Μελέτη Ενοτήτων 4.4.1, 4.4.2, 4.4.3 και 4.4.5, Attiya & Welch

29/3

30/3

Mutual Exclusion. Μελέτη Ενοτήτων 4.4.4 και 4.3.3, Attiya & Welch. Μελέτη Ενότητας 10.8, Nancy Lynch (φωτοτυπίες της ενότητας έχουν δοθεί για φωτοτύπηση).

31/3

3/4

4/4

5/4

Part of 1st Homework due

Παράταση ως 7/4

6/4

7/4

10/4

11/4

Consensus. Μελέτη διαφανειών. Μελέτη Ενοτήτων 5.1.1-5.13 και 5.2.1, 5.2.2, 5.2.4, Attiya & Welch.

12/4

13/4

Consensus. Μελέτη διαφανειών. Μελέτη Ενοτήτων 5.1.1-5.13 και 5.2.1, 5.2.2, 5.2.4, Attiya & Welch.

Project out

14/4

Διακοπές Πάσχα

1/5

2/5

Consensus. Μελέτη διαφανειών.

1st Homework due

3/5

4/5

Consensus. Μελέτη διαφανειών.

5/5

8/5

9/5

Snapshots

10/5

11/5

Snapshots

12/5

15/5

16/5

Causality and Time. Μελέτη Ενοτήτων 6.1.1, 6.1.2, 6.1.3

17/5

18/5

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.

19/5

Project due

22/5

23/5

24/5

25/5

Project due

Εξέταση Project

26/5

29/5

30/5

31/5

1/6

Εξέταση Project

2/6

Περιγραφή Project

Κάθε project περιλαμβάνει την κατανόηση κάποιων papers (ή μέρος κάποιου κεφαλαίου βιβλίου), την παρουσίαση των αποτελεσμάτων που περιγράφονται σε αυτά και τη συγγραφή ενός παραδοτέου. Για τα projects επιτρέπονται ομάδες των δύο ατόμων.

Διαφάνειες Διαλέξεων & Άλλο Υλικό

Περιγραφή Project (project-description.doc).

Οι διαφάνειες των διαλέξεων για το πρόβλημα του χρονισμού είναι διαθέσιμες (causality.pdf).

Οι διαφάνειες των διαλέξεων για το πρόβλημα της ομοφωνίας είναι διαθέσιμες (consensus.pdf).
2o μέρος Σειράς Ασκήσεων (ds2006-hw-part2.doc).
1o μέρος της Σειράς Ασκήσεων (ds2006-hw1.doc).
Οι διαφάνειες των μέχρι τώρα διαλέξεων είναι διαθέσιμες (lecture1-2.pdf και mutual-exclusion.pdf).
Γενικές Πληροφορίες για το μάθημα (distributed-systems-2005.doc)

Σχετική βιβλιογραφία

Other Books on Distributed Systems

§ S. Mullender, Distributed Systems, ACM Press, 1993.

§ G. Coulouris, J. Dollimore and T. Kindberg, “Distributed Systems, Concepts and Design”, Addison-Wesley, 1994.

§ A. Tanenbaum and M. van Steen, Distributed Systems: Principles and Paradigms, Prentice Hall, Inc., 2002.

§ M. Raynal, Algorithms for Mutual Exclusion, MIT Press, 1986.

§ M. Raynal, Networks and Distributed Computation: Concepts, Tools and Algorithms, MIT Press, 1988.

§ S. Dolev, Self-Stabilization, MIT Press, 2000.

§ Α. Tanenbaum, Computer Networks, Prentice-Hall, Inc., 1996.

§ G. Tell, Introduction to Distributed Algorithms, Cambridge University Press, 1994.

Journals

§ Journal of the ACM

§ SIAM Journal on Computing

§ Distributed Computing

§ Information and Computation

§ IEEE Transactions on Parallel and Distributed Systems

§ Parallel and Distributed Computing Practices

§ Parallel Computing

§ Journal of Parallel and Distributed Computing

§ Distributed and Parallel Databases

§ International Journal of High Speed Computing Networks

§ International Journal of Parallel and Distributed Systems and

§ Parallel Algorithms and Applications

§ Concurrency: Practice and Experience

Proceedings publishing distributed computing papers

§ 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

Τελευταία τροποποίηση:6/4/06
Κατασκευή και συντήρηση σελίδων: Παναγιώτα Φατούρου