Networks

Be aware of inherent distributed system issues (notes on distributed systems) - what do these mean?  Examples of 
how protocols deal with these issues:
	concurrency, 
	partial failure, 
	asynchrony, 
	impossibility of determining global state
Be aware of Internet issues
	decentralization
	scale
	interoperation
	extensibility
	maintainability
How do these impact network and protocol design??
	Why do we have multiple redundant paths?
	Why do we construct a spanning tree?  What makes it hard?
	Why do we need to find out who has an IP address?  
	Why do we use switching?
	Why do we use routing?
	What problems does ARP/TCP/UDP/DHCP have to solve?
Standard problems:
	Leader election - why?
	Agreement
	Broadcast communication - why?
	Routing
	Failure recovery
	Resource allocation - exactly once allocation
Performance issues
	Definitions: bandwidth, throughput, latency, delay, measurement
	Response time
	Throughput
	Utilization
	Congestion

Principles
	Filling the pipe
	Encapsulation
	
Layering - principle and what are the layers, what do they provide
Protocols
	Link layer - ARQ, ARP, STP, Learning Bridge Algorithm, Sliding Window
	Network layer - IP, RIP, distance vector vs shortest path routing algorithms
	Transport layer - UDP, TCP
		TCP reliability, flow control, congestion control
	Application layer - DHCP

========================================================================================
Asynchronous Network

Definitions:
I/O automaton - sig, states, start states, transitions, tasks
executions, execution fragments - alt. states and actions
traces - external actions only
fair execution / trace - finite, infinite and inf steps in each task, infinite and inf. states with task not enabled
compatible automata: empty int of locally-controlled
composition: union of actions, c. p. of states, transitions, union of tasks

hiding
implements (as in A implements B)
invariants
trace properties 
	safety
	liveness
simulation relation

System composed of processes and channels

========================================================================================

1) Reliable FIFO
2) Lossy channel (loses messages): internal delete action
3) Duplicative channel (duplicates messages): model Queue as a MSet and add each message a random number of times
4) Unordered channel (messages delivered out of order): model Queue as a Set

Should allow correct exec as well as incorrect ones

==========================================================================

Be able to prove

Simulation relation used in hierarchical proofs

Be able to define a simulation relation eg for FIFO implementing a lossy channel 

Be able to use induction or case analysis

Remember to think through what a protocol does!!

=============================================================================

Specs and Algorithms:

Reliable FIFO Channel - both as automaton and axioms
be ready to define varioius kinds of channels
Leader Election 
BFS
Broadcast
Broadcast/convergecast
Determining network diameter
Cisco spanning tree/min-weight spanning tree

===============================================================================