lecture1.md

#Lecture 1#

##Distributed Systems## A system in which hardware or software components located at networked computers communicate and coordinate their actions only by message passing
A distributed system is a collection of independent computers that appear to the users of the system as a single computer.
A distributed system is a collection of autonomous computers linked by a network with software designed to produce an integrated computing facility.

##Distributed Systems vs Computer Networks## Computer Network: An interconnected collection of autonomous computers able to exchange messages based on protocols. Network entities are visible and they are explicitly addressed (IP address). Networks focuses on packets and routing.

Distributed System: existence of multiple autonomous computers is transparent to the user. Distributed systems focus on applications.

##Characteristics##

• Parallel activities - Autonomous components executing concurrent tasks
• Communication via message passing - No shared memory
• Resource sharing - Printer, database, other services
• No global state - No single process can have knowledge of the current global state of the system
• No global clock - Only limited precision for processes to synchronise their clocks

##Design Challenges##

• Heterogeneity
• Openness
• Security
• Scalability
• Fault tolerance
• Concurrency
• Transparency

###Heterogeneity### Variety and Difference

• Computer hardware
• Operating Systems
• Communication Architectures
• Programming Languages
  Solution?: Middleware: Additional software layer to mask heterogeneity.

###Openness### The characteristic that determines whether the system can be extended and re-implemented in various ways

• Every services is equally accessible to every client (local or remote)
• It is easy to implement, install and debug new services.
• Users can write and install their own services.
• Standard interfaces and protocols (internet communication protocol) should be published.

###Security### Security of information resource

• Confidentiality - Protection against disclosure to unauthorised individuals
• Integrity - Protection against alteration or corruption
• Availability - Protection against loss of access whether circumstantial or a malicious denial of service attack

###Scalability### The system should remain efficient even with a significant increase in the number of users and resources connected

• Control performance loss (number of users & resources should be controlled)
• Avoiding performance bottlenecks
• Preventing software resources running out

###Failure Handling### Failures in DS are partial (some component fails while others continue to function)

• Detection - Checksums are used to detect corrupted data in a message/file
• Masking/hiding - Failed message retransmission. Data can be written to a pair of disks so that if one is corrupted, the other may still be correct
• Tolerance - Exception handling (e.g., timeouts when waiting for a web resource)
• Redundancy - Redundant routes in network

###Concurrency### Handling several simultaneous requests for a resource

• Shared objects/resources must guarantee correctness in a concurrent environment
• Synchronisation is required

###Transparency###

##Fallacies##

• The network is reliable
• Latency is zero
• Bandwidth is infinite
• The network is secure
• The topology doesn’t change
• There is one administrator
• Transport cost is zero
• The network is homogenous

lecture2.md

#Lecture 2#

##Types of Distributed Systems##

• Distributed Computing Systems
• Distributed Information Systems
• Distributed Pervasive Systems

Many distributed systems are configured for High-performance computing(Cluster computing, grid computing).

##Cluster Computing## Group of high-end systems connected through a LAN

• Homogenous - Same OS, near identical hardware
• Sing - (Definition goes here)

##Grid Computing## Lots of nodes from everywhere

• Heterogeneous
• Dispersed across several organisations
• Can easily span a wide-area network
• To allow for collaboration the grids generally use virtual organisations.
• Virtual organisations are groups of users (ID’s) that allow for authorisation on a resource allocation.

###Architecture for Grid Computing Systems###

• Fabric layer - provides interfaces to local resources at a specific site
• Connectivity layer - consists of communication protocols for supporting grid transactions, in addition, it will contain security protocols to authenticate users & resources
• Resource layer - responsible for managing shared resources
• Collective layer - deals with handling access to multiple resources and typically consists of services for resource discovery, allocation and scheduling of tasks onto multiple resources and data replication
• Application layer - consists of the applications that operate within a virtual organisation and which make use of the grid computing environment

##Transactions## A transaction is a collection of operations on the state of an object that satisfies the following properties:

• __A__tomic: All operations either succeed, or all of them fail.
• __C__onsistency: Only valid data will be written.
• __I__solation: Concurrent transactions do not interfere with eachother
• __D__urability: After the execution of a transaction, its effects are made permanent.

Nested Transation: Transaction constructed from a number of sub-transactions. Designed for performance gains and programming simplicity.

Transaction Processing Monitor: The data involved in a transaction is often distributed across several servers. A TP Monitor is responsible for coordinating the execution of a transaction.

##Enterprise Application Integration## A TP monitor works fine for database applications, but in many cases, the applications needed to be separated from the databases they were acting on. Instead, what was needed were facilities for direct communication between applications:

• Remote Procedure Call (RPC)
• Remote Method Invocation (RMI)
• Message-Oriented Middleware (MOM)

##System Architectures##

• Centralised Architectures - Client/Server
• Decentralised Architectures - Peer-to-Peer Systems “P2P”
• Hybrid Architectures - Client-Server architectures are combined with P2P solutions

##Two Tiered Model## *Thin Client - Client(User Interface), Server(Application, Data) *Fat Client - Client(User Interface, Application), Server(Data)

##Three Tiered Model##

##Horizontal vs Vertical Splitting## Vertical distribution: placing logically different components on different machines (multitier architecture) Horizontal distribution: a client or server may be physically split up into logically equivalent parts; each operating on its own share of the complete data. Replication and Clusters

##Client-Server Model## ###Advantages### Centralisation: access, resources, and data security are controlled through the server
Scalability: any element can be upgraded when needed
Flexibility: new technology can be easily integrated into the system

###Disadvantages### Single point of failure - if the server fails the system will come to a halt
Traffic congestion on the network - (number of simultaneous client requests to a server) can cause a server to become overloaded and unable to service client’s requests

lecture3.md

#Lecture 3#

##Middleware## The glue that holds client/server applications together Software which allows an application to interoperate with other software, without requiring the user to understand and code the low-level operations required to achieve interoperability.

With synchronous systems, the requesting system waits for a response to the request in real time.
Asynchronous systems send a request but do not wait for a response in real time – the response is accepted whenever it is received.

##Remote Procedure Call (RPC)## A procedure is a section of a program that performs a specific task (same as routine, function). Call a procedure in a program running on a remote machine, while hiding communication details from the programmer.

• How do we make this invisible to the programmer?
• What are the semantics of parameter passing?
• How do we bind (locate, connect to) servers?
• How do we support heterogeneity (OS, language)?

###Local Procedures###

###Remote Procedures###

###Stubs### Stubs make it look like a local function call, but actually use a client and server.

###Components & Interactions###

1. Client procedure calls client stub in a normal way
2. Client stub builds message, calls local OS
3. Client's OS sends message to remote OS
4. Remote OS gives message to server stub
5. Server stub unpacks parameters, calls server
6. Server does work, returns result to the stub
7. Server stub packs it in message, calls local OS
8. Server's OS sends message to client's OS
9. Client's OS gives message to client stub
10. Stub unpacks result, returns to client

###Async/sync RPC###

##Remote Method Invocation (RMI)## Remote objects” can be thought of as an expansion of the RPC mechanism (to support OO systems). RMI allows a Java program on one machine to invoke a method on a remote object.

The RMI compiler creates proxies and skeletons. Common organisation of a remote object with client-side “Proxy”. The “skeleton” can be thought of as the “server stub”. RMI registry used for interface lookup.

RMI and RPCs differ in two fundamental ways:

• RPCs support procedural programming; only one procedures or function could be called. While, RMI is object-based system, it support invocation of methods on remote objects.
• Parameters in RPC are ordinary data representation, but with RMI it is possible to pass objects as parameters.

##Message-Oriented Middleware (MOM)## As a communications mechanism, RPC/RMI is often inappropriate. For example: what happens if we cannot assume that the receiving side is “awake” and waiting to communicate? Also: the default “synchronous, blocking” nature of RPC/RMI is often too restrictive. Messaging is needed.

Communication using messages.
Messages stored in message queues
They support persistent, asynchronous communications.
Only guarantee: your message will eventually make it into the receiver’s message queue.

###Models### ####Persistent Communication#### Messages are stored by the communication system as long as it take to deliver it to the receiver.

####Transient Communication#### A messages is stored in the communication system only as long as the sending and receiving application are executing, if problems occur, the message is simply discarded e.g. network router – discard message if it can’t be delivered next router or destination.

###Properties of MOM###

• Asynchronous interaction
• Client and server are loosely coupled
• Messages are queued
• Typically, transport can take minutes (hours?) as opposed to seconds/milliseconds
• Good for application integration
• Support for reliable delivery service
• Keep queues in persistent storage
• Processing of messages by intermediate message server(s)

lecture4.md

#Lecture 4#

##Message Oriented Middleware (MOM)##

###Architecture### Messages are “put into” a source queue.
They are then “taken from” a destination queue.
Obviously, a mechanism has to exist to move a message from a source queue to a destination queue.
This is the role of the Queue Manager.

