Distributed Systems

Distributed System, independent, coherent

A collection of -- computers (nodes) that appear to users as a single -- system.

Middleware, intermediary, complexities

Software that acts as an -- between different software applications, enabling them to work together seamlessly. It hides the -- of the underlying infrastructure and provides a consistent interface for applications.

Client-server systems, central

Networked computers interacting with a -- server.

Peer-to-peer networks, distributed

Workloads -- among many computers running the same software.

Cell phone networks, switching, internet

Workload shared across headsets, -- systems, and internet devices.

Heterogeneity, openness, security, scalability, fault tolerance, concurrency, transparency

Challenges in distributed systems (7), H—, O—, S—, S—, F— T—, C—, T—

Heterogeneity, networks, languages

Variations in --, hardware, OS, programming --.

Openness, extended, uniform

System's ability to be -- or reimplemented, with documented interfaces and -- communication.

Security, confidentiality, integrity, availability

Protecting communication between devices, including --, --, and --.

Scalability, effectiveness, increase

The system's -- when resources and users --.

Fault Tolerance, reliability

System -- despite faults.

Concurrency, shared, simultaneously

Multiple clients accessing -- resources --.

Transparency, complexity

Hiding system — from users.

Access, location, concurrency, replication, failure, mobility, performance, scaling

Types of transparency (8): A—, L—, C—, R—, F—, M—, P—, S—

Physical, architectural, fundamental

System Models(3)

Physical

Represents hardware elements.

Architectural

Overall design and structure.

Fundamental

Conceptual framework.

Crash-stop, crash-recovery, byzantine

Node failure models(3)

Crash-stop

Node fails and stops responding.

Crash-recovery

Node crashes and recovers.

Byzantine

Node exhibits arbitrary, malicious behavior.

Synchronous, asynchronous, partially synchronous, bounded asynchrony

Timing and synchrony assumptions(4)

Synchronous

Upper bound on processing time for nodes

Asynchronous

Arbitrary delivery times

Partially synchronous

Unpredictable transitions between synchronous and asynchronous periods

Bounded asynchrony

Known upper bound on message delivery.

Reliable, fair-loss, arbitrary links

Network failure models(3).

Caching, frequently, slower

Using faster storage for -- accessed data from — memory.

Temporal, spatial

Locality of reference types(2)

Temporal locality

Recently accessed data likely to be accessed again.

Spatial locality

Data near recently accessed locations likely to be accessed soon.

Cache hit

Data found in the cache.

Cache miss

Data not found in the cache.

Least Recently Used, FIFO, Belady's algorithm

Cache replacement policies(3)

Server-side caching

Storing web files on a server for later use.

Content Delivery Networks (CDNs)

Servers that speed up delivery of web content.

Eavesdropping, tampering, masquerading, replaying, non-repudiation

Security threats(5): E—, T—, M—, R—, N—

Encryption, authentication, digital signatures, authorization, auditing

Security measures(5): E—, A—, D— S—, A—, A—

Cryptography, plaintext, ciphertext

Securing communication by converting -- into --.

Symmetric key cryptography

Uses a single key for encryption/decryption.

Asymmetric key cryptography

Uses a pair of keys (public and private).

Churn, network divergence, selfish users

P2P system challenges (3)

Decentralized, retrieval, replication, consistency

P2P data management (4): — storage, data —, —, and — management

Distributed Hash Tables, routing, peers

Structured -- algorithms for mapping keys to --.

Chord, lookup, keys

A distributed -- protocol that maps -- onto nodes.

Cloud Computing, remote internet

Storing and accessing data on -- -- servers.

Distributed Ledgers (Blockchain), cryptographic

A growing list of records (blocks) linked by -- hashes.

Decentralization and tamper-resistance

Blockchain goals(2)

Public key cryptography

Uses public and private keys.

Cryptographic hash functions

Produces a fixed-size string of characters (hash value).

Bitcoin

The first decentralized currency.

Proof-of-Work (PoW), computational

Miners compete to solve a -- puzzle.

Remote Method Invocation (RMI), invoke

Allows an object to -- methods on a remote object.

Remote Procedure Call (RPC), Interface Definition Language

A program requests a service from another program on a different computer. Uses -- -- -- to define interfaces.

HTTP/REST, architectural

An -- style for creating web services.

GET, POST, PUT, PATCH, and DELETE

HTTP methods.

Paxos, proposers, acceptors, learners

A consensus protocol to ensure all nodes agree on a single value. Uses --, --, and --.

Raft, leader-based

A -- -- consensus protocol based on PAXOS. Simplified compared to PAXOS.

Practical Byzantine Fault Tolerance

for reaching agreement despite malicious nodes.

Indirect Communication

Communication via an intermediary.

Group communication, publish-subscribe systems, message queues shared memory, tuple spaces

Indirect communication paradigms (5)

Publish-subscribe systems

publishers publish events, subscribers express interest.

Message queues

point-to-point communication using queues.

Shared memory

abstracts shared memory in distributed systems.

Tuple spaces

semi-structured shared spaces with tuples.

Group Communication

Multiple nodes communicate as a group.

Unicast, multicast, broadcast

Types of group communication (3)

Active replication

Multiple copies of a server handling requests independently.

Best effort, reliable, and atomic multicast

Group communication reliability guarantees (3)

Failure

inability of a system to perform its required function.

Error

transition to an invalid state.

Fault

cause of an error.

Omission, crash, timing, Byzantine

Types of failures(4)

Availability

readiness of a service.

Reliability

continuity of correct service.

Graceful degradation

ability to maintain limited function during failure.

Passive replication

Uses a primary replica.

Unordered, global time, FIFO, casual, total ordering

Message ordering(5): U—, G— T—, F—, C—, T— O—

Chubby, synchronisation, ephemeral

A distributed lock service for -- and coordination, uses -- nodes for temporary locks.

BigTable, NoSQL, Google, Chubby, SSTable

A -- database service using a wide-column key-value store, uses -- File System, -- lock service and --.

Google File System (GFS), consistency, chunk servers

Single meta-data copy, reduced -- model, uses a master node and -- --.

MapReduce, map, shuffle, reduce

A programming model for processing big data, includes —, —, and —.

Eventual Consistency

Data eventually becomes consistent across replicas.

Vector clocks

Causal ordering with multicast messages uses -- --.

Consistency, Availability, Partition tolerance

CAP theorem

Horizontal scaling

Adding more servers.

Vertical scaling

Increasing a single server's power.

Load balancing

Distributes requests across servers.

Partitioning

Breaking data across servers.

Replication

Making copies of data on multiple servers.

Software Containment

Encapsulating software and its dependencies.

Virtualization

Enables multiple OSs on a single machine.

Containers

Enables deployment of multiple apps using the same OS.

Docker

Uses Linux OS for lightweight sandbox.

Physical clocks

measure elapsed time, needing synchronisation.

Logical clocks

count events, track order, not time. Examples include

NTP, GPS

-- and -- used for physical clock synchronisation.

Timestamps

used for when events occur.