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

Κατανεμημένος Υπολογισμός

Μεταπτυχιακό μάθημα 

Γενικά | Χρονοδιάγραμμα | Ανακοινώσεις | Ημερολόγιο | Ασκήσεις & Άλλο Υλικό | Project | Βιβλιογραφία

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

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


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

 

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

Τρίτη 16:00-19: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η εβδομάδα

Distributed Consensus with link failures

5η εβδομάδα

Fault-Tolerant Consensus with Crash Failures

6η εβδομάδα

Fault-Tolerant Consensus with Byzantine Failures

7η εβδομάδα

Atomic Objects & Distributed Data Structures

8η εβδομάδα

Wait-Free Simulations of Arbitrary Objects

9η εβδομάδα

Snapshot Objects

10η εβδομάδα

Counting Networks

11η εβδομάδα

Scheduling Multithreaded computations

12η εβδομάδα

Flow Control
13η εβδομάδα

Εξέταση project - mini course

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

Κατά τη διάρκεια του εξαμήνου θα δοθεί 1 σετ ασκήσεων και 1 εργασία (project). Η εργασία εμπεριέχει τη μελέτη σειράς ερευνητικών εργασιών, την επέκταση ή την απλοποίηση ή τον συνδυασμό των αποτελεσμάτων που περιγράφονται σε αυτές, τη συγγραφή σχετικού παραδοτέου και μια παρουσίαση όσων μελετήθηκαν σε mini-course που θα πραγματοποιηθεί στο τέλος του εξαμήνου. Περισσότερες πληροφορίες για την εργασία θα συμπεριληφθούν σύντομα στη web σελίδα του μαθήματος.

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

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

H τελική εξέταση θα γίνει με ανοιχτές σημειώσεις. 

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

Σειρά Ασκήσεων: 10%

Εργασία: 30%

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

Απαραίτητη προϋπόθεση του μαθήματος είναι να πάρετε βαθμό τουλάχιστον 4.0/10.0 στην εργασία σας και να γράψετε τουλάχιστον 4.0/10.0 στην τελική εξέταση. 

 

Χρονοδιάγραμμα

1ο Σετ Ασκήσεων: θα δοθεί 20/3/06 και θα έχει προθεσμία παράδοσης στις 11/4/2006.

Εργασία: Επιλογή εργασίας θα πρέπει να γίνει μέχρι την 14η Απριλίου 2004, Παράδοση εργασίας θα γίνει την  6η Ιουνίου 2006 και τελική εξέταση εργασίας θα γίνει στις 6/6/06 και στις 13/6/06.

 

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

Η παρακολούθηση στις διαλέξεις είναι υποχρεωτική.

 

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

Για το  μάθημα θα υπάρχει e-mailing λίστα (dcgradlistΑΤcs.uoi.gr, όπου ΑΤ αντικαθίσταται από @) η οποία θα χρησιμοποιείται για την αποστολή e-mail σε όλους τους φοιτητές που έχουν δηλώσει το μάθημα. Οι φοιτητές υποχρεούνται να εγγραφούν στη λίστα. Η λίστα λειτουργεί ήδη και οι φοιτητές θα πρέπει να εγγραφούν το αργότερο μέχρι τη Τρίτη, 14/3/06. Για να εγγραφείτε στη λίστα αρκεί να στείλετε ένα ηλεκτρονικό μήνυμα (e-mail) στη διεύθυνση 

majordomoΑΤcs.uoi.gr  (όπου ΑΤ αντικαθίσταται από το @)

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

 subscribe dcgradlist  

 Για το μάθημα υπάρχει επίσης λογαριασμός με e-mail address: dcgradΑΤcs.uoi.gr. Μπορείτε να στέλνετε e-mails με απορίες τόσο στον λογαριασμό του μαθήματος όσο και στη λίστα (κάνετε cc τα e-mail σας και στο λογαριασμό faturuΑΤcs.uoi.gr).

 

Παρατήρηση

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

 

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

  Το ερωτηματολόγιο του μαθήματος είναι διαθέσιμο (questionary.pdf). Παρακαλώ συμπληρώστε το και αφήστε το στη θυρίδα μου.

  Το σετ διαφανειών σε προσομοίωση ατομικών αντικειμένων και καθολικότητα των αντικειμένων ομοφωνίας είναι διαθέσιμο (universality.pdf).

  Το σετ διαφανειών σε ατομικά αντικείμενα και snapshots είναι διαθέσιμο (atomic-objects.pdf).

Ημερολόγιο

Δευτέρα Τρίτη Τετάρτη Πέμπτη Παρασκευή
27/2

 

 

 

