CIS4307: Introduction to Distributed Systems and Networks Class Log

• 12/10/2008 - Class on 12/16/2008 - Final Exam
  • Final Exam will be on Tuesday, December 16, from 2:00 to 4:00pm in our usual classroom

• 12/04/2008 - Class on 12/09/2008 - Last class
  • The Google approach, in particular the Map-Reduce framework
  • Visit by Avi Freedman
  • Final Exam will be on Tuesday, December 16, from 2:00 to 4:00pm in our usual classroom

• 12/02/2008 - Class on 12/04/2008
  • Logical clocks
  • Vector clocks
  • FIFO and Causal ordering of messages
  • Multicast messages with the causal property
  • Totally ordered multicast
  • Consistent cuts - Chandy-Lamport: consistent global states
  • Tenth 5-minute test

• 11/26/2008 - Class on 12/02/2008
  • Digital signatures
  • Need for a Public Key Infrastructure - Certificate Authorities and Certificates
  • Mutual exclusion in a distributed system.
  • Elections: the Bully Algorithm.
  • Physical clocks.
  • Final homework

• 11/21/2008 - Class on 11/25/2008
  • Returned and discussed the ninth 5-minute test
  • Shamir's algorithm for sharing a secret
  • PGP: hybrid=RSA+IDEA
  • Hash functions: MD5, SHA-1,..
  • Integrity and non Repudiation
  • Nonces
  • Mutual Authentication and exchange of Session Key
  • Slides on Authentication from textbook including authentication in Kerberos
  • Zero-Knowledge Proofs and Authentication

• 11/19/2008 - Class on 11/20/2008
  • Starting on Security
  • Secret key cryptography (DES, AES, IDEA), public key cryptography (RSA)
  • Turing lecture by Rivest-Shamir-Adleman.
  • Block cyphers
  • Block chaining
  • One-time pad
  • Diffie-Hellman key exchange
  • Steganography, watermaking
  • Stream cyphers
  • Ninth 5-minute test

  11/13/08 - Class on 11/18/2008

  • Returned and discussed 5-minute test
  • An interesting article about how we become experts
  • Atomicity in a distributed system: Two Phase Commit protocol.
  • Flat vs nested transactions
  • Transaction servers.
  • Remote Procedure Calls (RPC). Read textbook, pages 68-77, 375-381.
  • RPC: passing parameters, serialization.
  • RPC: representation issues, failure semantics.
  • An old RPC system
  • Java Remote Method Invocation

• 11/11/08 - Class on 11/13/2008
  • Serializability Theorem.
  • Two-Phase Locking protocol.
  • Automatic lock management.
  • Using timestamps for serialization
  • Atomicity on a single system: WriteAhead log, Undo-Only or Redo-Only. Checkpoints and restart.
  • Eight 5-minute test.

• 11/06/08 - Class on 11/11/08
  • Returned and discussed the second midterm.
  • Transactions and ACID properties.
  • Problems when without transactions: lost updates, dirty reads, cascading aborts, ..
  • Serializability and conflicting operations.
  • Two interesting articles Frequently Forgotten Fundamental Facts about Software Engineering, Game-Changing Advances from Computing Research, and two interesting diagrams

• 10/30/08 - Class on 11/06/08
  • Second Midterm

• 10/30/08 - Class on 11/04/08
  • Returned and discussed seventh 5-minute test
  • Supernetting (CIDR - classless internet domain routing).
  • Private IP Addresses, Network Address Translation
  • Execution times: user, system, elapsed, wall-clock. Profiling: gprof.
  • Virtual Private Networks, Tunnelling
  • The select systems call, non-blocking IO
  • Fourth Homework

• 10/29/08 - Class on 10/30/08
  • Headers for IP, UDP, TCP.
  • Source Routing, Virtual Circuit Routing, Packet Routing.
  • Routing: Switching vs. Routing.
  • Forwarding using a Routing Table.
  • IP addresses: class A, B, C, D, E. Standard addresses.
  • Subnetting.
  • Seventh 5-minute test

• 10/24/08 - Class on 10/28/08
  • Returned and discussed the sixth 5-minute test.
  • Automatic Repeat Request (ARQ).
  • Performance of ARQ
  • OSI and TCP/IP network architectures.
  • You may find useful for your homework this program
  • CST JobFair and Career Center

• 10/21/08 - Class on 10/23/08
  • Signals vs. data: Fourier Analysis, Nyquist Sampling Theorem
  • How much data can we "pump" thru a channel. Measuring the Signal-to-Noise ratio in decibels.
  • Elementary coding theory: how much we can "compress" a message: entropy
  • Error detection and correction : parity, checksum, CRC, digests, forward error recovery and Hamming distance;
  • Sixth 5-minute test

