Distributed Systems And Networks

Application

Transport

Network

Link

Physical

Shields upper layers from specific connection type.

Transmits frames over physical media + encapsulates ip datagrams into frames

Receives frames and passes ip datagrams up the stack

Detects and handles transmission errors l

A packet, header, and trailer

Concurrency

No global clock

Independent features

Frames that vary based on the physical layer e.g. ethernet frame

Regulating the flow of data so a slow receiver is not swamped by a fast sender

Conectionless and no acknowledgement

(Low error rate networks e.g. wired ethernet. Connectionless means no signal path decided in advance)

Acknowledged Connectionless

(WiFi)

Acknowledged Connection oriented

(Long delay, unreliable links e.g. satellite)

A way to handle acks and errors. Sends a frame then waits for ack then sends next frame etc.

Can be improved by pipelining. Send multiple frames before receiving first ack

Uses a sequence of numbers to lable each frame. Sends many frames then if an ack is missed re send everything from that frame onwards

Similar to go back N ARQ but only resend the missed frame

Parity bit. Is thr number of 1s even of odd? Easy but unreliable

CRC cyclic redundancy check. Result is held in a checksum part of the frame. Calculated by sender and receiver to check same answer.

Use a FLAG byte value to mark it. If a flag occurs in the actual data use and escape byte. And also escape escape bytes in the data and so on.

MAC manages access to and fron the physical medium. It is part of the link layer. Is sends frames to and from physical and manages collisions. Specific to the physical layer

Carrier sense multiple access with collision detection

Used by original wired ethernet

Like a telephone conversation. Sender listens to see if media is busy, when free sender starts to send and will stop if collisions occur. Pause before restarting if a collision does occur.

CSMA/CA instead CA is collision avoidance.

Instead of listening for clear, waits for an acknowledgement from the ap to determine if the frame was successfully sent.

Heterogeneity means there's no one decided way. E.g. different programming languages, different OS.

Open systems can be extended e.g. adding more computation or storage resources or adding additional services. This can be difficult to achieve

Scalable systems can handle a significant increase in either the number of resources or the number of clients. Without loosing too much performance, cost, causing bottle necks, etc.

Need to be able to: detect, mask, tolerate, and recover from failures.

Let the user perceive the system as a whole instead of broken up? I think?

Need to meet deadlines, depends on availability of resources. QoS would guarantee available resources even for high workload

The communicating Entities

The communication paradigms

The roles and responsibilities

And the placement (within the physical distributed infrastructure)

Partitioning:

+ fault tolerant, load balancing

- need to ensure consistency

Replication:

+ no consistency overhead

- no real fault tolerance

Splitting functionality into groups/ layers. E.g. client server would have presentation, application, data

Presentation- users and view controls

Application- Application server

Data- database manager

I skipped all the pros and cons of different teiring levels. Go back if there's time

When each process is roughly the same and thre is no clear permanent leader.

When a cluster is performing a complex task with close collaboration

When the system has many distributed data writes and requires good consistency

Systems easy for humans to design because concurrency is in single place

Reduces partial failure modes

Single place for logs and metrics

Improve performance costs by providing a single consistent cache if data

Efficient because it can inform other systems about changes

Efficient because it can inform other systems about changes

Termination- algorithm must stop in finite time once leader selected

Uniqueness- only one process considers itself leader

Agreement- all processes know who the leader is

One process is the leader and all others know the leaders identifier

All processes participate and eventually are elected to receive leaders identifier

Sync can guarantee safety and liveness async can not

1) process decides election needed. Makes itself participant. Sends election message left

2)when get election msg, compares msg ID and its own. If msg is greater it forwards it.

If msg is less:

If it is not participating yet it forwards the msg but with its own ID and participates

If it is participating is shallows the msg

If the msg ID is its ID it is the leader. Sends elected msg with its ID left and stops participating.

3) receieve elected msg, stop participating, notes the ID. If not its own forwards msg on.

The participant flag triggers a process stop election messages with lower IDs but election msgs with higher IDs will pass.

Aka just one ends up finishing.

Worst case N(N-1)/2 additional messages

Yes. Only the process with highest ID can be selected

??yes??

Every process participates and receives the elected message

Extra elections are stopped

System is synchronous

Message delivery is reliable

Processes may fail any time

But failed processes are detected

Each process knows the ID and address of all other processes

1) when process P recovers from failure or the current coordinator fails, p does this:

If P has the highest process ID it sends a coordinator msg to all other processes and becomes coordinator