28/2

Introduction - Basic Algorithms in Message Passing Systems

Μελέτη διαφανειών και Κεφαλαίων1 & 2, Attiya & Welch

 1/3

 

 

 

 2/3

 

 

 3/3

 

 

 
6/3

 

 

 7/3

Αργία

 

 8/3

 

 

 9/3

 

 

 10/3

 

 
13/3

 

 


 

 14/3

Basic Graph Algorithms - Leader Election

Μελέτη διαφανειών και Κεφαλαίου 3, Attiya & Welch

 15/3

 

 


 

 16/3


 

 

 

 17/3

 

 


 
20/3

 

 

 21/3

Graph Algorithms in Synchronous Message-Passing Systems

Μελέτη διαφανειών και Κεφαλαίου 4, Nancy Lynch

 22/3

 

 

 23/3

 

1ο Σετ out

 24/3

 

 
27/3

 

 

 28/3

Graph Algorithms in Asynchronous Message Passing Systems

Μελέτη διαφανειών και Κεφαλαίων 14 & 15, Nancy Lynch

 

 29/3

 

 

 30/3 31/3

 

 
3/4

 

 

 4/4

Απουσία Διδάσκουσας

 

 5/4

 

 

 6/4

Μέρος 1, Σετ Ασκήσεων due (πριν από ώρα 16:00 στη θυρίδα μου)

Παράταση για το Μέρος 1: 7/4, ίδια ώρα

2ο μέρος Σετ Ασκήσεων out

 7/4

 

 
10/4

 

 

 

 11/4

Mutual Exclusion

Μελέτη διαφανειών, κεφαλαίου 4, Attiya & Welch

 

 

 12/4

 

 

 13/4

Project out

 

 

 14/4

 

 

 

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

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

 

 

 2/5

Mutual Exclusion

Μελέτη διαφανειών και Ενότητας 10.8, Nancy Lynch (έχει δοθεί για φωτοτύπηση)

 3/5

2o  Μέρος Σετ Ασκήσεων due, στη θυρίδα μου

Παράταση δεν μπορεί να δοθεί!!!

 

 4/5

 

 

 5/5

 

6/5

Αναπλήρωση μαθήματος που χάθηκε στις 4/4 λόγω απουσίας διδάσκουσας.

Consensus

Μελέτη διαφανειών και Ενοτήτων 6.1, 6.2.3, 6.3.2, Nancy Lynch & Ενοτήτων 5.1.1, 5.1.2, 5.1.3, 5.2.1 - 5.2.4, 5.3.1, Attiya & Welch (υλικό που έχει δοθεί για φωτοτύπηση)
8/5

 

 

9/5

 

Δίκτυα Μέτρησης

Μελέτη διαφανειών και paper που έχει δοθεί για φωτοτύπηση.

 

 10/5

 

 

 11/5

 

 

 

 12/5

 

 
15/5


 

 16/5


Αναβολή μαθήματος λόγω μεταπτυχιακών εξετάσεων

 17/5


 

 18/5


 

 19/5


 
22/5

 

 

 23/5

κατάληψη

 

 24/5

 

 

 25/5

 

 

 26/5

 

 
29/5

 

 

 30/5

 

κατάληψη

 31/5

 

 

 1/6

 

 

 2/6

 

 
5/6

 

 6/6

κατάληψη

 7/6

 

 8/6

 

 9/6

 
12/6

 

 13/6

κατάληψη

 14/6

 

 15/6

 

 16/6

 
19/6

Ατομικά Αντικείμενα - Ατομικά Στιγμιότυπα Μνήμης

Μελέτη διαφανειών και υλικού που έχει δοθεί για φωτοτύπηση

 20/6 21/6

Καθολικότητα των ατομικών αντικειμένων ομοφωνίας (universality of consensus)

Μελέτη διαφανειών και υλικού που έχει δοθεί για φωτοτύπηση.

 22/6 23/6
 
4 Σεπτεμβρίου: Παράδοση Project

 

Ασκήσεις  & Άλλο Υλικό

  Το σετ διαφανειών σε προσομοίωση ατομικών αντικειμένων και καθολικότητα των αντικειμένων ομοφωνίας είναι διαθέσιμο (universality.pdf).

  Το σετ διαφανειών σε ατομικά αντικείμενα και snapshots είναι διαθέσιμο (atomic-objects.pdf).

Project

Πιθανά Θέματα:

Περισσότερες πληροφορίες για τα projects θα τοποθετούν εδώ στο μέλλον.

Βιβλιογραφία

Journals

§         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

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

Other Books on Distributed Systems

§         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.

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