CUGS: Distributed Systems, 3 p - Course Materials

DRTS Research Group

News

080530: Slides for days #5-6 have been updated (including P2P).
080519: Slides for day #4 has been updated.
080513: The exam for 2007 has been added to the history of exams.
080513: The updated programing assignment has been added.
080513: <-- Spring 2008 -->
070514: The Exam for 2005 has been added to the Exams section.
070514: The programming assignment has been updated.
070511: The web page has been updated for 2007.

Previous messages

050617: The 2005 CUGS DS Exam has been distributed to students (June 17-30)
050614: Reading list updated
050614: Presentation slides for days #5 and #6 updated
050429: The source code and assignment document is now up to date.
050427: Presentation slides for day #4 updated
050427: Programming assignment description updated
050427: 2004 exam available
050426: Slides and assignment not yet updatednone

Slides

Part I (Petru Eles)

See Petru's web page for details.

Part II (Sten F Andler)

• Lecture notes (not updated)
• day 4 (3-up) (6-up) Replication, fault tolerance
• day 5 (3-up) (6-up) Distributed transaction processing / database systems / file systems
• day 6 (3-up) (6-up) Intro to DRTS, security, naming
  peer-to-peer (6-up)

Programming Assignment

Downloads

The programming assignment describes how a simple game, based on the classical Byzantine Generals Problem, should be implemented using Java and CORBA.
The source code.

Contact

If there are any questions concerning the assignment. Please, contact Marcus Brohede.

Exam

Previous take-home exams

• 2007 Exam (PDF)
• 2006 Exam (No course given)
• 2005 Exam (PDF)
• 2004 Exam (PDF)
• 2003 Exam (PDF)
• 2002 Exam (PDF)

Course contents

Course responsible

Sten F Andler <sten.f.andler@ida.his.se>
Petru Eles <petel@ida.liu.se>

Content and structure

Where course contents overlap with existing course, we try to focus on the CUGS goal of fundamental computer science: algorithms, data structures, general principles, etc.

Part I - Lecture days #1-3 (Eles)

o Introduction
  - Course content
  - What is a distributed system
  - Design goals, main problems
  - Models of distributed systems.

o Communication in distributed systems
  - Message passing, RMI, RPC
  - Group Communication

o Middleware/CORBA
  (RTES course has section on Real-Time Middleware)

o Time and state in distributed systems
  - Time in distributed systems
  - Logical clocks, Vector clocks
    (RTES course has section on Clock Synchronisation of RT clocks)
  - Causal ordering based on vector clocks
  - Global state and state recording

o Distributed mutual exclusion

o Distributed elections

Part II - Lecture days #4-6 (Andler) (Not updated)

o Introduction revisited
  - Definition of distributed systems
  - Issues in distributed systems
  - On system models

o Replication
  - Replication models
  - Consistency
  - Agreement and order
  - Update protocols

o Fault tolerance in distributed systems
  - Redundancy and voting
  - Byzantine agreement
  - Stabilization

o Distributed transaction processing
  - Distributed commit
  - Distributed concurrency control
  - Distributed recovery

o Distributed database systems (highly available or real-time)
  - Relaxation of ACID properties, weak consistency
  - Non-blocking commit

o Distributed file systems (discussion of goals, architecture, features)

o Distributed real-time systems
  - Dependability concepts
  - Time and order
  - Real-time communication (Quality of Service)

o Other issues
  - Security (encryption, authentication)
  - Naming

Literature

Course literature

Excerpts from:

A. Burns, A Wellings: Real-Time Systems and Programming Languages. 3rd edition. Addison-Wesley, 2001. ISBN 0-201-72988-1

S. Dolev: Self-stabilization. MIT Press, 2000. ISBN 0-262-04178-2

Other readings

Related courses

        LiU: TDDB 37 DISTRIBUTED SYSTEMS
        http://www.ida.liu.se/~TDDB37/

        HS: Distributed systems, 3 points, level C
        http://www.ida.his.se/ida/kurser/distribuerade_system/

        HS: Distributed Real-Time Systems, 5 points, level D
        http://www.ida.his.se/ida/kurser/distributed_real-time_systems/
 

Reading list

Part I

Ch 1: Characterization of distributed systems
Ch 2: System models
Ch 3: Networking and internetworking
Ch 4: Interprocess communication
Ch 5: Distributed objects and remote invocation
Ch 10: Time and global states
Ch 11: Coordination and agreement (see also lecture #4)
Ch 13-14: (parts, see also lecture #5)
Ch 15: (parts)
Ch 17: CORBA case study

Part II (Not updated)

Lecture #4
- review sections from chapter 1
  - 1.4.4 (scalability)
  - 1.4.5 (failure handling)
  - 1.4.7 (transparency)
- read chapter 14: Replication
  (includes fault-tolerant/highly available services)
- read/review sections from chapter 11
  - 11.2.1 (voting/fault tolerance, pp 429-431)
  - 11.5 (consensus, Byzantine agreement)
- read part of chapter 13
  - 13.6: Transaction recovery (pp 539-543)
  - (rest of chapter 13 is covered in lecture #5)

Lecture #5
- read chapter 12 (skip 12.5 - 12.7): transactions
- read chapter 13 (skip 13.4 - 13.5): distributed transactions
- for discussion on distributed file systems, read
  - sections 8.1 - 8.3: Distributed file systems, NFS
  - section 14.4.3: Coda (highly available distributed file system)

Lecture #6
- read chapter 7: security
- read chapter 9 (skip 9.3, 9.5): naming

Lecture #4
Ch. 2: Good models, pp 17-20, 24-25 (refs 25-26)
(2.1-2.2 intuition/good models, 2.5 which model)
Ch. 7: Replica management, pp 169-184 (refs 195-197)
(7.1-7.3 intro/state machines/fault tolerance, 7.4-7.5 replica coordination/order/stability)

Lecture #6
Ch 16: Dependability concepts, pp 411-415, 423-433, 437-444 (refs 444-445)
(intro-16.1 load/classification, 16.4 DRTS model, 16.6-16.7 reliable I/O/conclusion)

Lecture #4
Ch 14: Distributed systems, pp 523-527, 560-564 (refs 574-575)
(14.1-14.3 defs/issues/support, 14.6.4 Byzantine agreement)

Lecture #4
Ch.1-2.5 Introduction, example, pp 1-16
(1-2.5 intro/defs/requirements/measures/example)

Recommended reading

Coulouris et al. (2001): Remainder of book (Ch. 6-9, 12, 16, 18)

Mullender (1993): Ch. 6 and 14.

Mullender (1993): Ch. 17: Real-time communication, pp 447-462, 472-478, 485-486 (refs 486-490) (intro-17.5 bounded delay/reliable LAN, 17.7.1-17.7.2 time & order, 17.9 conclusions)

Helal et al. (1996): Selected replication techniques