Otherwise P broadcasts election msg to all processes with higher ID than it

2) if P receives no Answer msg after sending an election msg then it becomes coordinator

3) if P does receive answer from process with higher ID it just waits to hear the coordinator msg. Restarts process after timeout

4) if P receives election msg from lower ID it sends Answer back. If it has not already started election it starts one.

5) if P receives coordinator msg the sender is the coordinator.

Not always!

A lower ID process always yields to a higher ID one. But failure of a process may lead to two coordinators...

Yes!

Every process participates and knows the coordinator at the end. Multiple concurrent elections does not change outcome.

Network layer has small packet size and unreliable, out of order, delivery

Application layer is more readily available across range of devices

A correct process will eventually deliver the message IF the multicastor doesn't crash

Only group members receive messages sent to the group. Duh???

Integrity- a correct orocess delivers a message m at most once

Agreement- if a correct process delivers message m then all other correct processes in group with eventually deliver m

Validity- if a correct process multicasts m then it will eventually deliver m

Therefore all together ensure liveness

Initialize set received as empty

Send a message.

All received the message including sender

When a message delivered

If not already received add to received set

Then multicast the message (unless was og sender)

Then deliver the message to the receiving process

Inefficient. O(N^2) mesagea for every multicast. Not practical for large groups.

Og sender sends to 3 random processes

When anything receives a msg for the first time, forwards it on to 3 random processes

High probability of reaching all processes

Tries to establish a delivery order for messages, unlike e.g. reliable multicast.

FIFO- if m1 and m2 sent by SAME SENDER whichever is send first must be delivered first

Casual- if a multicast happens before another it must be delivered before the other

Total order- if m1 is delivered before m2 to a process then m1 must be delivered before m2 to all processes in group.

I skipped all the algorithms for the 3 ordered multicasts. Hopefully just vuagely knowing what they are is enough!?!?

Do at least learn that if the leader fails in TO multicast the whole thing fails

Physical clock synchronisation

1 client process requests the time from a clock server

2 clock server responds with time

3 client receives response and calculates the synchronised clock time which is server time plus half round-trip time.

Assumes each machine node in network doesn't have an accurate time source of doesn't possess a UTC server

1 an individual node is chosen as the coordinator using a leader election

2 coordinator requests time from each node using Cristian's algorithm

3 coordinator calcualtes adverage time difference

4 adverage time difference is added to the coordinators clock

5 the coordinators current time is Then broadcast over the current network

1 ignore outliers when averaging

2 if coordinator fails a 2nd leader should have been pre chosen to reduce down time

3 broadcast relative inverse time difference instead of final time to reduce latency in network

Network time protocol

Time sync protocol that runs across Internet

uses Stratum level (hierarchy of time servers) 0-15 indicates decices distance to the reference clock

E.g. Stratum 0 is high precision devices e.g. atomic clocks, GPS, radio clocks

Stratum 1 is attached to a 0

S2 is synced over network to a S1

S3 synced over network to S2... and so on

Counts events that occur rather than physical time

Each node has a counter that increments on every local event

When a message is sent the value t is sent with it

When a message is received if t is higher than local t, local t is moves forward to relieved t and incremented

They can define total order

They can define casual order

With two events even if one is lower t than the other you can't tell which happened before, or if they were concurrent

Allow detection of concurrent events

Assumes N nodes in system

Vector timestamp of a is V(a)=<t1,t2,,,,tn>

Where ti is number of events observed by note Ni

Nodes increment local timestamp each event

And attach timestamp to each message

Recipients of messages merge timestamp into their local vectors

Only one processes is in a CR at a time

Freedom from deadlock, at least one process can take an action and enter a CR

Every process trying to enter a CR must eventually succeed

Access to CR should happen in a fair order e.g. FIFO

Process 3 requests token to access CR

Token is granted

P2 requests token

P2 added to coordinators queue

P1 requests token

P3 releases token

P0 grants token to P2, removes P2 from queue

Server ensures grant is only sent after release is received

Queue ensures only one process can enter CR

So yes!

Server ensures grant is only sent after release is received

Queue ensures only one process can enter CR

So yes!

Server maintains queue so all processes eventually gain access

So yes!

Server maintains queue so enter CR in order. But can't ensure happened-before ordering if system is asynchronous

So yes for synchronous systems

P0 has token, its queue is empty

P0 releases token to p1

P1 accesses the critical process oldest item in queue

Removes oldest item in queue

