Distributed systems Midterm

A collection of independent computers that appears to users as a single coherent system ! Distributed System

The main goal of a distributed system: make it easy for users and applications to access remote resources and share them efficiently ! Goal of Distributed Systems

Hide differences in data representation and how a resource is accessed ! Access Transparency

Hide where a resource is located ! Location Transparency

Hide that a resource may move to another location ! Migration Transparency

Hide that a resource may be moved during use ! Relocation Transparency

Hide that a resource is replicated across the system ! Replication Transparency

Hide that a resource can be shared by several users at once ! Concurrency Transparency

Hide failure and recovery of a resource ! Failure Transparency

Implementations from different vendors can work together ! Interoperability

Applications developed for one system can run on another ! Portability

Relatively easy to add or remove components ! Extensibility

No machine has complete system state, decisions are local, failure of one does not ruin algorithm, no global clock assumed ! Properties of Decentralized Algorithms

Scalability problem: small latency in LAN vs large latency in WAN ! Geographical Scalability

Technique: try to avoid waiting for responses to remote service requests ! Hiding Communication Latency

Technique: split components into smaller parts and spread them (ex: DNS, WWW) ! Distribution

Technique: replicate components across the system for availability and load balancing ! Replication

Replication + caching leads to consistency problems ! Consistency Problem

Assuming the network is reliable, secure, homogeneous, zero latency, infinite bandwidth, etc. ! Pitfalls in Distributed Systems

A homogeneous collection of PCs/workstations connected by high-speed LAN, running same OS ! Cluster Computing System

High heterogeneity, resources from different organizations pooled into a Virtual Organization ! Grid Computing

Transaction property: indivisible execution ! Atomicity

Transaction property: does not violate system rules ! Consistency

Transaction property: concurrent transactions don’t interfere ! Isolation

Transaction property: committed changes are permanent ! Durability

Middleware that facilitates application communication in organizations ! Enterprise Application Integration

Devices are small, battery-powered, wireless, must handle context, ad hoc composition, and sharing ! Pervasive Systems

How software components are organized and interact ! Software Architecture

An instantiation of software architecture, e.g., client-server, peer-to-peer, edge computing ! System Architecture

Organizing software in layers, requests down and results up ! Layered Architecture

Each object is a component, interaction via (remote) procedure calls ! Object-based Architecture

Components communicate via a shared repository ! Data-centered Architecture

Processes communicate by propagating events, often publish/subscribe ! Event-based Architecture

One server provides resources to multiple clients ! Centralized Architecture

Clients act as both servers and clients, often organized as overlay networks ! Peer-to-Peer Architecture

Combination of centralized and P2P, often with edge servers ! Hybrid Architecture

Client-server communication without connection, efficient if no loss ! Connectionless Protocol

Client-server communication with connection setup/teardown, reliable (TCP/IP) ! Connection-oriented Protocol

Three levels: UI (client), processing (app logic), data (DB/files) ! Application Layering

A thin client handles only UI; server handles processing + data ! Thin Client

A fat client handles UI + processing; server handles data ! Fat Client

Three-tiered model: client (UI), app server (processing), DB server (data) ! Three-Tiered Architecture

Problem: how to find a file X in P2P when publisher may be offline ! Lookup Problem

Organized using Distributed Hash Tables (DHT), keys map deterministically to nodes ! Structured P2P

Chord system maps keys to successor node with ID ≥ key ! Chord Lookup

When node joins/leaves, it updates successor/predecessor and transfers data ! Chord Membership Management

Classic example of client-server distributed file system from Sun Microsystems ! NFS (Network File System)

A program in execution, sharing CPU, memory, I/O ! Process

Creating a process or switching context is expensive ! Problem with Processes

Multiple threads within one process for efficiency ! Multithreading

One thread for user interaction, one for computation, one for backup ! Example: Spreadsheet with Threads

In UNIX, different parts of apps communicate with IPC mechanisms ! Threads in UNIX Applications

Kernel does not know threads; lightweight; blocking call blocks entire process ! User-level Threads

Kernel manages threads; can switch on blocking; expensive to create/switch ! Kernel-level Threads

A web browser uses multiple threads to fetch components simultaneously ! Multithreaded Client

Server with dispatcher thread and multiple worker threads ! Multithreaded Server

Run multiple OS instances on one machine for portability and fault isolation ! Virtualization

Organizes VMs between hardware and OS for portability/flexibility ! Virtual Machine Monitor

Server that handles requests directly, one at a time ! Iterative Server

Server that forks threads/processes for requests ! Concurrent Server

Daemon like inetd that listens on multiple ports, launches specific servers on demand ! Superserver (inetd)

Server does not store client state, e.g., web server ! Stateless Server

Server maintains client-specific info (locks, cookies) ! Stateful Server

Multiple servers grouped for performance and fault tolerance ! Server Cluster

Layer 1: Bits between sender/receiver ! Physical Layer

Layer 2: Frames with error/control ! Data Link Layer

Layer 3: Routing packets across networks ! Network Layer

Layer 4: Provides reliable/unreliable transport (TCP/UDP) ! Transport Layer

Layer 5: Manages sessions between applications ! Session Layer

Layer 6: Formats/presents data ! Presentation Layer

Layer 7: Supports apps like HTTP, FTP ! Application Layer

Message stored until delivery possible ! Persistent Communication

Message dropped if receiver inactive ! Transient Communication

Sender continues immediately after sending message ! Asynchronous Communication

Sender blocks until request is accepted or processed ! Synchronous Communication

Blocking request–reply model between client/server ! Conventional RPC

Stub on client packs request, stub on server unpacks ! RPC Stubs

Client continues without waiting for reply, callback later ! Asynchronous RPC

Socket API: create, bind, listen, accept/connect, send/recv, close ! Berkeley Sockets

Standard library for passing messages in distributed computing ! MPI (Message Passing Interface)

Persistent message delivery with queues ! Message Queuing System

String of bits/characters referring to an entity ! Name

Access point through which an entity is operated ! Address

Unique reference to at most one entity, never reused ! Identifier

Resolve a name to an address ! Name Resolution

Send broadcast asking “who has this address” ! Broadcasting / ARP

When entity moves, leaves reference to new location ! Forwarding Pointers

Entity always found via “home” location ! Home-Based Approach

Mapping identifiers/keys to nodes via hash tables ! Distributed Hash Table (DHT)

Each node stores pointers to nodes at distances 2^i ! Chord Finger Table

Names organized into a graph of directories and leaves ! Structured Naming

Another name for the same entity ! Alias