2009-2010:Κατανεμημένα Συστήματα Ι:Υλικό Διαλέξεων

Από DistrSys

Πίνακας περιεχομένων 1 1η διάλεξη (Δευτέρα, 28 Σεπτεμβρίου 2009) 2 2η διάλεξη (Δευτέρα, 12 Οκτωβρίου 2009) 3 3η διάλεξη (Δευτέρα, 19 Οκτωβρίου 2009) 4 4η διάλεξη (Δευτέρα, 26 Οκτωβρίου 2009) 5 5η διάλεξη (Δευτέρα, 2 Νοεμβρίου 2009) 6 6η διάλεξη (Δευτέρα, 9 Νοεμβρίου 2009) 7 7η διάλεξη (Δευτέρα, 15 Νοεμβρίου 2009) 8 8η διάλεξη (Δευτέρα, 23 Νοεμβρίου 2009) 9 9η διάλεξη (Δευτέρα, 14 Δεκεμβρίου 2009) 10 10η διάλεξη (Παρασκευή, 18 Δεκεμβρίου 2009) 11 11η διάλεξη (Δευτέρα, 21 Δεκεμβρίου 2009)

1^η διάλεξη (Δευτέρα, 28 Σεπτεμβρίου 2009)

Ύλη:

• Εισαγωγή στα Κατανεμημένα Συστήματα

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Εισαγωγή απο τις σημειώσεις του μαθήματος

• Πανεπιστημιακές Σημειώσεις "Λειτουργικά Συστήματα" (Π.Τριανταφύλλου):
  • Κεφάλαιο 7: Εισαγωγή σε Κατανεμημένα Συστήματα

• Βιβλίο "Κατανεμημένα Συστήματα με Java" (Ι.Κ.Κάβουρας, Ι.Ζ.Μήλης, Γ.Β.Ξυλωμένος, Α.Α.Ρουκουνάκη), ISBN 9602098295
  • Κεφάλαιο 1: Εισαγωγή

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 1: Introduction

• Βιβλίο "Distributed Computing Fundamentals, Simulations, and Advanced Topics" (H.Attiya, J.Welch), ISBN 0471453242:
  • Chapter 1: Introduction

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 1: Introduction: Distributed Systems

• Βιβλίο "Distributed Systems, Concepts and Design" (G.Coulouris, J.Dollimore, T.Kindberg), ISBN 0201619180:
  • Chapter 1: Characterization of Distributed Systems

• Βιβλίο "Distributed Systems: Principles and Paradigms" (A.Tanenbaum, M.Steen), ISBN 0130888931:
  • Chapter 1: Introduction

Υλικό στο διαδίκτυο:

• Introduction to Distributed Computing @ Google
• Introduction to Distributed System Design @ Google Code University
• Wikipedia:Distributed Computing
• A primer on distributed computing
• Wikipedia:Dining philosophers problem

---

2^η διάλεξη (Δευτέρα, 12 Οκτωβρίου 2009)

Ύλη:

• Μοντέλο Σύγχρονων Συστημάτων
• Εκλογή Αρχηγού

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Μοντέλο Σύγχρονων Συστημάτων απο τις σημειώσεις του μαθήματος
• Εκλογή Αρχηγού σε Σύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος

• Βιβλίο "Κατανεμημένα Συστήματα με Java" (Ι.Κ.Κάβουρας, Ι.Ζ.Μήλης, Γ.Β.Ξυλωμένος, Α.Α.Ρουκουνάκη), ISBN 9602098295
  • Κεφάλαιο 6: Εκλογή Αρχηγού

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 2: Modelling I: Synchronous Network Model
  • Chapter 3: Leader Election in a Synchronous Ring
  • Chapter 4: Algorithms in General Synchronous Networks
    • 4.1: Leader Election in General Network

• Βιβλίο "Distributed Computing Fundamentals, Simulations, and Advanced Topics" (H.Attiya, J.Welch), ISBN 0471453242:
  • Chapter 2: Basic Algorithms in Message Passing Systems
    • 2.1: Formal Model for Message Passing Systems
  • Chapter 3: Leader Election in Rings
    • 3.1: The Leader Election Problem
    • 3.4: Synchronous Rings

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 2: The Model
    • 2.1: Transition Systems and Algorithms
      • 2.1.1: Transision System
      • 2.1.3: Systems with Synchronous Message Passing
    • 2.4: Additional Assumptions, Complexity
  • Chapter 7: Election Algorithms
    • 7.1: Introduction
    • 7.2: Ring Networks

