Τμήμα Πληροφορικής, Εαρινό Εξάμηνο Ακ. Έτους 2006-2007
Κατανεμημένος Υπολογισμός
Μεταπτυχιακό μάθημα
Γενικά | Χρονοδιάγραμμα | Ανακοινώσεις | Ημερολόγιο | Ασκήσεις & Άλλο Υλικό | Project | Βιβλιογραφία
Διδάσκουσα:
Παναγιώτα Φατούρου
Γραφείο:
26 (Α’ ορόφου)
Ώρες Γραφείου:
Πέμπτη: 11:00 – 12:00
Ηλεκτρονική Διεύθυνση: faturuATcs.uoi.gr
Τηλέφωνο:
(26510) 98808
Ηλεκτρονική Διεύθυνση Μαθήματος:
dcgradATcs.uoi.gr
Ηλεκτρονική Διεύθυνση Λίστας Μαθήματος:
dcgradlistATcs.uoi.gr
Τρίτη 12:00-15:00, στην αίθουσα Α2.
§ H. Attiya & J. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, Morgan Kaufmann, 1998 (main textbook)
§
N. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996
1η
εβδομάδα |
Introduction - Basic Algorithms in Message Passing Systems |
2η
εβδομάδα |
Leader Election in Rings - Graph Algorithms |
3η
εβδομάδα |
Mutual Exclusion in Shared Memory |
4η
εβδομάδα |
Fault-Tolerant Consensus with Crash Failures |
5η
εβδομάδα |
Atomic Objects & Distributed Data Structures |
6η
εβδομάδα |
Wait-Free Simulations of Arbitrary Objects |
7η
εβδομάδα |
Snapshot Objects |
8η
εβδομάδα |
Counting Networks |
9η
εβδομάδα |
Scheduling Multithreaded computations |
10η
εβδομάδα |
Flow Control |
11η
εβδομάδα |
|
12η εβδομάδα |
|
Κατά τη διάρκεια του
εξαμήνου θα δοθούν κάποια σετ ασκήσεων και 1
εργασία (project). Η εργασία εμπεριέχει τη μελέτη
κάποιων ερευνητικών εργασιών, την επέκταση ή
την απλοποίηση ή τον συνδυασμό των
αποτελεσμάτων που περιγράφονται σε αυτές,
τη συγγραφή
σχετικού παραδοτέου και μια
παρουσίαση όσων μελετήθηκαν σε mini-course που θα πραγματοποιηθεί στο τέλος του
εξαμήνου. Περισσότερες πληροφορίες για την
εργασία θα συμπεριληφθούν σύντομα στη web σελίδα του μαθήματος.
Τα σετ
ασκήσεων και οι εργασίες θα πρέπει να
επιστρέφονται πριν από την αναγραφόμενη
ημερομηνία και ώρα. Καθυστερημένες
ασκήσεις ή εργασίες χωρίς προηγούμενη
συνεννόηση με τη διδάσκουσα δεν θα γίνονται
δεκτές.
Οι λύσεις των ασκήσεων, καθώς και η εργασία που θα παρουσιάσετε πρέπει να είναι αποτέλεσμα προσωπικής σας δουλειάς. Συνεργασίες απαγορεύονται και θα τιμωρούνται αυστηρά.
H τελική εξέταση θα γίνει με ανοιχτές
σημειώσεις.
Ο τελικός
βαθμός θα εξαρτηθεί τόσο από τη βαθμολογία
των ασκήσεων και της εργασίας, όσο και από
την επίδοση των φοιτητών στην τελική
εξέταση, ως εξής:
Σειρά
Ασκήσεων: 25%
Εργασία: 25%
Τελική Εξέταση: 50%
Απαραίτητη προϋπόθεση του μαθήματος είναι ο μέσος όρος των βαθμών των ασκήσεων και της εργασίας να είναι τουλάχιστον 4.0/10.0 και να γράψετε τουλάχιστον 4.0/10.0 στην τελική εξέταση.
Η παρακολούθηση στις
διαλέξεις είναι υποχρεωτική.
Για το μάθημα θα υπάρχει e-mailing λίστα (dcgradlistΑΤcs.uoi.gr, όπου ΑΤ
αντικαθίσταται από @) η οποία θα
χρησιμοποιείται για την αποστολή e-mail σε όλους τους φοιτητές που
έχουν δηλώσει το μάθημα. Οι φοιτητές
υποχρεούνται να εγγραφούν στη λίστα. Η
λίστα λειτουργεί ήδη και οι φοιτητές θα
πρέπει να εγγραφούν το αργότερο μέχρι τη Δευτέρα, 14/5/07. Για να εγγραφείτε στη λίστα αρκεί να
στείλετε ένα ηλεκτρονικό μήνυμα (e-mail)
στη διεύθυνση
με κενό
θέμα και σώμα:
subscribe
dcgradlist
Για το μάθημα υπάρχει
επίσης λογαριασμός με e-mail address: dcgradΑΤcs.uoi.gr. Μπορείτε να στέλνετε e-mails με απορίες τόσο στον λογαριασμό του
μαθήματος όσο και στη λίστα (κάνετε cc τα e-mail σας και στο λογαριασμό faturuΑΤcs.uoi.gr).
Καλή γνώση της Αγγλικής
γλώσσας θα διευκολύνει ουσιαστικά την
επιτυχή διεκπεραίωση του μαθήματος.
To 3ο Σετ Ασκήσεων είναι διαθέσιμο (dc07-hw3.pdf).
Νέο Σετ Διαφανειών "Universality - Consensus Hierarchy" (universality-grads.pdf).
Νέο Σετ Διαφανειών "Πρόβλημα Ομοφωνίας" (consensus-grads.pdf).
3ο Σετ Ασκήσεων (dc07-hw3.pdf).
Νέο Σετ Διαφανειών "Δίκτυα Μέτρησης" (counting-grads.pdf).
Νέο Σετ Διαφανειών "Ατομικοί Καταχωρητές" (atomic-registers-grads.pdf).
Η ανάθεση και η περιγραφή των projects είναι διαθέσιμη (projects-grads.pdf).
To 2ο Σετ Ασκήσεων είναι διαθέσιμο (dc07-hw2.pdf).
Σετ Διαφανειών "Ατομικά Αντικείμενα" (atomic-objects-grads.pdf).
To Σετ Διαφανειών Αμοιβαίου Αποκλεισμού έχει αναρτηθεί (mutual-exclusion-grads.pdf).
To 1o Σετ Ασκήσεων είναι διαθέσιμο (dc07-hw1.pdf).
To 1o Σετ Διαφανειών έχει αναρτηθεί (lectures-grads.pdf).
Όλοι οι φοιτητές θα πρέπει να εγγραφούν στη λίστα μέχρι τη Δευτέρα, 14/5/07.
Γενικές Πληροφορίες για το μάθημα (dcgrad.doc)
Δευτέρα | Τρίτη | Τετάρτη | Πέμπτη | Παρασκευή |
23/4
|
24/4 Εισαγωγή, Μοντέλο, Βασικοί Αλγόριθμοι Γράφων Μελέτη διαφανειών. Μελέτη Κεφαλαίων 1 και 2, Attiya & Welch, Μελέτη κεφαλαίου 1 και 2, Nancy Lynch (έμφαση στο Attiya & Welch) |
25/4
|
26/4
|
27/4
|
30/4
|
1/5
Αργία |
2/5
|
3/5
|
4/5
|
7/5
|
8/5 Εκλογή Αρχηγού σε Δακτύλιο Μελέτη διαφανειών. Μελέτη Κεφαλαίου 3, Attiya & Welch (όχι παράγραφοι 3.3.3 και 3.4.2). Η ύλη αυτή περιγράφεται και στο βιβλίο της Lynch, κεφάλαιο 3 (όχι ενότητες 3.6 και 3.7) και κεφάλαιο 15, ενότητες 15.1 (χωρίς το 15.1.4). Έμφαση στο Attiya & Welch |
9/5
|
10/5
|
11/5
|
14/5
|
15/5
Αλγόριθμοι σε Σύγχρονα Γενικά Δίκτυα Μελέτη διαφανειών. Μελέτη Κεφαλαίου 4, Lynch (όχι Ενότητα 4.5) |
16/5
|
17/5
|
18/5
|
21/5
|
22/5 Αλγόριθμοι σε Σύγχρονα Γενικά Δίκτυα, Αλγόριθμοι σε Γενικά Ασύγχρονα Δίκτυα Μελέτη διαφανειών. Μελέτη Ενοτήτων 15.2, 15.3, 15.4, 15.5.1-15.5.2, Lynch |
23/5
|
24/5
|
25/5
|
28/5
|
29/5
O αλγόριθμος GHS σε ασύγχρονα δίκτυα. Μοντέλο Διαμοιραζόμενης μνήμης, Αμοιβαίος Αποκλεισμός |
30/5
|
31/6
|
1/6 Αναπλήρωση μαθήματος 1/5. Αμοιβαίος Αποκλεισμός. |
4/6
|
5/6 Αμοιβαίος Αποκλεισμός.
|
6/6
|
7/6
|
8/6
|
11/6
|
12/6 Ατομικά Αντικείμενα - Ατομικά Στιγμιότυπα Μνήμης Μελέτη διαφανειών. Μελέτη Ενοτήτων 13.1.1, 13.2, 13.3.1, 13.3.2, Nancy Lynch |
13/6
|
14/6
|
15/6
|
18/6
|
19/6
|
20/6
|
21/6
|
22/6 Δίκτυα Μέτρησης Μελέτη διαφανειών. Μελέτη εργασίας "Counting Networks" by Aspnes, Herlihy, Shavit |
25/6
|
26/6
Μελέτη διαφανειών. Μελέτη ενοτήτων 12.1, 12.2.1, 12.2.2, 12.2.3, 12.2.4, "Distributed Algorithms" by Nancy Lynch |
27/6
|
28/6
|
29/6 Consensus Hierarchy. Μελέτη διαφανειών. Μελέτη Κεφαλαίου15.1
(όχι το Θεώρημα 15.3 και την απόδειξή του),
15.2, 15.3, |
2/7 | 3/7 Επίλυση Ασκήσεων - Συζήτηση Project |
4/7 | 5/7
|
6/7 Επίλυση Ασκήσεων - Συζήτηση Project |
9/7
|
10/7 Παράδοση Αναφοράς Project, στο γραφείο ή στη θυρίδα μου, ώρα 12:00-13:00 |
11/7
|
12/7 Παρουσίαση Project, ώρα 10:00-12:00, στην αίθουσα μεταπτυχιακών μαθημάτων του 2ου ορόφου |
13/7
|
16/7
|
17/7
|
18/7
|
19/7
|
20/7 Εξέταση Μαθήματος, ώρα 10:00-13:00, αίθουσα μεταπτυχιακών μαθημάτων 1ου ορόφου |
Νέο Σετ Διαφανειών "Universality - Consensus Hierarchy" (universality-grads.pdf).
Νέο Σετ Διαφανειών "Πρόβλημα Ομοφωνίας" (consensus-grads.pdf).
3ο Σετ Ασκήσεων (dc07-hw3.pdf).
Νέο Σετ Διαφανειών "Δίκτυα Μέτρησης" (counting-grads.pdf).
Νέο Σετ Διαφανειών "Ατομικοί Καταχωρητές" (atomic-registers-grads.pdf).
Ανάθεση και Περιγραφή των projects (projects-grads.pdf).
2ο Σετ Ασκήσεων (dc07-hw2.pdf).
Σετ Διαφανειών "Ατομικά Αντικείμενα" (atomic-objects-grads.pdf).
Σετ Διαφανειών Αμοιβαίου Αποκλεισμού (mutual-exclusion-grads.pdf).
1o Σετ Ασκήσεων (dc07-hw1.pdf).
1o Σετ Διαφανειών (lectures-grads.pdf).
Γενικές Πληροφορίες για το μάθημα (dcgrad.doc)
Πιθανά Θέματα:
Περισσότερες πληροφορίες για τα projects θα παρεχθούν στο μέλλον.
§
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.
§
G. Coulouris, J. Dollimore and T. Kindberg, Distributed Systems,
Concepts and Designs, 2nd ed. Addison-Wesley Publishing Company,
1994.
§
S. Mullender, Distributed Systems, 2nd
Ed.Addison-Wesley Publishing Company, 1993.
§
Maarten
Van Steen, Andrew
S. Tanenbaum, Distributed
Systems: Principles and Paradigms, Prentice Hall, 2002.
§
M. Raynal, Algorithms for Mutual Exclusion, MIT Press, 1986.
§
M. Raynal, Networks and Distributed Computation: Concepts, Tools and
Algorithms, MIT Press, 1988.
§
Α. Tanenbaum, Distributed Operating Systems,
Prentice-Hall, Inc., 1995.
§
Α. Tanenbaum, Computer Networks,
Prentice-Hall, Inc., 1996.
§
G. Tell, Introduction to Distributed Algorithms, Cambridge
University Press, 1994.
Τελευταία
τροποποίηση:
24/4/07
Κατασκευή και
συντήρηση των
σελίδων: Παναγιώτα
Φατούρου