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

Από DistrSys

Πίνακας περιεχομένων 1 1η διάλεξη (Δευτέρα, 4 Οκτωβρίου 2010) 2 2η διάλεξη (Δευτέρα, 11 Οκτωβρίου 2010) 3 3η διάλεξη (Δευτέρα, 18 Οκτωβρίου 2010) 4 4η διάλεξη (Δευτέρα, 25 Οκτωβρίου 2010) 5 5η διάλεξη (Δευτέρα, 1 Νοεμβρίου 2010) 6 6η διάλεξη (Δευτέρα, 8 Νοεμβρίου 2010) 7 7η διάλεξη (Δευτέρα, 13 Δεκεμβρίου 2010) 8 8η διάλεξη (Δευτέρα, 20 Δεκεμβρίου 2010) 9 9η διάλεξη (Δευτέρα, 20 Δεκεμβρίου 2010) 10 10η διάλεξη (Δευτέρα, 10 Ιανουαρίου 2011) 11 11η διάλεξη (Δευτέρα, 17 Ιανουαρίου 2011)

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

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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

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

• Reimagining Internet, Vinten Cerf (Vice President at Google, Internet Pioneer)
• Participatory Sensing applications as drivers of Internet and social innovation, Deborah Estrin (CENS, UCLA)
• 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^η διάλεξη (Δευτέρα, 11 Οκτωβρίου 2010)

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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: Transmision 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^η διάλεξη (Δευτέρα, 18 Οκτωβρίου 2010)

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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^η διάλεξη (Δευτέρα, 25 Οκτωβρίου 2010)

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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^η διάλεξη (Δευτέρα, 1 Νοεμβρίου 2010)

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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^η διάλεξη (Δευτέρα, 8 Νοεμβρίου 2010)

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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^η διάλεξη (Δευτέρα, 13 Δεκεμβρίου 2010)

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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^η διάλεξη (Δευτέρα, 20 Δεκεμβρίου 2010)

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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: Αποτίμηση καθολικού κατηγορήματος

---

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

Ύλη:

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

Διαφάνειες:

• Διαφάνειες διάλεξης σε μορφή 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

---

10^η διάλεξη (Δευτέρα, 10 Ιανουαρίου 2011)

Ύλη:

• Πρωτόκολλα Πληθυσμών

Διαφάνειες:

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

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

• James Aspnes and Eric Ruppert. An introduction to population protocols. Bulletin of the European Association for Theoretical Computer Science, 93:98-117, October 2007. Columns: Distributed Computing, Editor: M. Mavronicolas.

• Paul Spirakis, Othon Michail and Ioannis Chatzigiannakis: Population Protocols and Related Models. Theoretical Aspects of Distributed Computing in Sensor Networks, Springer-Verlag, ISBN: 978-3-642-14848-4, pp. 109-160, 2011.

• Othon Michail, Ioannis Chatzigiannakis and Paul Spirakis: New Models for Population Protocols. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, Editor: N. Lynch.

---

11^η διάλεξη (Δευτέρα, 17 Ιανουαρίου 2011)

Ύλη:

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

Διαφάνειες:

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

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

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

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