• Βιβλίο "Distributed Systems, Concepts and Design" (G.Coulouris, J.Dollimore, T.Kindberg), ISBN 0201619180:
  • Chapter 2: System Models
  • Chapter 11: Coordination and Agreement
    • 11.3: Elections

• Βιβλίο "Distributed Systems: Principles and Paradigms" (A.Tanenbaum, M.Steen), ISBN 0130888931:
  • Chapter 5: Synchronization
    • 5.4: Election Algorithms

---

3^η διάλεξη (Δευτέρα, 19 Οκτωβρίου 2009)

Ύλη:

• Εκλογή Αρχηγού
• Αναζήτηση κατά Εύρος
• Συντομότερα Μονοπάτια

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Εκλογή Αρχηγού σε Σύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος
• Κατανεμημένες Δομές σε Σύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 3: Leader Election in a Synchronous Ring
  • Chapter 4: Algorithms in General Synchronous Networks

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 6: Wave and Traversal Algorithms
  • Chapter 7: Election Algorithms

• Βιβλίο "Distributed Computing Fundamentals, Simulations, and Advanced Topics" (H.Attiya, J.Welch), ISBN 0471453242:
  • Chapter 2: Basic Algorithms in Message Passing Systems
  • Chapter 3: Leader Election in Rings

• Βιβλίο "Distributed Systems, Concepts and Design" (G.Coulouris, J.Dollimore, T.Kindberg), ISBN 0201619180:
  • Chapter 11: Coordination and Agreement

---

4^η διάλεξη (Δευτέρα, 26 Οκτωβρίου 2009)

Ύλη:

• Συναίνεση Υπό Την Παρουσία Σφαλμάτων
• Σφάλματα Επικοινωνίας
• Σφάλματα Τερματισμού
  • Αλγόριθμοι Επικύρωσης

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Συναίνεση Υπό Την Παρουσία Σφαλμάτων σε Σύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος

• Βιβλίο "Κατανεμημένα Συστήματα με Java" (Ι.Κ.Κάβουρας, Ι.Ζ.Μήλης, Γ.Β.Ξυλωμένος, Α.Α.Ρουκουνάκη), ISBN 9602098295
  • Κεφάλαιο 19: Ανοχή Βλαβών

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 5: Distributed Consensus with Link Failures
  • Chapter 6: Distributed Consensus with Process Failures

• Βιβλίο "Distributed Computing Fundamentals, Simulations, and Advanced Topics" (H.Attiya, J.Welch), ISBN 0471453242:
  • Chapter 5: Fault-Tolerant Consensus

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 13: Fault Tolerance in Distributed Systems

• Βιβλίο "Distributed Systems, Concepts and Design" (G.Coulouris, J.Dollimore, T.Kindberg), ISBN 0201619180:
  • Chapter 13: Distributed Transactions

• Βιβλίο "Distributed Systems: Principles and Paradigms" (A.Tanenbaum, M.Steen), ISBN 0130888931:
  • Chapter 7: Fault Tolerance

---

5^η διάλεξη (Δευτέρα, 2 Νοεμβρίου 2009)

Ύλη:

• Βυζαντινά Σφάλματα
• Μοντέλο Ασύγχρονων Συστημάτων
  • Εκλογή Αρχηγού
  • Κατασκευή Επικαλυπτικών Δέντρων
  • Αναζήτηση κατά Εύρος

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Μοντέλο Ασύγχρονων Συστημάτων απο τις σημειώσεις του μαθήματος
• Βασικοί Αλγόριθμοι Ασύγχρονων Συστημάτων απο τις σημειώσεις του μαθήματος

• Βιβλίο "Κατανεμημένα Συστήματα με Java" (Ι.Κ.Κάβουρας, Ι.Ζ.Μήλης, Γ.Β.Ξυλωμένος, Α.Α.Ρουκουνάκη), ISBN 9602098295
  • Κεφάλαιο 6: Εκλογή Αρχηγού

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 8: Modelling II: Asynchronous System Model
    • 8.1: I/O Automata
    • 8.2: Operations on Automata
  • Chapter 14: Modelling IV: Asynchronous Network Model
  • Chapter 15: Basic Asynchronous Network Algorithms