• 10/16/08 - Class on 10/21/08
  • Returned and discussed the fifth 5 minute test
  • Using echosigserver to echo back what sent to server. And the corresponding client to send lines to it.
  • Using telnet to connect to a server [blocked by most firewalls]
  • End-to-End principle. Network neutrality.
  • Introduction to networks: some characteristics.
  • Autonomous systems.
  • Delays: Transmission, propagation, queueing.
  • Simplex, half-duplex, duplex.
  • Round-trip delay. Delay-Throughput product. Bit length.
  • Operating in promiscuous mode - Packet sniffers: Ethereal.
  • Unicast, multicast, broadcast, anycast.

• 10/14/08 - Class on 10/16/08
  • setsockopt, getsockopt, and fcntl
  • Using sockets: 3-way handshake, 4-way handshake.
  • Here is information on how to use a library of functions that are useful in doing your homeworks. There is also a reference to code for a web server (developed for a course at CMU) which we will use in future assignments. More information about this code is in the Bryant and O'Hallaron textbook used in cis72 and cis207 (page 777-845).
  • Structure of HTTP requests and responses - in texbook pages 560-565
  • Viewing HTTP headers
  • The tiny web server
  • HTTP: non-persistent connection, persistent connection, persistent connection with pipelining

• 10/09/08 - Class on 10/14/08
  • Concurrent servers: task based, thread based, thread pools, finite state machine - the select system call.
  • Clients can be iterative or concurrent (select system call).
  • More distinctions on servers; stateless vs stateful implementations, Horizontal and Vertical architectures. In the case of the Vertical Architecture, we use the alternative name of 3-Tier Architecture.
  • Distinctions in interactions: pull vs push, stateless vs stateful, synchronous vs asynchronous, time-assured vs time-insensitive, message vs stream.
  • Identifying connection endpoints: IP address + port.
  • Introduction to sockets: stream vs datagram, connection-oriented vs connectionless.
  • Little endian vs big endian data representation. An example
  • Basic functions: socket, connect, bind, listen, accept, read, write, close.
  • Kinds of sockets: client socket (in Java, Socket), listening socket (in Java, ServerSocket), connected socket (in Java, Socket).
  • Third homework

• 10/08/2008 - Class on 10/09/08
  • Returned and discussed the first Midterm.
  • Returned and discussed last week's 5 minute test.
  • More about synchronous/asynchronous, blocking/non-blocking send/receive

• 10/02/2008 - Class on 10/07/2008
  • First Midterm

• 09/30/08 - Class on 10/02/08
  • We are at last talking about distributed systems!!
  • What are distributed systems? Some slides from Tanenbaum-VanSteen [Slides from Tanenbaum-VanSteen are on Blackboard] and from Kschemkalyani-Singhal
  • We have reviewed some hardware terminology, like SISD, .. NUMA, clusters. (Chapter 1 in text)
  • Distributed Systems and some wonderful concepts like Openness, Scalability, Transparency, Security, Reliability (High Availability), ..
  • Role played by Middleware in the architecture of distributed systems. Examples of services provided by middleware: RPC/RMI, naming, security, transactionality, persistence, .. Service Oriented Architecture (SOA): HTTP, SOAP, UDDI,WSDL,XML,..
  • But services are not just horizontal/pervasive, across different systems, like security or persistence. They can also be vertical/special, like a service from Google for search, or from Amazon for pricing, or a verifier of charge requests.
  • Client-Server, 3(n)-tier architecture.
  • Fourth 5 minute test.

