Τμήμα Πληροφορικής, Εαρινό Εξάμηνο 2004
Κατανεμημένος Υπολογισμός
Μεταπτυχιακό μάθημα
Γενικά | Ανακοινώσεις | Ημερολόγιο | Διαφάνειες Διαλέξεων & Άλλο Υλικό | Project | Βιβλιογραφία
Τελική Εξέταση & Άλλα
Η τελική εξέταση του μαθήματος θα πραγματοποιηθεί την Παρασκευή 25/6/04, ώρα 10:00-13:00 στην αίθουσα Α2.
Η ύλη που θα εξεταστεί είναι η ακόλουθη:
Όλα τα lower bounds και impossibility results που έχουν διδαχθεί στο μάθημα
Η ύλη από τα papers που έχει διδαχθεί στο μάθημα.
Η παράδοση του project του μαθήματος είναι την Τρίτη 29/6/2004 και η παρουσίασή του είναι την Τετάρτη 30/6/2004.
Πρόοδος Μαθήματος
Η πρόοδος του μαθήματος θα πραγματοποιηθεί την Πέμπτη 27/5/04, ώρα 11:00-14:00 στην αίθουσα Α2.
Η ύλη που θα εξεταστεί είναι η ακόλουθη:
Attiya & Welch: Κεφάλαιο 1: όλο, Κεφάλαιο 2: όλο, Κεφάλαιο 3: Ενότητες 3.1, 3.2, 3.3.1, 3.3.2, 3.4.1, Κεφάλαιο 4: όλο, Κεφάλαιο 5: Ενότητες 5.1 & 5.3
Nancy Lynch: Κεφάλαιο 5: όλο, Κεφάλαιο 6: Ενότητες 6.1, 6.2.1, 6.2.2, 6.7, Κεφάλαιο 12: Ενότητα 12.2 (στη μορφή που έχει δοθεί στη βιβλιοθήκη)
Όλες οι διάφανειες που αναφέρονται στην παραπάνω ύλη.
Μελετήστε και τις ασκήσεις των κεφαλαίων αυτών (όσες περισσότερες προλάβετε), καθώς και τις ασκήσεις της πρώτης σειράς ασκήσεων σας.
Διδάσκουσα:
Παναγιώτα Φατούρου
Γραφείο:
26 (Α’ ορόφου)
Ώρες Γραφείου:
Δευτέρα: 19:00 – 20:00, Πέμπτη: 15:00-17:00
Ηλεκτρονική Διεύθυνση: faturu@cs.uoi.gr
Τηλέφωνο:
(26510) 98808
Ηλεκτρονική Διεύθυνση Μαθήματος:
dcgrad@cs.uoi.gr
Ηλεκτρονική Διεύθυνση Λίστας Μαθήματος:
dcgradlist@cs.uoi.gr
Πέμπτη 11:00-14: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 |
2η
εβδομάδα |
Basic Algorithms in Message Passing Systems |
3η
εβδομάδα |
Leader Election in Rings |
4η
εβδομάδα |
Mutual Exclusion in Shared Memory |
5η
εβδομάδα |
Mutual Exclusion in Shared Memory |
6η
εβδομάδα |
Distributed Consensus with link failures |
7η
εβδομάδα |
Fault-Tolerant Consensus |
8η
εβδομάδα |
Fault-Tolerant Consensus |
9η
εβδομάδα |
Atomic Objects |
10η
εβδομάδα |
Snapshot Objects |
11η
εβδομάδα |
Counting Networks |
12η εβδομάδα |
Other Related Topics |
13η Εβδομάδα | Other Related Topics |
|
Κατά τη διάρκεια του
εξαμήνου θα δοθούν 3 σετ ασκήσεων και 1
μεγάλη εργασία. Κάθε σετ ασκήσεων θα
περιέχει ένα σύνολο από θεωρητικές
ασκήσεις. Η εργασία εμπεριέχει τη μελέτη
σειράς ερευνητικών εργασιών, την επέκταση ή
την απλοποίηση ή τον συνδυασμό των
αποτελεσμάτων που περιγράφονται σε αυτές,
τη συγγραφή σχετικού παραδοτέου και μια
ενδεχόμενη παρουσίαση όσων μελετήθηκαν σε mini-course που θα πραγματοποιηθεί στο τέλος του
εξαμήνου. Περισσότερες πληροφορίες για την
εργασία θα συμπεριληφθούν σύντομα στη web σελίδα του μαθήματος.
Τα σετ ασκήσεων και οι
εργασίες θα πρέπει να επιστρέφεται πριν από
την αναγραφόμενη ημερομηνία και ώρα.
Καθυστερημένες ασκήσεις ή εργασίες χωρίς
προηγούμενη συνεννόηση με τη διδάσκουσα
δεν θα γίνονται δεκτές.
Οι λύσεις των ασκήσεων,
καθώς και η εργασία που θα παρουσιάσετε
πρέπει να είναι αποτέλεσμα προσωπικής σας
δουλειάς. Οι αντιγραφές απαγορεύονται και
θα τιμωρούνται αυστηρά. Είναι καλύτερα να
παραδώσετε μια ημιτελή άσκηση παρά μια
παραλλαγμένη αντιγραφή.
Η τελική εξέταση είναι με
ανοιχτές σημειώσεις. Στα συγγράμματα που θα
έχετε μαζί σας θα πρέπει να αναγράφεται το
όνομά σας με ανεξίτηλο τρόπο.
Ο τελικός βαθμός θα
εξαρτηθεί τόσο από τη βαθμολογία των
ασκήσεων και της εργασίας, όσο και από την
επίδοση των φοιτητών στην τελική εξέταση,
ως εξής:
Σειρές Ασκήσεων:
5%
Πρόοδος: 15%
Εργασία: 50%
Τελική Εξέταση: 30%
Προκειμένου να περάσετε με
επιτυχία το μάθημα θα πρέπει να πάρετε
βαθμό τουλάχιστον 5.0/10.0 στην εργασία σας και
να γράψετε τουλάχιστον 4.0/10.0 στην τελική
εξέταση.
Η παρακολούθηση στις
διαλέξεις είναι υποχρεωτική.
Για το μάθημα θα υπάρχει e-mailing λίστα (dcgradlist@cs.uoi.gr) η οποία θα
χρησιμοποιείται για την αποστολή e-mail σε όλους τους φοιτητές που
έχουν δηλώσει το μάθημα. Οι φοιτητές
υποχρεούνται να εγγραφούν στη λίστα. Η
λίστα λειτουργεί ήδη και οι φοιτητές θα
πρέπει να εγγραφούν το αργότερο μέχρι τη
Δευτέρα, 15/3/04. Για να εγγραφείτε στη λίστα αρκεί να
στείλετε ένα ηλεκτρονικό μήνυμα (e-mail)
στη διεύθυνση
με κενό
θέμα και σώμα:
subscribe
dcgradlist
Για το μάθημα υπάρχει
επίσης λογαριασμός με e-mail address: dcgrad@cs.uoi.gr. Μπορείτε να στέλνετε e-mails με απορίες τόσο στον λογαριασμό του
μαθήματος όσο και στη λίστα (κάνετε cc τα e-mail σας προς το λογαριασμό στο faturu@cs.uoi.gr).
Καλή γνώση της Αγγλικής
γλώσσας θα διευκολύνει ουσιαστικά την
επιτυχή διεκπεραίωση του μαθήματος.
H πρόοδος του μαθήματος θα πραγματοποιηθεί την Πέμπτη 27/5/2004. Η ύλη που θα εξεταστεί είναι η ακόλουθη:
Attiya & Welch: Κεφάλαιο 1: όλο, Κεφάλαιο 2: όλο, Κεφάλαιο 3: Ενότητες 3.1, 3.2, 3.3.1, 3.3.2, 3.4.1, Κεφάλαιο 4: όλο, Κεφάλαιο 5: Ενότητες 5.1 & 5.3
Nancy Lynch: Κεφάλαιο 5: όλο, Κεφάλαιο 6: Ενότητες 6.1, 6.2.1, 6.2.2, 6.7, Κεφάλαιο 12: Ενότητα 12.2 (στη μορφή που έχει δοθεί στη βιβλιοθήκη)
Όλες οι διάφανειες που αναφέρονται στην παραπάνω ύλη.
Μελετήστε και τις ασκήσεις των κεφαλαίων αυτών (όσες περισσότερες προλάβετε), καθώς και τις ασκήσεις της πρώτης σειράς ασκήσεων σας.
Δευτέρα | Τρίτη | Τετάρτη | Πέμπτη | Παρασκευή |
1/3
|
2/3
|
3/3
|
4/3
Syllabus & Ιntroduction. Μελέτη κεφαλαίου 1, Attiya & Welch |
5/3
|
8/3
|
9/3 | 10/3
|
11/3
Basic Algorithms in Message Passing Systems. Μελέτη κεφαλαίου 2, Attiya & Welch
|
12/3
|
15/3
|
16/3
|
17/3
|
18/3 Leader Election in Rings. Μελέτη Ενοτήτων 3.1, 3.2, 3.3.1, 3.3.2 και 3.4.1, Attiya & Welch 1η Άσκηση out |
19/3
|
22/3
|
23/3
Αναπλήρωση μαθήματος Πέμπτης 25/3 Mutual Exclusion in Shared Memory. Μελέτη Ενοτήτων 4.1, 4.2, 4.3 και 4.4.1, Attiya & Welch |
24/3
|
25/3
|
26/3
|
29/3
1η Άσκηση due |
30/3
|
31/3
|
1/4
Mutual Exclusion in Shared Memory. Μελέτη Ενότητας 4.4, Attiya & Welch |
2/4
|
5/4
Αρχή Διακοπών Πάσχα |
6/4
xxxx |
7/4
xxxx |
8/4
xxxx |
9/4
xxxx |
12/4
xxxx |
13/4
xxxx |
14/4
xxxx |
15/4
xxxx |
16/4
xxxx |
19/4
|
20/4
|
21/4
|
22/4
Distributed Consensus with Link Failures. Μελέτη Ενότητας 5.1, Nancy Lynch |
23/4
|
26/4
|
27/4
|
28/4
|
29/4
Distributed Consensus with Process Failures. Μελέτη Ενοτήτων 6.1, 6.2.1, 6.2.2, 6.7, Nancy Lynch & Μελέτη Ενοτήτας 5.1, Attiya & Welch |
30/4
|
3/5
|
4/5
|
5/5
|
6/5
Fault-Tolerant Consensus. Μελέτη Ενότητας 5.3, Attiya & Welch & Μελέτη Ενότητας 12.2, Nancy Lynch (φωτοτυπίες που έχουν δοθεί στη βιβλιοθήκη) |
7/5
|
10/5
|
11/5
|
12/5
|
13/5
Thread Scheduling. Μελέτη Ενοτήτων 1, 2, 3, 4.14.2 και 4.3, από την εργασία: Arora, Blumofe & Plaxton, "Thread Scheduling for Multiprogrammed Multiprocessors", SPAA 1998. |
14/5
|
17/5
|
18/5
Counting Networks. Μελέτη Ενοτήτων 1,2,3,5 και 6 από την εργασία Aspnes, Herlihy & Shavit, "Counting Networks", JACM, September 1994. |
19/5
|
20/5
Απουσία Διδάσκουσας |
21/5
|
24/5
|
25/5
|
26/5
|
27/5
Πρόοδος!!!! |
28/5
|
31/5
|
1/6
|
2/6
|
3/6
Atomic Snapshots |
4/6
|
7/6 | 8/6 | 9/6 | 10/6 Flow Control |
11/6 |
Causality & Time |
1η Άσκηση (hw1.ps)
Γενικές Πληροφορίες για το μάθημα
(dcgrad.doc)
Αναθέσεις Εργασιών
Ανδρέας Κακολύρης
a. Nimar S. Arora, Robert D. Blumofe, C. Greg Plaxton, «Thread Scheduling for Multiprogrammed Multiprocessors», ACM Symposium on Parallel Algorithms and Architectures, pp. 119-129, 1998.
b. Guy Blelloch, Phillip Gibbons and Yossi Matias, “Provably Efficient Scheduling for Languages with Fine-Grained Parallelism, Journal of the ACM, Vol. 46, No. 2, March 1999, pp. 281-321.
c. G. Blelloch and P. Gibbons, “Effectively Sharing a Cache”, SPAA 2004, to appear.
Φίλιππος Παπαδόπουλος
a. M. Herlihy, S. Tirthapura and R. Wattenhofer, “Competitive Concurrent Distributed Queueing”, pp. 127-133, ACM PODC, 2001.
b. M. Demmer and M. Herlihy, “The arrow distributed Directory Protocol”, pp.119-133, DISC 1998.
c. M. Herlihy and S. Tirthapura, “Self-Stabilizing Distributed Queueing”, pp. 209-223, DISC 2001.
Κώστας Πουρσαλίδης
?
Κώστας Στεφανίδης
a. Ion Stoica, Robert Morris, David Liben-Nowell, David Karger, M. Frans Kaashoek, Frank Dabek and Hari Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications”, ACM SIGCOM, pp. 149-160, San Diego, California, August 2001.
b. James Aspnes and Gauri Shah, “Skip Graphs", ACM-SIAM Symposium on Discrete Algorithms, January 2003, pp. 384-393.
c. B. Awerbuch and C. Scheideler, “Peer-to-Peer Systems for Prefix Search”, ACM Principles of Distributed Computing, 2003.
Βασίλης Τενέντες
a. Ion Stoica, Robert Morris, David Liben-Nowell, David Karger, M. Frans
Kaashoek, Frank Dabek and Hari Balakrishnan, "Chord: A Scalable Peer-to-Peer
Lookup Protocol for Internet Applications", ACM SIGCOM, pp. 149-160, San Diego,
California, August 2001.
b. David R. Karger and Matthias Ruhl, "Diminished Chord: A Protocol for
Heterogeneous Subgroup Formation in Peer-to-Peer Networks",
International Workshop on Peer-to-Peer Systems (IPTPS '04) San Diego, February
2004, URL: http://iptps04.cs.ucsd.edu/papers/karger-subgroup.pdf
c. Antony Rowston and Peter Druschel, "Pastry: Scalable, decentralized object
location routing for large-scale P2P systems", IFIP/ACM International Conference
on Distributed Systems Platforms (Middleware), pp. 329-350, 2001.
d. Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp and Scott Shenker,
"A Scalable Content Addressable Network", Proceedings of ACM SIGCOMM 2001, URL:
citeseer.ist.psu.edu/ratnasamy01scalable.html
Νίκος Τσάπανος
?
Ανδρέας Φωτίου
a. Ion Stoica, Robert Morris, David Liben-Nowell, David
Karger, M. Frans Kaashoek, Frank Dabek and Hari
Balakrishnan, "Chord: A Scalable Peer-to-Peer Lookup
Protocol for Internet Applications", ACM SIGCOM, pp.
149-160, San Diego, California, August 2001.
b. David Liben-Nowell, Hari Balakrishnan and David Karger, "Analysis
of the Evolution of Peer-to-Peer Systems", pp. 233-242,
Monterey, California, July 2002.
c. Antony Rowston and Peter Druschel, "Pastry: Scalable,
decentralized object location routing for large-scale P2P systems",
IFIP/ACM International Conference on Distributed Systems
Platforms (Middleware), pp. 329-350, 2001.
d. Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp and
Scott Shenker, "A Scalable Content Addressable Network",
Proceedings of ACM SIGCOMM 2001, URL:
citeseer.ist.psu.edu/ratnasamy01scalable.html
----------------------------------------------------------------------------------------------------------------------------
§
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.
Τελευταία
τροποποίηση:
14/5/04
Κατασκευή και
συντήρηση των
σελίδων: Παναγιώτα
Φατούρου