Networks Flashcards
Define Physical Layer
The physical part of a network (e.g. Cables, Radio Waves, etc.)
The path data takes is a channel (e.g. Frequency Range)
Define Link Layer
Responsible for sending frames (encapsulated packets) over one hop of the physical layer
Link Layer: Frame Header & Trailer
Header: Source & Destination MAC Address
Trailer: Error Checking (e.g. Checksum). Uses Cyclic Redundancy Check (CRC) to identify corruption
Link Layer: Flow Control
Regulation of data transmitted over a network to prevent congestion
Link Layer: ARQ
Automatic Repeat Request. Re-transmits frames if Link Layer Acknowledgement (ACK) isn’t received before timeout
Link Layer: Connection-oriented & Connectionless Communication
Connection-Oriented: Established dedicated connection e.g. TCP
Connectionless: Independently delivered frames e.g. UDP
Link Layer: MAC Layer
Media Access Control sub-layer. Manages access to Physical Layer. CSMA/CD protocol ensures only one sender transmits at a time
Link Layer: LANs: ARP
Address Resolution Protocol. Determines MAC addresses using IPv4. Stores in ARP Cache (Vulnerable to Spoofing)
Network Layer: Define
Responsible for routing packets
Network Layer: MTU
Maximum Transmission Unit. Determines fragment size
Network Layer: QoS Methods
Quality of Service Methods. Minimise loss of important data by giving critical data (voice, video, etc.) necessary bandwidth and low latency
Network Layer: IPv4: Subnetting
Uses Subnet Masks to split on network into multiple sub-networks
Network Layer: IPv4: NAT
Network Address Translation. Translates private IPv4 address to public IPv4 address.
Network Layer: IPv4: CGNAT
Carrier Grade NAT (CGNAT). One public IPv4, many ISP customers.
Network Layer: IPv6: Address Compression
Remove leadings 0s, compress longest consecutive 0s to ::
Network Layer: IPv6: Link-local Address
For routing local network packets. fe80::/10
Network Layer: IPv6: Path MTU Discovery
Determines MTU size on path to receiver, fragmentation occurs only once
Network Layer: IPv6: Deployment Issues
Time, Money, Hardware Support, Education
Network Layer: ICMP
Internet Control Message Protocol. Adds a header to provide diagnostics before IP encapsulation
Network Layer: ICMPv6: NDP
Neighbour Discovery Protocol.
Neighbour Solicitation (NS) and Neighbour Advertisement (NA) messages to retrieve MAC addresses using IPv6 addresses
Router Advertisement (RA) and Router Solicitation (RS) to discover routers and config info (Network Prefix, Default Router Address, Address Allocation Type (SLAAC or DHCP))
Redirections inform hosts of better first-hop routers by updating routing tables.
Network Layer: ICMPv6: SLAAC
Allows hosts to configure their own IPv6 address without relying on a DHCPv6 server
Network Layer: Routing Tables
Database of information about paths to destinations.
Gateway: Connection to another network (typically a router). ‘On-link’ means end point is on the same network
Interface: The point of connection
Metric: Priority, lower number is higher priority
Network Layer: Traceroute
Determines route between two hosts by sending packets with increasing time-to-live (TTL) packets. ICMP time exceeded message sent
to sender when TTL is 0.
Latency not equal to RTT/2 as routes change quickly and routes are likely to be asymmetric
Network Layer: Autonomous Systems (AS)
Interconnected networks managed by a single netwrok
Network Layer: Multi-Homed AS
AS with multiple connections to other AS
Network Layer: Transit AS
AS with no network of its own, just provides connections between AS
Network Layer: Single-Homed/Stub AS
AS with one connection to another AS, typically a service provider
Network Layer: AS: Interior Gateway Protocol
A routing protocol using within autonomous systems
Network Layer: AS: Interior Gateway Protocol: Distance Vector Routing: RIP
Routers interact with only neighbour routers
Routing Information Protocol (RIP). Has a router send its routing table periodically to connected routers.
Limitations:
- Slow Updates (30s periodically)
- Unacknowledged (uses UDP)
- Poor Quality Metric (Hop count doesn’t take into account physical medium speed)
- Maximum Hop Count (after 15 hops, the router is deemed unreachable
- Cracked Authentication Hash (MD5)
Network Layer: AS: Interior Gateway Protocol: Link-State Routing
Routers interact with all routers to establish complete network knowledge
Broadcast reaches all routers and assigns cost
Dijkstras algorithm populates routing table
Benefits:
- Fast Updates
- Known Topology
- Avoids loops
Network Layer: AS: Exterior Gateway Protocol: BGP
Route between autonomous systems
Border Gateway Protocol: Considers relationships with other AS. Neighbours choose whether to route by you
Drawbacks:
- Trust Based
- Slow
- Flapping
- Limited routing table
Transport Layer: Definition
Responsible for data transfer between applications
Transport Layer: UDP
Connectionless, Unacknowledged
Transport Layer: TCP
Connection-oriented, Acknowledged (Uses SYN, SYN-ACK, ACK to establish connection)
Transport Layer: TCP: Congestion Control
Manages flow of data to avoid overload.
Congestion window is number of bytes that can be sent over a network. The ‘Slow Start’ algorithm gradually increases the window until timeout and then resets
Transport Layer: TCP: Flow Control
e.g. Sliding Window Protocol
Uses buffers and messages to allow sender to send data when buffer has enough space
Application Layer: Definition
Responsible for providing services to applications and users
Application Layer: DHCP
Dynamic Host Configuration Protocol.
Assigns IP addresses to reduce IP conflicts and simplify network administration
Uses DISCOVER, OFFER, REQUEST, ACK to assign IP addresses
Application Layer: DHCP Helper
Forwards DISCOVER messages from subnets to DHCP servers. Stops needed a server per subnet which is inefficient
Application Layer: DHCPv6
Uses IPv6 and uses DHCP Unique Identifiers (DUIDs) instead of MAC Addresses.
Terminology Changes
- DISCOVER -> Solicit
- OFFER -> Advertise
- ACK -> Reply
Application Layer: Telnet
Remote access of CLI.
Unencrypted, replaced by SSH
Application Layer: SMTP
Simple Mail Transfer Protocol.
Sends email, no authentication, vulnerable to email spoofing (extensions resolve this)
Application Layer: IMAP
Internet Message Access Protocol.
Used to manage and retrieve emails from a server. Uses TCP
Application Layer: HTTP
Client to Web Server.
GET
HEAD (Retrieve resource headers without retrieving all data)
POST (Process Data)
PUT (Modify or create data)
DELETE
1XX: Information
2XX: Success
3XX: Redirection
- 301: Moved Permanently
4XX: Client Error
- 403: Forbidden
- 404: Not Found
5XX: Server Error
- 500: Internal Error
Application Layer: HTTP/2
Adopted Multiplexing, one TCP connection, many requests
Application Layer: HTTP/3
Adopts Quick UDP Internet Connection (QUIC) protocol.
Built on UDP - adds reliability and encryption
Application Layer: RTSP
Real-time Streaming Protocol
Application Layer: SMB
Server Message Block.
Windows file-sharing
Application Layer: NFS
Network File System.
Unix file sharing. used between servers
Application Layer: MQTT
Message Queuing Telemetry Transport
Communication between IoT devices. TCP or UDP
Pub/Sub Model with Hierarchical Topics
+ wildcard selects all at a level
# wildcard selects all after a specific level
Application Layer: CoAP
Constrained Application Protocol
Communication between constrained devices (low power systems)
Uses small messages
UDP with retransmission and ACK
RESTful architecture like HTTP
Features
- Observation: Clients get updates on resource change
- Proxy Servers: Cache values
- Multicast Support
- Data Chunking
- Resource Discovery using CoRE
Application Layer: DNS
Domain Name System
Converts URL to IP
Uses UDP
ICANN Delegates domain names
Target for cyber attacks
DNS Resolvers query root DNS server if it cannot find the URL
Network Security: Firewalls
A barrier to malicious traffic between internal and external network
Network Security: Stateless Firewalls
Examine packets against a set of rules in an attempt to identify malicious intent
Network Security: Stateful Firewalls
Track connections to identify malicious pakcets
Network Security: Application-Layer Firewalls
Analyse packet contents to ensure the purpose is legitimate e.g. port 80 only receives HTTP
Network Security: NID
Network Intrusion Detection.
Monitoring of network traffic
Network Security: NIDS
Network Intrusion Detection Systems (NIDS)
Use signature-based detection and anomaly detection to identify potential threats (and in some cases take action)
Network Security: NAC
Network Access Control (NAC)
Determines what devices are granted network access (e.g. use MAC Address filtering (poor choice)
Network Security: NAC: 802.1x
NAC Solution using Extensible Authentication Protocol (EAP) requiring login credentials to access a network
Network Security: IPSec
Protocol and standards used by IP to provide authentication, integrity, confidentiality of IP packets. e.g. via encryption
Network Security: VPN: Site-to-Site
Securely connects two netwroks
Network Security: VPN: Remote-Access
Allows client to connect to a server and act resources as if they were physically there
Network Security: WEP
Wired Equivalent Privacy.
Outdated, insecure protocol designed to provide confidentiality over wireless connections similar to that of wired networks
Network Security: WPA
Wi-Fi protected access.
Upgrade to WEP
WPA Personal for small networks uses a constant Pre-shared key (PSK) that is vulnerable to dictionary attacks. Compromised devices are also an issue and there is no user-level authentication
WPA Enterprise for larger orgs, uses 802.1x
Network Security: Key Reinstallation Attack (KRACK)
Vulnerability in WPA and WPA2 that allows an attacker to work out the key used for secure connections
Network Security: WPS
Wifi Protected Setup
Makes it easier to connect to a WPA protected network using an easily trackable 8 digit pin or by pushing a physical button on the access point
Network Security: DNS
Vulernable as not encyrpted.
Where you are going can be seen, not what you are doing
Network Security: DNS Amplification
DDoS Attack using a spoofed IP and a misconfigured DNS server that response to a large request. overloading the victim
Mitigate by ignoring large requests
Network Security: DNS Man-in-the-Middle
DNS is vulnerable to man in the middle attacks
Network Security: DNS Cache Poisoning
Causes DNS Resolver to return the wrong IP aaddress
Network Security: DNS Hijacking
Hackers take over a DNS server
Network Security: DNSSEC
DNS Security Extensions providing authentication and integrity allowing response to be verified.
Slow Deployment like IPv6
Network Security: DDoS
Overwhlem a server’s bandwidth, CPU cucles, server state, etc.
Typically used as a distraction
Network Security: DDoS: TCP SYN Flood
Send multiple TCP SYN packets causing the server to be left waiting
Network Security: DDoS: LOIC
Low Orbit Ion Cannon. Voluntary botnet used to perform UDP/TCP attacks
Network Security: DDoS: HOIC
High Orbit Ion Cannon. Uses HTTP flood attack (lots of POST requests)
Network Security: DDoS: Slowloris
Opens mulitiple HTTP GET requests but never sends the final packet to complete the request header
Network Security: DDoS: IPv6 RA Flood
Exploits NDP and sends lots of RA multicast to consume CPU resources
Network Security: DDoS: Mitigation
Use Content Delivery Network (CDN) to distribute servers. Causes DDOS attacks to be spread across multiple servers
Also ensure systems are patched
Distributed System: Definition
A system where data and computation is distributed over networked machines that communicate and coordinate their actions through messages
Distributed System: Trends
Volume, Variety, Velocity
IOT devices producing lots of data sent to more powerful devices
Distributed System: Trends: Edge Computing
Enables processing to occur closer to source of data, reducing latency and increasing efficiency
Distributed System: Trends: Fog Computing
Addresses limitation of Edge Computing by adding an intermediate layer of resources between the edge and the cloud
Distributed System: Challenges
Heterogeneity: Variety of hardware
Openness: capacity for a system to be extended
Scalability: Ability to remain effective with increase in demand
Failure Handling
Concurrency: Serialise resource access and limit throughput or allow concurrent access and maximise throughput
Distributed System: Physical Models
Cover physical infrastructur and hardware
Distributed System: Architectural Models
Describes components, relationships and interactions of a system.
Validated against performance, adaptability, security and availabilitu
Distributed System: Architectural Models: Communicating Entities
Elements that communicate with each other. Two perspectives
- System-oriented perspective. Entities are processes, threads, and nodes. Not suitable for programming
- Problem-Object perspective. Entities are objects, components (objects that specify required dependencies) and web services
Distributed System: Architectural Models: Communication Paradigms: IPC
Inter-process Communication. Message-passing primatives and socket programming
Distributed System: Architectural Models: Communication Paradigms: Remote Invocation
Two-way exchange. e.g. Request reply protocols (e.g. HTTP)
Distributed System: Architectural Models: Communication Paradigms: Remote Invocation: RPC
Remote Procedure Call.
Request remote function execution and receive a response.
No pass by reference
Distributed System: Architectural Models: Communication Paradigms: Remote Invocation: RMI
Problem-oriented perspective, invoke methods of remote entities
Distributed System: Architectural Models: Communication Paradigms: Indirect Communication
Sends don’t know who they’re sending to and do not need to exist at the same time .
E.g. Group Communication
Recipients join groups to receive messages
E.g. Pub/sub model, publishers send messages to topics and subscribers receive
Distributed System: Architectural Models: Entity Roles & Responsibilities
Processes interact with each other to perform a function, in doing so they take on roles
Client-Server Model
Peer-to-Peer Model. Decentralisation increases scalability, distributed workload but increases complexity
Distributed System: Architectural Models: Entity Placement
Refers to how to map entities (objects, processes, etc.) onto underlying physical infrastructure. It determines performance, reliability and security
Services mapped to servers.
Distributed System: Architectural Patterns: Layering
Logical decomposition of the system into layers
Distributed System: Architectural Patterns: Tiers
Organising Layers onto appropriate servers
Distributed System: Architectural Patterns: One-Tier
- Performance: No network communication overhead
- Scalability: Replicating layers leads to overhead
- Fault Tolerance: Server crash means service is unavailable
Distributed System: Architectural Patterns: Two-Tier
- Performance: Interaction between UI and AL are affected by network
- Scalability: Limited by server’s resources but can be scaled
- Fault Tolerance: Server crash means service is unavailable
Distributed System: Architectural Patterns: Two-Tier with Server Replication
- Performance: Interaction between UI and AL are affected by network
- Scalability: Can add more servers
- Fault Tolerance: Can tolerate N-1 server crashes
Distributed System: Architectural Patterns: Three-Tier
- Performance: Interactions between UI and AL or AL and DM (Data Management) are affected by network
- Scalability: Can scale application logic and data management independently
- Fault Tolerance: Finer grain fault tolerance
Distributed System: Architectural Patterns: Object Replication
- Performance: Overhead to keep data consistent
- Scalability: Limited by the mechanism to preserve consistency (limited by server’s storage)
- Fault Tolerance: Can tolerate N-1 crashes
Distributed System: Architectural Patterns: Object Partitioning
- Performance: No overhead for consistency. Overhead to find right partition
- Scalability: Can partition over more servers but the request load for most frequently accessed data affects it
- Fault Tolerance: Server crash means all data objects stored in that server are unavailable
Distributed Systems: Fundamental Model
Fundamental models explicitly state assumptions about the system to capture properties including performance, reliability and security
Distributed Systems: Fundamental Model: Interaction Model
Describes interactions in a system
Distributed Systems: Fundamental Model: Interaction Model: Factors affecting communication
Latency (transmission time, network card delay, os delay)
Bandwidth
Jitter (variation in time to deliver a series of messages)
Distributed Systems: Fundamental Model: Interaction Model: Synchronous Models
Has known lower and upper bounds for each step.
Messages received in bounded time
Clock drift rate is known
Distributed Systems: Fundamental Model: Interaction Model: Asynchronous Models
Proccess execution time unknown
Message times not known
Clock drift rate unknown
Distributed Systems: Fundamental Model: Interaction Model: Failure Model: Process Omission Failure
e.g. Crash
In Synchronous, detected with timeouts. Known as a fail-stop if can be detected with certainty
In Asynchronous, cannot be detected
Distributed Systems: Fundamental Model: Interaction Model: Failure Model: Communication Omission Failure
e.g. Message Drop
Arbritrary Failure e.g. communication channel corrupts message, message delivered more than once
Timing failure (in synchronous, e.g. exceeds time allowance etc)
Distributed Systems: Fundamental Model: Interaction Model: Failure Model: Handling Failures
Failure Masking: Hiding failure e.g. resend message, restart process
Failure Conversion: convert to acceptable failure. e.g. checksum: arbitrary corruption to handlable failure
Distributed Systems: Fundamental Model: Interaction Model: Reliable Communication
Requires validity (messages eventually delivered)
Integrity (delivered msg same as sent)
Ensured through timeout-based retransmission.
Checksums. disregarding duplicate msgs
Distributed Systems: Fundamental Model: Interaction Model: Security Model
Describe how security is achieved
Threats include, process threats, communication threats, dos
Prevented through encryption, authentication, secure channels
Distributed Systems: Measuring Time
Measured using quartz clocks or atomic clocks
Distributed Systems: Timing: Local Network Clock Synchronisation
Used to sync a machines clock with an accurate one
Distributed Systems: Timing: Local Network Clock Synchronisation: Cristian’s Algorithm
- Cristian’s Algorithm has the user request a server for a time. It then calculates it as Tserver + (T1 – T0)/2 where T1 is time response is received by client and T0 time when request is sent. Division by 2 is an approximation that the time delay between the client and server is symmetrical
Distributed Systems: Timing: Local Network Clock Synchronisation: Berkeley Algorithm
assumes no clock server and a co-ordinator fetches the time of each node, it calculates the average time difference and broadcasts the new time. To improve the algorithm, ignore outliers, use a secondary-coordinator in case the primary goes down and instead, broadcast the time difference for each node (reducing impact of latency)
Distributed Systems: Timing: Internet Network Clock Synchronisation: NTP
- Network Time Protocol (NTP) uses a hierarchy of time servers (Stratum model)
- Stratum level 0-15 indicates the device’s distance to the reference clock. stratum 0 is atomic clocks
- Algorithm uses a UDP packet with 4 slots for 4 timestamps, client send, server receive, server send, client receive. Network delay calculated as delta = (T3 – T0) – (T2 – T1). Assume request and response delay are equal so time at server when client receives is T2 + delta/2. Clock skew is time different between client and server. Theta = T2 + delta/2 – T3
- Estimating clock skew several times determines how the client should adjust their clock. <125ms: Slewing (slowly adjust). 125ms-1000s: stepping (reset clock). >1000s: manual reset
Distributed Systems: Timing: Logical Clocks
Count the number of events
No relation to time
Distributed Systems: Timing: Logical Clocks: Happens-before Relation
Event a happens before event b if
- they occur at the same node and a occurs before b
- OR event a sends a message and event b is the recipient of that message
- OR there exists an event c such that a-> c, c -> b
If Neither a -> b or b-> a then a || b (concurrent)
Distributed Systems: Timing: Logical Clocks: Lamport Clock
Each node maintains a counter that increments on each local event
Sent messages include time t. Recipient uses largest of the received time and their time
FLAWED: If L(a) < L(b) where L(e) is the value of t at e, we cannot tell which happened before or whether they’re concurrent
Distributed Systems: Timing: Logical Clocks: Vector Clocks
Each node tracks a vector of observed events
On Receiving a message, find the max of each vector value
- Relational operators can be defined on the vector timestamps. Two vector timestamps are equal if all values are the same, one vector timestamp is less than another if all values are less than. Two vector timestamps are concurrent if neither one is less than the other
- V(a) < V(b) iff a -> b
- V(a) = V(b) iff a =b
- V(a) || V(b) iff a | b
Distributed Systems: Mutual Exclusion
Ensuring only one process accesses a critical section at any time
Distributed Systems: Mutual Exclusion: Algorithm Requirements
No Deadlocks
No Starvation (indefinite waiting process)
Fairness (every site gets a chance to access the critical section)
Fault Tolerances (Failures are recognizable)
Distributed Systems: Mutual Exclusion: Algorithm Properties
Safety: Mutual exclusion guaranteed and freedom from deadlock
Liveness: Every process eventually accesses the critical section
Fairness: Access is in a fair-order, first-come-first-serve
Performance: Measured in number of messages, client delay, synchronisation delay
Distributed Systems: Mutual Exclusion: Token-based Algorithm: Centralised Algorithm
Server stores queue of requests to obtain token and grants token when process finishes with critical section.
Satisfies safety, liveness, and fairness
Performance: Single point of failure, risk of bottleneck. Server must be elected or known
Distributed Systems: Mutual Exclusion: Token-based Algorithm: Ring Algorithm
Suitable for ring topologies
Token passed to neighbouring process
Satisfies safety, and liveness
Does not satisfy fairness. Ordering is based on ring order
Performance: Token circulation consumes bandwidth
Distributed Systems: Mutual Exclusion: Token-based Algorithm: Raymond’s Tree Based ALgorithm
Nodes have one parent to which they send requests for the token to.
Each node maintains a FIFO queue
Satisfies Safety, Liveness (if not using a greedy strategy) and Fairness
Performance: O(log n)
Distributed Systems: Mutual Exclusion: Non-token-based Algorithm: Ricart-Agrawala
Sites broadcast request to access critical section. Those not in request queue or critical section respond immediately, otherwise add to queue
When leaving critical section, respond to broadcast requests as way of letting the process know they can enter the critical section
Requests contain site ids and timestamp
Satisfies Safety Liveness and Fairness
Good Performance
Distributed Systems: Mutual Exclusion: Quorum Based Algorithm: Maekawa’s Algorithm
Quorums are subsets of nodes that must agree on an operation.
Any two quorums must have a common site to ensure mutual exclusion
- Processes request access and only gain access when all processes in the quorum reply. Processes don’t reply when they know another process is accessing the critical section.
- Processes notify all other processes in the quorum when they have released the critical section
Satisfies safety
Does not satisfy liveness (easy to deadlock with two requests t the same time. Resolved by using happens-before ordering)
Does not satisfy fairness (Resolved with vector clocks)
PErformance better than ricart-agrawala if N>4
Distributed Systems: Leader Elections: Definition & Advantages
Used to give one node special powers:
Systems are easier to manage and design
Can be more efficient than consensus
Can improve performance and costs
Easier to write software
Distributed Systems: Leader Elections: Properties
Safety: One process becomes the leader and all other processes know this
Liveness: All processes participate and eventually are either elected or identify a leader
Performance: Minimise number of messages
Distributed Systems: Leader Elections: Ring Leader Election
- Each process has a unique identifier I(n) that acts as a priority. Higher value means more suitable for leader
- Satisfies safety and liveness
Distributed Systems: Leader Elections: Bully Election
- A failed process is detected and an ‘Election’ message is sent to processes with a higher unique identifier to announce an election
- Higher ID processes respond with ‘Answer’, then they send out ‘Election’ to processes with a higher Id than them. This repeats until a process gets no ‘Answer’s meaning they are the highest priority. They then send out coordinator messages
- Satisfies liveness, can violate safety if a failed process leads to two coordinators
- Performance is best case n-2 messages, worst case O(n^2) messages
- Unreliable process failure detection can cause two coordinators.
- Multiple elections are handled as highest id is still selected
Distributed Systems: Multicast
- Multicast is an asynchronous group communication protocol.
- Multicast middleware sits between application and network. Data is send and received by middleware. Data is multicasted and delivered to and from application
Distributed Systems: Multicast Models: Basic Multicast
- Messages will be eventually be delivered to the group (closed or open (sender can be outside the group))
- B-multicast(g, m) sends m to all processes p in m with send(p, m). Middleware receives with receive(m) and delivers to application with B-deliver(m)
- Poor failure tolerance, if crash during multicast then not all will receive
Distributed Systems: Multicast Models: Reliable Multicast
- Improves basic multicast, guarantees integrity (delivers messages at most once), agreement (all or nothing delivery), validity (if multicast, a message will eventually be delivered)
- When message received for first time, the node multicasts the message and then once that’s done delivers the message. So if the sender crashes then no multicast occurs or at least one other process receives the message and calls multicast.
- O(N^2) messages. Inefficient
- Gossip protocol stop forwarding to all in the group and selects only a few
Distributed Systems: Multicast Models: FIFO Ordered Multicast
- Built on reliable multicast and ensures two messages multicast from the same process maintain their delivery order
- Uses buffer queue to store messages until guarantees are met
Distributed Systems: Multicast Models: Causal Ordering Multicast
- Built on FIFO Ordered Multicast and ensures that if a multicast happens-before another multicast then it will be delivered before the other
Distributed Systems: Multicast Models: Total Ordered Multicast
- Built on reliable multicast and ensures if a multicast happens before another multicast, then it must be delivered before the other for all processes
- One process acts as a sequencer, responsible for ordering messages. Processes add messages to a buffer until the sequencer tells them to process it
- Poor Fault Tolerance, if leader crashes no messages received
Distributed Systems: Multicast Models: FIFO-Total ORdered Multicast
- Combination of FIFO ordered multicast and total ordered multicast
- Meets requirements for casual multicast
Distributed Systems: Consensus
- Used to achieve agreement on a single data value among distributed processes
Distributed Systems: Consensus: Two Generals Problem
- Two generals problem has no solutions, it focuses on the issue of network communication and that you can never guarantee reliable communication in a distributed systems
Distributed Systems: Consensus: Byzantine Generals Problem
- The byzantine generals problem focuses on node behaviour and says that you need 3f + 1 total generals to tolerate f malicious generals i.e. 1/3 may be malicious
Distributed Systems: Consensus: Algorithm Requirements
- Algorithms must satisfy:
Termination (eventually every non faulty process sets its value)
Agreement (All-non faulty processes decide on the same value
Integrity (If majority propose a value, then non-faulty processes select that value)
Distributed Systems: Consensus: Relation to Total Ordered Multicast
- Without failures, total-order multicast can be used to solve consensus. All processes TO-multicast proposed values, sequencer multicast.
An algorithm that solves consensus can also be used to implement TO-multicast without a leader (sequencer) – use successive rounds of consensus to decide on next message
Distributed Systems: Consensus: Synchronous System Consensus
- Timeouts to detect when a process has crashed
- With F crashed processes, at least F + 2 processes are needed total to make a consensus (at least 2 processes needed to form a consensus)
- Need F + 1 rounds as a failure during a round may mean some processes have not correctly received values. Another round is necessary to ensure any missing values are updated
- Each process stores only the new values multicast to it each round before choosing a value in the final round
- With F arbitrary failures, more than 3F processes are needed with F + 1 failures. AKA if more than a third of processes fail with arbitrary failures then you cannot reach a consensus (byzantine generals problem)
Distributed Systems: Consensus: ASynchornous System Consensus
- Cannot use timeouts to detect missing messages so cannot detect crash processes
- Can only achieve consensus with a probability to a certain level
Distributed Systems: Data Replication: Primary-Backup Replication
- One server acts as a primary, the others act as a backup
- Clients interact with the primary who executes and stores the response (if it hasn’t been done before), changes in data are replicated by the backups using ordered multicast (so all are synchronised), primary awaits ACKs
- Can tolerate N-1 server failures. If backup fails, it is replaced and its state is collected from other backups (not the primary to avoid overload). If primary fails, a new primary is elected via leader election, new primary registers itself with name service so clients no who to consult. Clients resend requests after timeout
Distributed Systems: Data Replication: CAP Theorem
- CAP Theorem states it is impossible to achieve the following three properties at once, at most two can be obtained:
Consistency (Replicas have the same state for data objects)
Availability (All requests are served as long as at least one server is available)
Partition Tolerance (Data stores continue to work even with a network partition) - Proved by contradiction, a network partition occurs and a client updates on server, another client reads from another server. Values are inconsistent
Distributed Systems: Data Replication: CAP Theorem: AP Systems
- Availability & Partition Tolerance ensured and Consistency is lost
- Can ensure partial consistency on partially synchronous networks as messages will be eventually delivered. During synchronous periods the servers reconcile data, during asynchronous periods, read operations return inconsistent values
Distributed Systems: Data Replication: CAP Theorem: CP Systems
- Consistency & Partition Tolerance ensured and availability is lost. Refuse requests when a network partition occurs (may accept read requests)
- Suitable when consistent data is essential
Distributed Systems: Data Replication: CAP Theorem: CA Systems
- Not really a distributed system as Partition Tolerance is not impossible on all distributed systems (even for those on a single site)
Distributed Systems: Data Replication: Scalability
- Scalability is the ability to adapt something to meet greater needs in the future
- Scalability Parameters: External fluctuating values e.g. number of client, workload
- Scalability Metrics: Measurements of system properties e.g. latency, throughput, availability
- Scalability Criteria: Expected metrics, e.g. system available 99.99% of the time
- Adding more servers only improves metrics to a certain point. Overhead of adding servers include downtime for reconfiguration (e.g. rebalancing) and increased messages for server communication. Bottlenecks as scale parameters increase for deciding on what server to use etc.
Distributed Systems: Data Replication: Scalability: Primary-Backup Model Scalability
- The primary-backup model has poor scalability, the primary server handles all requests and the backups have to send ACKs with every change. TO resolve, add more primary servers and partition the data, and make the primary only wait for the majority of ACKs, not all. The overhead of this is adding new servers means more time spent partitioning and migrating, also dependency on data objects increases the coordination required among primary servers. And not all backups may be synchronised with the primary, so needs to be taken into account when running leader election
Distributed Systems: Consitency Models: Strong Consistency
Models use CP systems and requires a global ordering of updates that all replicas agree on
Distributed Systems: Consitency Models: Weak COnsitency
Models use AP system and uses eventual consistency
Distributed Systems: Consitency Models: Passive Replocation
The Primary-Backup MOdel
Distributed Systems: Consistency Models: Active Replication
clients communicate with a group of replicas and updates are propagated amongst replicas using total-order multicast
Distributed Systems: Consistency Models: Strict Consistency
where a write to any variable is immediately available to all other replicas. The DS acts as a single store, this is impossible as instantaneous message exchange isn’t possible
Distributed Systems: Consistency Models: Linearizability
a weaker version of strict consistency stating that if one operation completes before another, then it precedes the other. Implemented with a perfectly synchronised clock and bounded message delays (synchronous system) with total order multicast
Distributed Systems: Consistency Models: Sequential Consistency
weaker than linearizability that does not mention timing but states that if a write precedes another write then no process reading the variable will read the latter write before the former. Implemented by forcing replicas to return local copies and write operations trigger TO-multicast that awaits acknowledgements. No synchronised clocks needed
Distributed Systems: Consistency Models: Causal Consitency
any writes with a causal relationship must be seen in the same order and the order of values returned by read operations must be consistent with the causal order. Implemented with Vector Timestamps and write operations are multicasted
Distributed Systems: Consistency Models: Eventual Consitency.
How to resolve conflicts
- Eventual Consistency states that after an unspecified amount of time following a write, if there are no more writes, then all replicas will be in the same state. No guarantee of how long it will take. Implemented by propagating changes in the background. Conflicts resolved with a consensus algorithm, a rollback, or delegation to the application. Allows for fast reads and writes even when network partition occurs, very weak notion of consistency and requires mechanism to deal with conflict
Distributed Systems: Consistency Models: Strong Eventual Consistency
CRDT
- Strong Eventual Consistency guarantees that any two replicas that have received the same set of updates in any order will be in the same state. Concurrent updates applied with Conflict-Free Replicated Data Types (CRDT)
- Operation-based CRDT: On write, broadcast operation. On broadcast receive, apply operation. Used in collaborative editors e.g. Overleaf, Google Docs
- State-based CRDT: On write, broadcast state. On broadcast receive, merge states. Used for grow-only counters
Distributed Systems: Consistency Models: Quorum-based Protocol
- Quorum-based Protocols, read quorum and write quorum, the two quorums intersect to ensure consistency. R + W > N. On a write, the write quorum replicates others in the background. On a read, replicas return stored value and vector timestamp so that more recently updated replicas have their values take precedence. If replicas fail, the quorum can read and write as long as the remaining vectors form a majority
Distributed Systems: Remote Invocation
- Remote Invocation utilises Request-Reply protocols. There are three styles
Request (R) Protocol – No reply expected
Request-Reply (RR) Protocol
Request-Reply-Acknowledgement (RRA) Protocol - They are implemented with UDP to reduce overhead
- Protocol can fail if there is a process crash, channel omission failure or messages out of order. To resolve, use timeouts and ids for messages to discard duplicates
Distributed Systems: Remote Invocation: Remote Procedure Call (RPC)
- Call a subroutine remotely as if it were local (Transparency)
- There should be no syntax difference between local and remote
- RPC is more vulnerable to failures
- Latency is significantly larger
- RPC cannot support call by reference
- RPC Call Semantics is how the RPC system handles delivery, execution and responses:
- Maybe: No fault tolerance. System can’t guarantee request will be executed
- At-Least-Once: Request executed at least once and client receives a response
- At-Most-Once: Requests executed at most once and duplicates are discarded
- Local Procedure calls are Exactly-Once
RPC Interfaces specify procedures offered by a server. They are described in an Interface Definition Language (IDL), enabling communication regardless of programming language
Distributed Systems: Remote Invocation: Remote Method Invocation
- OOP equivalent of RPC, call remote object methods as if local
- Like RPC, uses interfaces, request-reply protocols and has transparency. Additionally allows objects to be used as parameters in method calls
- Remote Object References identify remote objects and can be passed as arguments or returned as results
- RMI can cause local invocations on the remote machines, instantiate new objects (new IDL must be created)
- Clients using garbage collection use distributed garbage collection modules to ensure remote object’s lifecycles are handled properly. Uses reference counting, increment when a reference is created and sent to a different process. Decrement when reference count is no longer needed. If 0, garbage collector reclaims memory
- Exceptions raised by RMI are exposed to the caller, they can be caused due to remote nature of the object, such as the remote process crashing or communication omission
Distributed Systems: Peer-to-Peer
- Client-Server architectures have bottlenecks of computational power, memory, disk space, network bandwidth. Upgrading infrastructure with more servers and bandwidth takes time and has high maintenance and management costs
- Peer-to-Peer is an alternative with two types
- Servers become peers, clients communicate with service provider consisting of peers
- Both clients and servers become peers
Peer spread over internet. Peers can leave or fail. Computational power and resources fluctuates. Poses challenges of
How to distribute data and consumption
How to access distributed data and computation
How to cope with failures
How to cope with high churn (rate at which nodes enter and leave the network)
Distributed Systems: Peer-to-Peer: Napster
- Napster uses a server to store locations of files. User requests file location, server responds with locations, user requests from peer, file is delivered, the user then updates the server to say it now has the file
- Taught us that large-scale P2P systems are feasible although it was not a pure P2P system with a centralised server index. It was limited by server-based indexing with lots of requests and index updates. Ensuring consistency is simple as it was used for mp3 files which are never updated
Distributed Systems: Peer-to-Peer: BitTorrent
- Sharing a file to BitTorrent requires creating a torrent, this is done by using a .torrent file that references the file(s) they want to distribute.
- A tracker keeps track of peers participating in a torrent. The URL to the tracker is stored on .torrent server where .torrent files are stored. The .torrent file directs the user to the tracker.
- Peers are either Seeders or Leechers. A seeder has the entire file downloaded. A leecher is in the process of downloading a file. New peers contact the tracker who responds with a list of peers who they can connect to exchange data
- The .torrent server also stores file name and size and chunk chesums (files are divided into chunks, the server stores checksums of these ensure integrity)
- BitTorrent operates on peer cooperation principles, peers must be willing to upload chunks of a file they have download to other peers who are downloading.
- Uses a tit-for-tat incentive mechanism
- Peers that don’t upload enough are choked.
- Choking/unchoking decisions is based on the upload rate of the peer.
- New peers are penalised because they don’t have any chunks to upload. Optimistic unchoking unchokes a random peer every 30 seconds
- Trackers and .torrent server are centralised
- Evolved towards a Distributed Hash Table (DHT) based tracker-less schema to achieve full decentralisation. Uses a ring network.
Distributed Systems: Distributed Transactions:
- A transaction is a set of sequential operations guaranteed by a server to be atomic in the presence of multiple clients and server crashes. Operation is free from interference, either all steps of the transaction complete or none. Needs to tolerance crash failures or omission communication failures.
- ACID Properties (Atomicity, Consistency, Isolation, Durability)
- In the event of a server crash, a completed transaction must be durable. A new server to replace the old one can recover the server’s objects. Uncommitted transactions are aborted and recovery procedures restore objects to last committed values
