• 11/19/2009 - Class on 11/24/2009
    • Returned and discussed the ninth 5-minute test
    • Hash functions: MD5, SHA-1,..
    • Integrity and non Repudiation, Digital Signatures
    • PGP: hybrid=RSA+IDEA
    • Nonces
    • Access to protected pages with HTTP
    • Logging-in locally and remotely
    • Slides on Authentication from textbook
    • Zero-Knowledge Proofs and Authentication
    • Need for a Public Key Infrastructure - Certificate Authorities and Certificates

  • 11/17/2009 - Class on 11/19/2009
    • Starting on Security
    • Secret key cryptography (DES, AES, IDEA), public key cryptography (RSA)
    • Turing lecture by Rivest-Shamir-Adleman.
    • Block cyphers
    • One-time pad
    • Block chaining
    • Stream cyphers
    • Diffie-Hellman key exchange
    • Shamir's algorithm for sharing a secret
    • Steganography, watermaking
    • Ninth 5-minute test

  • 11/14/09 - Class on 11/17/09
    • Returned and discussed eight test
    • 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
    • Two interesting articles Frequently Forgotten Fundamental Facts about Software Engineering, Game-Changing Advances from Computing Research, and two interesting diagrams

  • 11/10/09 - Class on 11/12/09
    • Grice's Conversational Maxims
    • 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.
    • Atomicity in a distributed system: Two Phase Commit protocol.
    • Eight 5-minute test.
  • 11/09/09 - Class on 11/10/09
    • Returned and discussed the second midterm.
    • Transactions and ACID properties.
    • Problems when without transactions: lost updates, dirty reads, cascading aborts, ..
    • Serializability and conflicting operations.
    • Fourth Homework

  • 10/29/09 - Class on 11/05/09
    • Second Midterm

  • 10/29/09 - Class on 11/03/09
    • Returned and discussed the seventh 5-minute test.
    • 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.
    • Supernetting (CIDR - classless internet domain routing).
    • Private IP Addresses, Network Address Translation
    • Virtual Private Networks, Overlay networks, Tunnelling

  • 10/27/09 - Class on 10/29/09
    • OSI and TCP/IP network architectures.
    • Headers for IP, ICMP, UDP, TCP.
    • Seventh 5-minute test

  • 10/22/09 - Class on 10/27/09
    • Returned and discussed the fifth test
    • Error detection and correction : digests, forward error recovery and Hamming distance;
    • Automatic Repeat Request (ARQ)
    • Performance of ARQ

  • 10/20/09 - Class on 10/22/09
    • Computing in the large
    • HTTP: non-persistent connection, persistent connection, persistent connection with pipelining
    • Delays: Transmission, propagation, queueing.
    • Round-trip delay. Delay-Throughput product. Bit length.
    • Operating in promiscuous mode - Packet sniffers: Ethereal.
    • Simplex, half-duplex, duplex.
    • Unicast, multicast, broadcast, anycast.
    • Using telnet to connect to a server [blocked by most firewalls]
    • 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
    • Sixth Test

  • 10/16/09 - Class on 10/20/09
    • Returned and discussed last week's test.
    • The question about 4-way handshake [ server, client ]
    • Client-Server, 3(n)-tier architecture.
    • 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.
    • Synchronous/asynchronous, blocking/non-blocking send/receive
    • Structure of HTTP requests and responses - in texbook pages 560-565
    • Viewing HTTP headers
    • The Tiny Web Server and the networking library.
    • Third homework

  • 10/13/09 - Class on 10/15/09
    • Introduction to sockets: stream vs datagram, connection-oriented vs connectionless.
    • Basic functions: socket, connect, bind, listen, accept, read, write, close.
    • Using sockets: 3-way handshake, 4-way handshake.
    • Kinds of sockets: client socket (in Java, Socket), listening socket (in Java, ServerSocket), connected socket (in Java, Socket).
    • setsockopt, getsockopt, and fcntl
    • Fifth Test

  • 10/08/09 - Class on 10/13/09
    • Returned and discussed first Midterm
    • Networks - End-to-End principle. Network neutrality.
    • Autonomous systems.
    • Identifying connection endpoints: IP address + port.
    • Little endian vs big endian data representation. An example

  • 10/04/09 - Class on 10/08/09
    • First Midterm

  • 10/04/09 - Class on 10/06/09
    • Returned and discussed last week's test.
    • The Law of diminishing returns
    • We have reviewed some hardware terminology, like SISD, .. NUMA,
    • Introduction to networks: some characteristics.

  • 09/29/09 - Class on 10/01/09
    • The Five Minute rule.
    • Speedup in an n processor system. Amdhal's Law. Using common sense: the Law of Diminishing returns. Gustafson-Barsis Law.
    • The performance of a few systems components.
    • You may find interesting the following discussion.
    • This is what Berkeley thinks about future parallel computing research
    • 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
    • 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.
    • Fourth 10 minute test.

  • 09/24/2009 - Class on 09/29/09
    • Returned and discussed the third 5 minute test.
    • The select system call
    • We do performance evaluation. Performance indicators: throughtput, response time, latency, utilization, queue sizes, .., saturation, 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 = Ts/(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?

  • 09/22/2009 - Class on 09/24/2009
    • Computing with Graphic Processing Units - CUDA
    • Virtualization and Virtual Machines
    • Third 10 minute test.

  • 09/17/2009 - Class on 09/22/2009
    • Visit by our alumna at Vanguard
    • On September 29 there is an important Job Fair
    • Returned and discussed the second 5-minute test
    • Unix Signals
    • Computing with Graphic Processing Units - CUDA
    • Homework 2

  • 09/15/09 - Class on 09/17/09
    • 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.
    • Shared memory
    • Memory mapped IO, the sendfile system call.
    • Stable storage
    • Starting with threads
    • Threads: m:1, 1:1, m:n implementations (user vs kernel threads).
    • Read in textbook from page 70 to page 79.
    • Pthreads: Mutex locks.
    • Condition variables. Conditional critical regions.
    • Implementing a protected bounded buffer with locks and condition variables
    • Signals.
    • 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.
    • 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.
    • 10-minute test

  • 09/12/09 - Class on 09/15/09
    • Returned and discussed 10 minute test.
    • 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?
    • 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.
    • The pipe call

  • 09/08/09 - Class on 09/10/09
    • 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.
    • We have discussed the "Dining Philosophers Problem".
    • We have discussed the implementation of monitors.
    • Transactional Memory and Haskell
    • Next we will re-examine Unix topics - process control, files, signals, threads
    • Remember
      • that there are different kinds of storage associated with variables, automatic, static, dynamic
      • not to return from a function with the address of a local variable
      • that C is not Java: here you must explicitly allocate and deallocate dynamic storage
      • that we can interpret the content of memory any way we want, so int *x can be interpreted as referencing characters by saying char *s = (char *)x;
      • that parameters are passed by value, thus if we want to modify a pointer, say char *s, passed to a function, the formal parameter must be char **a and the corresponding actual parameter must be &s.
    • First 10-minute test.

  • 09/03/09 - Class on 09/08/09
    • 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. 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.
    • 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 shown an implementation of a protected bounded buffer as a monitor. This is the classic "Producers and Consumers Problem".

  • 09/03/09 - Class on 09/03/09
    • 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 10-minute tests will be on Thursdays (unless told differently in advance). Our first test will be next week's Thursday.
    • Synchronization.
    • We worry about how to implement critical regions. We discuss interrupts, interrupt disabling.
    • We introduce the TestAndSet and CompareAndSwap hardware instructions.
    • We see how to implement spinlocks using TAS and CAS instructions.
    • CompareAndSwap and lock-free operations.
    • See some of the defects and some of the merits of spinlocks. 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.

  • 08/31/09 - Lab on 08/31/09
    • No lab today

  • 07/21/09 - Class on 09/01
    • 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.

  • 07/21/09 - Before Class on 09/01
    • 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.