P1 releases token to P2And so on. So if a node needs CR it puts the process in its queue and does it when it gets the token. If it gets the token with an empty queue it just passes it on

And so on. So if a node needs CR it puts the process in its queue and does it when it gets the token. If it gets the token with an empty queue it just passes it on

And so on. So if a node needs CR it puts the process in its queue and does it when it gets the token. If it gets the token with an empty queue it just passes it on

There is only one token so only one can enter CR at a time

Deadlock free because one token

So yes!

Every process gets equal access as token passed around

So yes!

Not fair as order is based on ring and location of token when starting

Each node has one parent. Child can only send requests to parent. Each node has a FIFO queue of requests.

If a node- n, is not holding the token wants CR it passes a request to its parent- j

If the Js queue is empty it moves the child- n- into its queue then sends a request to its parent- k, for the token

If Js queue is not empty just adds the child- n, to the queue

When K, that has the token, receives a request it sends the token to J and sets J as its parent

When J receives the token it forwards the token to n, J must issue a request to n to get the token back

The swapping basically means the node with the token is always the root of the tree.

Only one process can hold the token

Deadlock impossible

So yes!

Algorithm can cause starvation as it uses a greedy strategy where a site can execute the CR when getting a token even if its request is not the top of the queue

So no!

Algorithm can cause starvation as it uses a greedy strategy where a site can execute the CR when getting a token even if its request is not the top of the queue

So no!

Everyone is allowed to hold the token, non greedy strategy

Is what notes said but I thought it was greedy?!?? We will just say yes because idk

Site is any device running the algorithm

All sites have a queue

Request msg contains ID and timestamp

When a site wants CR

It broadcasts to all other sites

All sites add it to their queue+ respond IF

- it itself is not currently wanting the CR

- it itself is lower priority based on time

Otherwise they will just respond

Requesting site waits for all responses to be positive and then uses CR

When done with CR sends any deferred response messages ifself

If this doesn't make sense the slides do!

If a process is in CR it can't respond until it leaves and processes can't join until getting all responses.

Lowest timestamp always goes first

So yes!

Total ordering of timestamps ensures each request will eventually get all replies

So yes!

Clocks ensure fair ordering

So yes!

Centralised

Ring

Raymond's

Lamport's

Ricart Agrawala

Maekawa's

Please just go over this it's too much to write on a flashcard

Processes can only vote for one other at a time so only one process can get enough votes to enter CR

Very easy to deadlock

E.g. 2 send request at same time

So no!

No! But can be introduced using vector clocks to determine the order of requests

A process to achieve agreement on a single value among distributed processes

Less than a third. Aka for N malicious generals must have 3N+1 total

All correct processes must correctly set their value and have decided on the same value

all N processes TOmulticast their proposed value

Then for example all processes could then just take the first delivered by TOmulticast

This is because TO guarantees all processes see messages in the same order!

This also works the other way around so a solved consensus algorithm could be used to implement TO by consensusly deciding the next message each time.

Assume basic multicast guarantees delivery of messages to correct processes

Works in rounds with a timeout each time to detect failure

Round 1: deliver proposed value, store all received values that round.

Subsequent rounds: only deliver a value from the previous round, save that rounds, and repeat

Final round: choose value based on selection criteria. (I assume like, pick highest?)

For F crashes you need at least F+2 processes and F+1 rounds

Can't detect crashed processes

Can't use timeout to detect missing msg

Can not guarantee consensus, only to a certain probability of reaching one

It's almost exactly how the cw works

It's almost exactly how the cw worksExcept responses to requests are stored so that if a request comes on that's already been executed it doesn't execute again and just sends the response

Also primary is a data store itself chosen by leader election

Consistency- all replicas of a data object are always in the same state

Availability- requests are served as long as at least one server is available

Partition tolerance- data store keeps working even if servers are partitioned

CAP theorem says it is impossible to achieve all three, at most 2 can be had

Can't have true consistency but can have eventual consistency!

This is done with a partially synchronous system. In synchronous periods servers reconcile data objects and replicas to make consistent.

In asynchronous periods read operations may not give up to date data

Eventually data will be consistent.

Can't have true consistency but can have eventual consistency!

This is done with a partially synchronous system. In synchronous periods servers reconcile data objects and replicas to make consistent.

In asynchronous periods read operations may not give up to date data

Eventually data will be consistent.

These don't have partition tolerance so assume partitions can't happen.

But that's kind of impossible as network partitions can ways happen.

So CA systems aren't really an option

Can be measured in different ways, throughput, latency, availability

There is a point where adding servers stops improving throughput.

