Τμήμα Πληροφορικής, Χειμερινό Εξάμηνο Ακ. Έτους 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       Nancy A. Lynch, "Distributed Algorithms", Morgan Kaufmann Publishers, Inc., 1996.

q       Sape Mullender, Distributed Systems, Addison-Wesley, 1993.

q       Andrew S. Tanenbaum and Maarten van Steen, " Distributed Systems: Principles and Paradigms", Prentice Hall, Inc., 2002.    

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», των «Δομών Δεδομένων» και των «Λειτουργικών Συστημάτων». Επίσης, η γνώση «Βάσεων Δεδομένων», «Δικτύων Υπολογιστών» και «Σχεδίασης και Ανάλυσης Αλγορίθμων» θα βοηθούσε επίσης. Καλή γνώση της Αγγλικής γλώσσας θα διευκολύνει ουσιαστικά την επιτυχή διεκπεραίωση του μαθήματος.

 

Άλλη σχετική βιβλιογραφία

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.

§         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 είναι υποχρεωτικό. Δείτε Διάφανειες Διαλέξεων και Άλλο Υλικό για περισσότερες πληροφορίες.

  Οι σειρές ασκήσεων σας έχουν διορθωθεί. Μπορείτε να περάσετε από το γραφείο μου να τις πάρετε.


Ημερολόγιο

Δευτέρα Τρίτη Τετάρτη Πέμπτη Παρασκευή
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

 

   


Project

Προθεσμία Παράδοσης
Μέρος Α: 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)


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