Often, there’s a need to integrate new/existing apps into a “single, coherent Distributed Information System (DIS)”. In other words, it is not always possible to start with a blank page – distributed systems have to live in the real world. Problem: different message formats exist in legacy systems (cooperation and adherence to open standards was not how things were done in the past). It may not be convenient to “force” legacy systems to adhere to a single, global message format (cost!?).
It is often necessary to live with diversity (there’s no choice).

###Message Brokers### The general organisation of a message broker in a message-queuing system – also known variously as an “interface engine”

##Event-Based Middleware (Publish/Subscribe)## An Event-based Middleware is a middleware for large-scale distributed systems that provides scalable and efficient publish/subscribe communication between components. It also addresses traditional middleware requirements, such as usability, interoperability, administrability and extensibility.

###Types of Clients###
Publishers - information producers that publish data in form of events (messages) Subscribers - information consumers that receive the data express

Event Service notifies interested subscribers of published events

###Properties###

• Asynchronous communication
• Publishers and subscribers are loosely coupled
• Many-to-many interaction between Publishers and Subscribers
• Scalable scheme for large-scale systems
• Publishers do not need to know subscribers, and vice-versa
• Dynamic join and leave of nodes

###Event Subscription Mechanisms### Channel – based subscription Topic – based subscription Content – based subscription

##Transmission Modes## ###Asynchronous Transmission### Asynchronous transmission mode – the data stream is transmitted in order, but there’s no timing constraints placed on the actual delivery (e.g., For example typing keyboard characters, file transfer).

Each group (usually 8-bit) is sent as a unit. The sender handles each group independently. The receiver cannot predict when the next group will arrive.

To alert the receiver for a new group coming and finishing, a start bit and stop-bit are used. There may be a gap between each byte.

###Synchronous Transmission### The bit stream is combined into longer ᾿frame of multiple bytes.
To send bits one after another without start or stop bits or gaps. It is the responsibility of the receiver to group the bits.
Time generated by the sender’s clock is sent along with data so that the receiver can keep its clock synchronised with that of the sender throughout a long transmission

###Isochronous Transmission### In real-time audio and video, in which uneven delays between frames are not acceptable, synchronous transmission fails. For example, TV images are broadcast at the rate of 30 images per second; they must be viewed at the same rate. If each image is sent by using one or more frames, there should be no delays between frames. For this type of application, synchronisation between characters is not enough; the entire stream of bits must be synchronised.
There’s a maximum and minimum end-to-end delay (known as “bounded jitter”). Isochronous network is designed to accept and send data at a fixed rate, “R” For example, an isochronous mechanism designed to transfer voice operates at a rate of 64,000 bits per second Known as “streams” – isochronous transmission mode is very useful for multimedia systems.

####Types of Streams#### Simple Streams – one single sequence of data, for example: voice Complex Streams – several sequences of data (sub-streams) that are “related” by time. Think of a movie, with sound and pictures, together with sub-titles

##Summary## Middleware is an important abstraction for building distributed systems
Remote Procedure Call
Object-Oriented Middleware
Message-Oriented Middleware
Event-Based Middleware
Synchronous vs. asynchronous communication
Scalability, many-to-many communication
Streams: a special case, useful when dealing with “temporally related data” (not easy)

lecture5.md

(Appears to be missing)

lecture6.md

#Lecture 6#

##Chord## A Scalable peer-to-peer Lookup Service for Internet Applications
Solves problem of locating a data item in a collection of distributed nodes, considering frequent node arrivals and departures Chord does not store any files! it just maintains pointers to the nodes in the Chord ring where the data associated with keys can be found
Supports just one operation: given a key, it maps the key onto a node

###Base Protocol###

• Specifies how to find the locations of keys
• How new nodes join the system
• How to recover from the failure or planned departure of existing nodes

Hash function assigns each node and key an m-bit identifier using a base hash function

ID(node) = hash(IP, Port)
ID(key) = hash(key)

###Chord Ring###

###Chord Lookups### Each Chord node needs routing information about only a few other nodes Resolves lookups via messages to other nodes (iteratively or recursively) (iterative, recursive)

####Recursive Lookup#### Every node knows its successor_

Example: node 8 try to locate key 54

Lookups are accelerated by maintaining additional routing information
Each node maintains a routing table with m entries, called the finger table
Finger [i] = successor (n + 2i-1)

#Get Sensible Info on Finger Tables#

###Applications Using Chord###

####DNS with Chord####

• Host names hashed to keys, corresponding IP addresses are values
• Routing information and host changes can be updated dynamically

####Cooperative mirroring: load balancing mechanism###

• Multiple providers of the same content
• Load is spread evenly between all hosts by mapping data blocks into hosts

lecture7.md

#Lecture 7#

