Microkernel-based distributed operating systems. Distributed file systems: models for file accessing and file sharing semantics, merging of file systems, naming, encryption and caching. Distributed Shared Memory (DSM): design, choices, coherence and algorithms for migration and replication (superficially).

Readings:

[1] Wu, Sections 12.1.3, 12.2 and 12.3 (through 12.3.1).

Design decisions, parameters and other relevant issues for load balancing. Iterative versus direct load balancing algorithms. Example: diffusion algorithms. Network operating systems. Issues for the designer of a distributed operating system. Servers and services. Types of services in a distributed operating system.

Readings:

[1] Coulouris, Dollimone and Kindberg, Chapter 6 and Chapter 18.

[2] Wu, Sections 10.4, 10.5, 10.6 and Section 12.1.

Static load distribution: optimal vs. suboptimal, approximate vs. heuristic, centralised vs. decentralised, cooperative vs. noncooperative, single vs. multiple applications, nonpreemptive vs. preemtive, adaptive vs. nonadaptive. The problems of processor interconnection, task partition and task allocation. Task precedence graph and task interaction graph. Task partitioning: horizontal vs. vertical, communication delay minimization problem, task duplication. Dynamic load distribution and its six components: initiation policy, transfer policy, selection policy, profitability policy, location policy, information policy.

Readings:

[1] Wu, Sections 9.1, 9.2 and Sections 10.1, 10.2

Case study of a distributed system: the High Data Rate (HDR) wireless system. The Proportional Fair scheduling algorithm for it. The notion of stability for a distributed system - its particularization to the HDR system. Introduction to load distribution: local vs. global, static vs. dynamic.

Readings:

[1] Instability of the Proportional Fair Scheduling Algorithm for HDR (by M. Andrews).

[2] Data Throughput of CDMA-HDR: a High Efficiency - High Data Rate Personal Communication Wireless System.

Evaluation of fair solutions to a resource sharing problem in distributed systems. Classification of routing algorithms. Dependability in distributed systems: reliability, safety, security. Notion of fail-safe system. The concepts of fault, error and failure. Types of faults. The redundancy approach to fault-tolerance. Replication as a fault-handling method; types of replication/ Stable storage as a building block of fault-tolerant system design.

More on the flow control problem as an abstract problem of resource sharing in a distributed system. The concept of max-min fairness. Convergence to max-min fairness as a sequence of local adjustments. Quality of the convergence. Schedulers and terminators, and their trade offs.

Continuation of the discussion on factors influencing latency in a distributed system. Routing versus flow control. Flow control as a resource sharing problem. Requirements on solutions to the flow control problem.

Static scheduling on multiprocessor machines. Task graphs, schedules, Gantt chart, utilization, optimal schedules. The List Scheduling Algorithm of Graham. The Scheduling Algorithm of Coffman-Graham.

Security in distributed systems: Evolution of security needs, Threads, Attacks. Types of clock synchronization (internal, external).

Discussion on the programming project (implementation of Kleinberg's algorithm for finding authorities through the link structure of the web).

General characteristics of distributed systems: Resource sharing (client-server model, object-based model); Openness; Concurrency; Faults and Robustness; Availability; Scalability; Transparency. General design principles of distributed systems: Design goals (Performance, Reliability, Scalability, Consistency, Security); Naming; Structure of software for a distributed system.

Introduction to distributed algorithms and notions of correctness and complexity. Clock synchronization algorithms as a case study. Models of communication for distributed systems. Precision of synchronization algorithms as a function of assumptions in modeling communication.

• Authorities and hubs in a hyperlinked environment as a case study of a distributed system.
• Kleinberg's algorithm to compute authorities from the link structure of the WWW.

• Finish up the technique for analyzing the Price of Anarchy.

• The Scheduling Problem for Identical Users and Related Machines (with a set of allowed machines for each user).
• Techniques for the analysis of the Price of Anarchy in Scheduling Problems.

• The Scheduling Problem for Arbitrary Users and Related Machines (With a set of allowed machines for each User).
• Proof that the Price of Anarchy of this Scheduling Problem does not scale (it is linear in the number of machines).

• The Price of Anarchy on distributed systems.
• Implementation of scheduling under restrictions on user privileges: computation of the Price of Anarchy.

• Distribution of Resources with Limitations on User Privileges.
• The simplest possible limitation: User Privilege on two machines only. Graph Theoretic Modeling and Analysis of the Systems' Balances.

13/09/2005

• The Fair Pricing Model for pricing users in resource sharing

• The Sequential Pricing Model

09/09/2005

• Introduction to Distributed Systems

• Introduction to basic issues such as:

  • Resource Sharing (criteria for the evaluation of solution, pricing)

  • Load Distribution and Balancing

  • Synchronization (timers)

  • Shared Memory Consistency (& Distributed Shared Memory)

  • Security

  • Competitive Entities in a Distributed System and Equilibrium