• Βιβλίο "Distributed Computing Fundamentals, Simulations, and Advanced Topics" (H.Attiya, J.Welch), ISBN 0471453242:
  • Chapter 2: Basic Algorithms in Message Passing Systems
  • Chapter 3: Leader Election in Rings

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 2: The Model
  • Chapter 6: Wave and Traversal Algorithms
  • Chapter 7: Election Algorithms

• Βιβλίο "Distributed Systems, Concepts and Design" (G.Coulouris, J.Dollimore, T.Kindberg), ISBN 0201619180:
  • Chapter 2: System Models
  • Chapter 11: Coordination and Agreement

• Βιβλίο "Distributed Systems: Principles and Paradigms" (A.Tanenbaum, M.Steen), ISBN 0130888931:
  • Chapter 5: Synchronization
    • 5.4: Election Algorithms

Υλικό στο διαδίκτυο:

• I/O Automata
• Wikipedia:Automata theory
• Visual Automata Simulator

---

6^η διάλεξη (Δευτέρα, 9 Νοεμβρίου 2009)

Ύλη:

• Διάταξη Γεγονότων και Λογικός Χρόνος
• Αμοιβαίος Αποκλεισμός

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Διάταξη Γεγονότων και Λογικός Χρόνος απο τις σημειώσεις του μαθήματος
• Αμοιβαίος Αποκλεισμός σε Ασύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος

• Πανεπιστημιακές Σημειώσεις "Λειτουργικά Συστήματα" (Π.Τριανταφύλλου):
  • Κεφάλαιο 11: Συντονισμός Γεγονότων σε Κατανεμημένα Συστήματα

• Βιβλίο "Κατανεμημένα Συστήματα με Java" (Ι.Κ.Κάβουρας, Ι.Ζ.Μήλης, Γ.Β.Ξυλωμένος, Α.Α.Ρουκουνάκη), ISBN 9602098295
  • Κεφάλαιο 2: Διάταξη γεγονότων
  • Κεφάλαιο 3: Αμοιβαίος αποκλεισμός

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 18: Logical Time

• Βιβλίο "Distributed Computing Fundamentals, Simulations, and Advanced Topics" (H.Attiya, J.Welch), ISBN 0471453242:
  • Chapter 6: Causality and Time
    • 6.1 Capturing Causality

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 2: The Model
    • 2.3 Synchronizer Algorithms

• Βιβλίο "Distributed Systems, Concepts and Design" (G.Coulouris, J.Dollimore, T.Kindberg), ISBN 0201619180:
  • Chapter 10: Time and Global States
    • 10.4 Logical time and logical clocks
  • Chapter 11: Coordination and Agreement
    • 11.2 Mutual Exclusion

• Βιβλίο "Distributed Systems: Principles and Paradigms" (A.Tanenbaum, M.Steen), ISBN 0130888931:
  • Chapter 5: Synchronization
    • 5.2 Logical Clocks

Υλικό στο διαδίκτυο:

• Λειτουργικά Συστήματα ΙΙ - Μάθημα Επιλογής Eαρινού Εξαμήνου
  • Παρουσίαση 5^ου Κεφάλαιου (Π.Τριανταφύλλου)
• Wikipedia:Logical clock
• Wikipedia:Mutual exclusion

---

7^η διάλεξη (Δευτέρα, 15 Νοεμβρίου 2009)

Ύλη:

• Καθολικές Καταστάσεις
• Ολικά Συνεπή Στιγμιότυπα

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Καθολικές Καταστάσεις απο τις σημειώσεις του μαθήματος

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 19: Global Snapshots and Stable Properties

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 10: Snapshots

• Βιβλίο "Κατανεμημένα Συστήματα με Java" (Ι.Κ.Κάβουρας, Ι.Ζ.Μήλης, Γ.Β.Ξυλωμένος, Α.Α.Ρουκουνάκη), ISBN 9602098295
  • Κεφάλαιο 4: Καθολικές καταστάσεις

Υλικό στο διαδίκτυο:

• wikipedia:Snapshot algorithm

---

8^η διάλεξη (Δευτέρα, 23 Νοεμβρίου 2009)

Ύλη:

• Σφάλματα σε Ασύγχρονα Συστήματα
  • Αδυναμία Εύρεσης Λύσης
• Ανιχνευτές Σφαλμάτων

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson: Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM (JACM), Volume 32(2), 374 - 382, 1985.

• Tushar Deepak Chandra and Sam Toueg: Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM (JACM), Volume 43(2), 225 - 267, 1996.

• Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg: The weakest failure detector for solving consensus. In Proc. 11th annual ACM symposium on Principles of distributed computing (PODC), pp. 147 - 158, 1992.

• Marcos Kawazoe Aguilera, Wei Chen, and Sam Toueg: [ On Quiescent Reliable Communication]. SIAM Journal on Computing, Volume 29(6), 2040 - 2073, 2000.

• Michel Raynal: A Short Introduction to Failure Detectors for Asynchronous Distributed Systems. ACM SIGACT News, Volume 36(1), 53 - 70, 2005.

• Felix C. Gartner: A Gentle Introduction to Failure Detectors and Related Subjects.

---

9^η διάλεξη (Δευτέρα, 14 Δεκεμβρίου 2009)

Ύλη:

• Σταθεροποίηση / Αυτο-σταθεροποίηση
  • Τεχνική Power-Supply
  • Αμοιβαίος Αποκλεισμός
  • Αναζήτηση κατά Εύρος
  • Εκλογή Αρχηγού

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Αυτο-σταθεροποίηση απο τις σημειώσεις του μαθήματος

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 13: Fault Tolerance in Distributed Systems
  • Chapter 17: Stabilization

---

10^η διάλεξη (Παρασκευή, 18 Δεκεμβρίου 2009)

Ύλη:

• Συγχρονισμός
• Συγχρονισμός Ρολογιών

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Βασικοί Αλγόριθμοι σε Ασύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος
• Συγχρονισμός στα Ασύγχρονα Συστήματα απο τις σημειώσεις του μαθήματος

• Βιβλίο "Κατανεμημένα Συστήματα με Java" (Ι.Κ.Κάβουρας, Ι.Ζ.Μήλης, Γ.Β.Ξυλωμένος, Α.Α.Ρουκουνάκη), ISBN 9602098295
  • Κεφάλαιο 2: Διάταξη γεγονότων
    • 2.1 Εισαγωγή
    • 2.2 Συγχρονισμός φυσικών ρολογιών

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 16: Synchronizers

• Βιβλίο "Distributed Computing Fundamentals, Simulations, and Advanced Topics" (H.Attiya, J.Welch), ISBN 0471453242:
  • Chapter 11: Simulating Synchrony

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 12: Synchrony in Networks
    • 12.3 Synchronizer Algorithms
    • 12.4 Application: Breadth-first Search
  • Chapter 15: Fault Tolerance in Synchronous Systems
    • 15.3 Clock Synchronization

• Βιβλίο "Distributed Systems, Concepts and Design" (G.Coulouris, J.Dollimore, T.Kindberg), ISBN 0201619180:
  • Chapter 10: Time and Global States
    • 10.1 Introduction
    • 10.2 Clocks, events and process states
    • 10.3 Synchronizing physical clocks

• Βιβλίο "Distributed Systems: Principles and Paradigms" (A.Tanenbaum, M.Steen), ISBN 0130888931:
  • Chapter 5: Synchronization
    • 5.1: Clock Synchronization

Υλικό στο διαδίκτυο:

• Wikipedia:Synchronizer (algorithm)
• Wikipedia:Clock synchronization
• Wikipedia:Global Positioning System
• Wikipedia:Radio Clock
• RFC 958 - Network Time Protocol (NTP)
• Baruch Awerbuch, "Complexity of Network Synchronization", 1985

---

11^η διάλεξη (Δευτέρα, 21 Δεκεμβρίου 2009)

Ύλη:

• Αποτίμηση Καθολικού Κατηγορήματος
• Ανίχνευση Τερματισμού

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή PDF

Σχετικό υλικό:

• Καθολικές Καταστάσεις απο τις σημειώσεις του μαθήματος

• Βιβλίο "Distributed Algorithms" (N.Lynch), ISBN 1558603484:
  • Chapter 19: Global Snapshots and Stable Properties

• Βιβλίο "Introduction to Distributed Algorithms" (G.Tel), ISBN 0521794838:
  • Chapter 10: Snapshots

• Βιβλίο "Κατανεμημένα Συστήματα με Java" (Ι.Κ.Κάβουρας, Ι.Ζ.Μήλης, Γ.Β.Ξυλωμένος, Α.Α.Ρουκουνάκη), ISBN 9602098295
  • Κεφάλαιο 5: Αποτίμηση καθολικού κατηγορήματος