##Routing## A name indicates what we seek.
An address indicates where it is.
A route indicates how we get there.

###Forwarding vs Routing### Forwarding: the process of moving packets from input to output based on: *The routing (forwarding) table *Information on packets

Routing: process by which the routing (forwarding) table is built and maintained

• Computing paths the packets will follow
• Algorithms to convert routing info to routing (forwarding) table
• Routers talking amongst themselves

###Why does it matter?###

• End-to-end performance
• Quality of the path affects user performance
• Propagation delay, throughput, and packet loss
• Use of network resources
• Balance of the traffic over the routers and links
• Avoiding congestion by balancing load
• Transient disruptions during changes
• Failures, maintenance, and load balancing
• Limiting packet loss and delay during changes
• Realising business objectives
• Maximising revenue or minimizing cost
• Avoiding paths going through untrusted parties

##Autonomous Systems (AS)## A group of networks and routers under the authority of a single administration.

##Popular Routing Protocols## Goal: distributed management of resources

• Internetworking of multiple networks
• Networks under separate administrative control Solution: two-tiered routing architecture
• Intra-domain routing (interior protocol): are used within a single autonomous system
• Inter-domain routing (exterior protocol): are used for communications between autonomous systems.

###Intradomain Routing### Routing within an AS Ignoring the Internet outside the AS.
Protocols for Intradomain routing are also called Interior Gateway Protocols (IGP’s)

Popular protocols are:

• RIP (simple, old) - distance vector routing (Bellman-Ford)
• OSPF (better) -Link state routing (Dijkstra)
• IS-IS (Intermediate System-to-Intermediate System protocol)

###Interdomain Routing### Routing between AS’s
Assumes that the Internet consists of a collection of interconnected AS’s
Normally, there is one dedicated router in each AS that handles interdomain traffic.

Routing protocols:

• BGP - Policy-based path vector routing

###Distance Vector Routing (DVR)### Completely decentralised
No node has complete information about the costs of all network links
Gradual calculation of path by exchanging information with neighbours

Each node constructs a one-dimensional array containing the “distances” or “costs” to all other nodes (as it relates to its knowledge) and distributes it to its immediate neighbours.

Each node knows the cost of links to its neighbours.

If no link exists between two nodes, the cost of a direct link between the nodes is “infinity”.

####Initialisation of Tables in DVR####

#Get sensible info on Distance Vector Routing# #And finish this lecture!#

lecture8.md

#Lecture 8#

##Domain Name Server##

A good naming server should provide

• Scalability
• Decentralised maintenance
• Robustness, fault-tolerance
• Global scope
• Names mean the same thing everywhere

Distributed database implemented in hierarchy of many name servers
Decentralised control and management of data
Core Internet function implemented as application layer protocol used by hosts and name servers
Communicate to resolve names (name/address translation)

###Levels### (Root Zone, Top Level, Second Level, Third Level, Fourth Level)

Root name server knows authoritative servers for particular subdomains

• Hierarchy organises authoritative name servers

Authoritative name servers store parts of the database
Names assigned to authoritative name servers

• For a host, authority stores that host’s IP address, name
• Responds to queries for host’s IP address
• Perform name/address translation for that host’s name

Reserving a domain gives you control of entry in root name server for particular names

There is one primary server for a domain, and typically a number of secondary servers containing replicated database, used for load sharing and reliability.

##DNS Resolution (Lookup)##

###Iterative Name Resolution.### Server responds with as much as it knows (i.e. name of server to contact next)
“I don’t know this name, but ask this server”
Client iteratively queries additional servers

###Recursive Name Resolution### Server goes out and searches for more info on behalf of the client (recursive)
Only returns final answer or “not found”
Puts burden of name resolution on contacted name server
Heavy load? - Root server implosion

###Typical Resolution### Client (resolver) does recursive request to local name server Resolvers are the clients that access name servers.
The resolver handles:

• Querying a name server
• Interpreting responses (which may be resource records or an error)
• Returning the information to the programs that requested it.

Local name server does iterative requests to find name
Local name server has knowledge of root servers

The name resolver queries each name server (at each layer) in an iterative fashion.
Note: the client is doing all the work here (and generating a lot of traffic, too).

###Cache Name Server### DNS responses are cached - Improve the efficiency of the DNS by reducing the DNS traffic across the network DNS negative queries are cached - Save time for nonexistent sites, e.g. misspelling Name servers can't cache data forever - Cached data expires (The administrator of the zone that contains the data decides on a time to live (TTL) for the data).

lecture9.md

#Lecture 9#

##Clocks##