• 09/28/2008 - Class on 09/30/08
  • Returned and discussed the third 5 minute test.
  • Saturation and bottlenecks
  • The Utilization Law: u = Ts/Ta.
  • Little's Law: N = a*T
  • Seen the impact of queue sizes on the queueing delay at a router (Little's law) - transmission delay, propagation delay.
  • The M|M|1 single server queueing system. Given the formula T = T_s/(1 - u).
  • Used the study of round robin scheduling to review again the concept of weighted average.
  • Is it better to have two servers of equal power or one server with double power?
  • Could we have answered questions of lab1 using what we now know about performance evaluation? See the answer
  • The Five Minute rule.
  • Speedup in an n processor system. Amdhal's Law. Using common sense: the Law of Diminishing returns.
  • You may find interesting the following discussion.
  • This is what Berkeley thinks about future parallel computing research
  • The last lecture of professor Randy Pausch.

• 09/23/2008 - Class on 09/25/2008
  • Question: do all threads in a process share the same signal blocking mask? NO, each thread can establish its own mask.
  • Question: do all threads in a process share the same handler for a signal? YES.
  • Question: Do threads share the same standard C buffer?
    The answer is yes. But one can play tricks: the unix call "openfd" goes from file descriptor (int), to file pointer (FILE *) and creates a new buffer, as demonstrated by this example. Thus if you like in each thread you can have your own buffer to the terminal. That will be safe as long as you write single lines. If you want to write atomically a block of lines you will need to use locks.
  • Signals.
  • Be sure when you hand in homework to put in each file your name and the name of the file (no social security number). And of course document your code.
  • We do performance evaluation. Performance indicators: throughtput, response time, latency, utilization, queue sizes, ..
  • Third 5 minute test.

• 09/19/2008 - Class on 09/23/2008
  • Returned and discussed the second 5-minute test
  • Starting with threads
  • Threads: m:1, 1:1, m:n implementations (user vs kernel threads).
  • Read in textbook from page 70 to page 79.
  • Why do threads have each its own stack?
  • Pthreads: Mutex locks.
  • Condition variables. Conditional critical regions.
  • Implementing a protected bounded buffer with locks and condition variables

• 09/16/08 - Class on 09/18/08
  • The pipe call
  • popen, launching a process and being able to read from its standard output, or to write to its standard input (either one or the other). In java instead it is possible to launch a process and to read and/or write to its standard input and output. Of course in Unix, by using fork, exec, dup2, pipe we can program to achieve the same effect.
  • A film about teaching and understanding.
  • Shared memory
  • Memory mapped IO, the sendfile system call.
  • Internal structure of Unix files, data blocks vs directory blocks (metadata).
  • Why a "write once policy" may be a good way to write to files.
  • Stable storage
  • 5-minute test

• 09/11/08 - Class on 09/16/08
  • Returned and discussed 5 minute test.
  • Remember that there are different kinds of storage associated with variables, automatic, static, dynamic.
  • We are reviewing Unix system calls. For concurrency issues see also Chapter 13 (pages 848 - 903) in the cis72-207 textbook (Bryant-o'Hallaron)
  • Review of process control calls (fork, wait, waitpid, exit, exec)
  • Review of file I/O (open, read, write, lseek, ioctl, close). Blocking vs.non-blocking I/O, synchronous vs non-synchronous write.
  • dup2
  • Control blocks for files.
  • You can go from FILE* to file descriptor with fileno, in the opposite direction with fdopen. But greatest care must be taken when using a file with both the C and Unix API.
  • Why do we buffer I/O?

• 09/09/08 - Class on 09/11/08
  • I know that you are overloaded with work, but here is a place where you can read about what is happening in our industry. It is pretty interesting and it can be read fairly quickly. It is given to us by ACM.
  • Readers and Writers Problem.
  • We have lamented that using semaphores, or spinlocks, is not easy.
  • We have introduced the concept of "monitor" and condition variables.
  • We have discussed the "Dining Philosophers Problem".
  • We have shown an implementation of a protected bounded buffer as a monitor. This is the classic "Producers and Consumers Problem".
  • We have discussed the implementation of monitors.
  • Transactional Memory and Haskell
  • Next we will re-examine Unix topics - process control, files, signals, threads
  • First 5-minute test.

• 09/07/08 - Class on 09/09/08
  • We worry about how to implement critical regions. We discuss interrupts, interrupt disabling.
  • We introduce the TestAndSet hardware instruction. CompareAndSwap and lock-free operations. We see how to implement spinlocks. See some of their defects and some of their merits. We discuss how we can speed up spinlocks in a shared memory multiprocessor, see the Cache Coherence Problem and Snooping Caches.
  • We see that spinlocks can be executed in user mode but that they suffer of a number of problems, like busy waiting, deadlocks, unfairness, convoys, priority inversion.
  • Remember that processes can be in various states, Ready, Running, Blocked, and there are transitions among these states.
  • Semaphores as a way to avoid at least busy waiting and deadlocks. We see that the implementation of semaphore methods has critical regions, thus require some other locking mechanism, like spinlocks. Semaphores may give origin to the Priority Inversion problem.
  • Using the CompareAndSwap instruction to avoid the use of locks.
  • Futexes, to build semaphores that mostly avoid kernel mode.
  • We distinguish three types of semaphores, mutual exclusion semaphores, blocking semaphores, and counting semaphores.
  • Ways to use each kind of semaphore. For example we use blocking semaphores to enforce the precedence constraints in precedence graphs, counting semaphores for multiple occupancy problems, and mutual exclusion semaphores for critical regions.

• 09/03/08 - Class on 09/04
  • Atomic actions - read, write
  • Memory Consistency Models. Program Order and the Sequential Memory Consistency Model
  • Assuming we have atomic elementary actions, we understand concurrent computations in terms of their interleavings. Determinacy/race-conditions.
  • Bernstein's sufficient conditions for determinacy.
  • Precedence graphs.
  • Our 5-minute tests will be on Thursdays (unless told differently in advance). So our first test will be next Thursday.
  • Synchronization.

• 08/01/08 - Class on 09/02
  • We go over the syllabus, describing the objectives of the course, identifying textbook, contact hours, TAs, grading rules, etc.
  • We overview the course's content.
  • A general discussion of the course.
  • First homework.
  • The first lab is this week on Wednesday at 8:40am in room 207

• 08/01/08 - Before Class on 09/02
  • This is hard to do, since probably you will not look here until after the first day of class. But if you can, try to review what you learned in previous classes, in particular cis68, cis72, cis207, cis223.
  • Start to review your knowledge of C and of the Unix system.
  • Test your knowledge entering cis307 by answering the following questions.
  • Note the directives I give to my TA for grading your homeworks.
  • Note that I have already posted your first homework.