Used by CP approaches

Requires global ordering of updates

When updates are committed replicas need to reach agreement on global ordering

Used by AP systems

No global ordering

More relaxed guarantees on consistency- I.e. eventually consistent

One replica is considered primary

Clients communicate with primary

Any others are backups

If primary fails backups take over

Leader election picks new primary

Clients communicate with group of services (replicas)

When a client writes to a replica the update is propagated to a with TOmulticast

Any write update is IMMIDIATELY available to read. Like the system is a single store

Impossible on distributed systems as requires instant messaging.

No guarantee for how long consistency will take, just eventually.

But an application must be able to tolerate the lack of consistency

Also conflicts may occur so requires a way to solve that e.g. global consensus on answer, roll back, or delegate to application

Addresses weakness of eventual consistency

Adds that if any two replicas have received the same set of updates in any order they will be in the same state

Does not require waiting for network communication.

Can use casual multicast for updates

Use CRDT to manage concurrent updates

Operation based CRDTs

On write only broadcasts opperation

On recieve broadcast apply operation

Often used in collaborative editors

State based CRDTs

On write broadcast full state

On receive broadcast merge states

E.g. grow only counter

Quorum is a subset of replicas dynamically selected during opperations

Clients read from a read quorum and write to a write quorum

The quorums of both types intersect to insure consistency

Skipped notes on peer to peer. I think it's mostly guessable haha

Process crashes

Channel omission failures

Message out of order

R alone has no safety e.g. lost messages are undetected

RR detects issues like server crash, lost msgs, using timeouts. But reply history (if exists) will grow unbounded.

RRA does all the above and also but reply history can be kept shorter by discarding replies that have been acknowledged

R alone has no safety e.g. lost messages are undetected

RR detects issues like server crash, lost msgs, using timeouts. But reply history (if exists) will grow unbounded.

RRA does all the above and also but reply history can be kept shorter by discarding replies that have been acknowledged

Provides high level communication paradigm used in OS. Assumes lower level exists e.g TCPIP or UDP

Used to implement client server systems

To make remote prcedure calls as much like local procedure calls as possible. There should be no difference in syntax.

Only differences are stuff like failure rate, latency, call by reference unsupported

Maybe- no fault tolerance

At least once- retransmit request messages

At most once- above but also filter duplicates and retransmit replies

Describes a RPC interface in a langue specific way.

Enables communication between software components e.g. in different languages

Defines structures and types

One example is Sun RPC which uses UDP and at least once semantics

The object oriented equivalent of RPC

Client calls a method on a remote object as if it were local

Uses interfaces

built on request reply protocols.

If the lang has garbage collection then the distributed object needs to coordinate with it.

Therefore a module implementing distributed garbage collection is needed

This is usually based on reference counting

Used for distributed garbage collection

When a remote object ref is created and sent the ref count is incremented

When the remote ref is no longer needed by the remote process the ref count is decremented.

I skipped the section on Java RMI...

a set of related sequential operations that is guaranteed by the server to be atomic in the presence of multiple clients and server crashes.

Properties if database transactions intended to guarantee data validity

Atomicity- transactions are all of nothing

Consistency

Isolation- transactions don't interfere with eachother

Durability- transactions effects are saved permanently

Objects must be recoverable.

This is to support transaction durability and atomicity after a crash.

Synchronisation of opperations in different transactions is necessary to support isolation.

Concurrent execution of transactions is allowed if it produces the same effect as if they were done serial. Aka they ate serially equivalent

When working concurrently can be issues e.g. setting a value to the read+100 but in between the read and update a different process changed the value. Now whatever that different process did is essentially lost.

Good in slides!

Reads happening around writes are inconsistent if happen one side of the other of the write.

Not entirely sure on this one tbh

If their combined result depends on the order they are executed.

E.g. Read and write conflict but two reads dont

Find the conflicting operations! E.g. Read and write of the same object.

For each group, for each opperation in the group note which process came first.

For them to be serially equivalent the same process must always be first.

Before object is accessed it is locked. Only the transaction it is locked for can access it now. Lock is removed when transaction completes.

Can cause deadlocks

Maintains consistency

Assumes conflicts between concurrent transactions are infrequent

Read- each data item read is associated with a timestamp or version num

Validation- transactions recheck data items. Compare recorded timestamp and current ones. If all match proceed if not roll back

Write- data items are written to and get new timestamp or version

Multiple transactions try to write to one thing

One succeeds but then is aborted

Object is left in an inconsistent state