A DS is a collection of computers that are spatially separated and do not share a common memory
The processes executing on these computers communicate with one another by exchanging messages over communication channels
The messages are delivered after an unpredictable transmission delay
It is fundamentally impossible to all node to have exactly the same clock time

###Problems with Internal Clocks###

• Each node has its own private physical clock
• Physical clocks are hardware devices that count oscillations on a quartz.
• Frequency of oscillations varies with temperature and different rate on different computers
• Clock drift: difference in reading due to different oscillation rate of crystal (~ sec/day).
• Clock skew: the instantaneous difference between the readings of and two clocks.

###Christian's Algorithm###

• Assume one machine (the time server) has WWV receiver and all other machines are to stay synchronised with it.
• Each machine send a message to the time server asking for the current time.
• The server responds ASAP with the current time CUTC
• The client sets its clock to CUTC

####Problems#### Minor problem: results from the delay introduced by the network request/response: Latency, best estimate (T1-T0)/2
If the interrupt handling time, I, is known, (T1-T0 -I)/2
Major problem: time never run backward
If the client clock is fast, CUTC will be lower than client’s current time.
Solution: Introduce changes gradually; slow down client clock by adding less time per tick.

####Disadvantages#### Single point of failure: if Server fails, no synchronisation is possible!
Faulty or corrupt time servers may reply with spurious time values!
An impostor may deliberately reply with incorrect times and wreak havoc.
Solution: Cristian advocated the use of groups of time servers to avoid some of these problems.

###Berkley Algorithm### Assumes no machine has an accurate time source
Aim: synchronise clocks of a group of machines as close as possible (also called internal synchronisation)
Assumes no machine has an accurate time source (i.e., no differentiation of client and server)
Obtains average from participating computers
Synchronises all clocks to average

1. The master machine asks all the other machines for their clock values.
2. The machines answer and the master computes the average.
3. The master tells everyone how to adjust their clock.

To eliminates readings of faulty clocks
Fault-tolerant average: average over the subset of clocks that differ by up to a specified amount
What if master fails?
Elect another master

###Network Time Protocol (NTP)### Cristian‘s method and the Berkley algorithm are both designed for primarily use in intranets.

The Network Time Protocol was designed for use in the Internet right up from the start.

Cristian‘s method and Berkley algorithm both synchronise against one time server.

The NTP synchronises against many time servers.

NTP Enable clients across Internet to be accurately synchronised to UTC despite message delays

It is built on the Internet Protocol (IP) and User Datagram Protocol (UDP)

Provide a reliable service that can survive lengthy losses of connectivity.

This means having redundant paths and redundant servers.

####Hierarchical Structure#### The NTP service is provided by a network of servers located across the Internet

Primary servers are connected directly to a time source
e.g. a radio clock receiving UTC, GPS

Secondary servers are synchronised with primary servers

The servers are connected in a logical hierarchy called a synchronisation subnet

####NTP Subnet#### Computer local clock are synchronised to a number of Time Servers and peer computer The set of these computers and Time Servers is known as the Synchronisation Subnet Stratum 0: Composed by Atomic Clocks, GPS Clocks 1st stratum: Primary time server-machines connected directly to stratum 0 2nd stratum: machines synchronised from 1st stratum machine, .....etc

####Determining Time####

• Timestamps exchanged between the server and clients (subnet peers)
• A knows T4 - T1 from its own clock
• One way trip delay is approximately 1/2 total.
• B reports T3 and T2 in response to delay.
• A computes total round: (T4 - T1) - (T3 - T2)

One way trip delay is approximately 1/2 total:

((T4 - T1) - (T3 - T2)) / 2

*B's clock at T4 reads approximately:

T3 + ((T4 - T1) - (T3 - T2)) / 2 = ((T4 - T1) + (T2 + T3)) / 2

• Thus, the clock offset between B and A at T4 is:

(((T4 - T1) - (T3 - T2)) / 2) - T4 = ((T2 - T1) + (T2 + T3)) / 2

###Modes of Operation### Multicast (Low accuracy)

• For high speed networks
• High Accuracies are not required
• Time Servers send periodic NTP broadcasts
• Determine the time based on an assumed delay
• Time servers provides synchronization, but do not accept NTP messages from clients

Procedure-Call (middle accuracy)

• Server responds to client requests with its actual timestamp (Cristian’s algorithm)
• applicable where higher accuracy is needed, or where multicast is not supported by the network’s hard- and software

Symmetric (high accuracy)

• Used to synchronise between the time servers (peer-peer)
• Two modes of operation: Active Mode: For servers in the high levels of the stratum (near the leaves)
  Passive Mode: For servers in the low levels of the stratum (near the root)