- 12/03/2009 - Class on 12/08/2009 - Last class
- Mutual exclusion in a distributed system.
- Elections: the Bully Algorithm.
- Consistent cuts and checkpoints
- Final Exam will be on Thursday, December 17, from 10:30 to 12:30 in
our usual classroom
- 12/01/2009 - Class on 12/03/2009
- The Google approach, in particular the Map-Reduce framework
- 11/25/2009 - Class on 12/01/2009
- The talk by Professor Kai Hwang on Cloud Computing is on Blackboard
- Java for adults
- Physical clocks.
- Logical clocks
- Vector clocks
- FIFO and Causal ordering of messages
- Why updates to replicated stores have to be
applied in the same order at all sites (at least for updates
on shared items)
- Class evaluation
- 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
- 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
- 11/17/2009 - Class on 11/19/2009
- Starting on Security
- Secret key cryptography (DES, AES, IDEA), public key cryptography
- 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
- 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.
- 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
- 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.
- 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
- 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 [
- 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
- 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,
- 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.
- 10/04/09 - Class on 10/08/09
- 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
- We are at last talking about
- 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
- 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
- 09/22/2009 - Class on 09/24/2009
- Computing with Graphic Processing Units - CUDA
- Virtualization and Virtual Machines
- Third 10 minute
- 09/17/2009 - Class on 09/22/2009
- Visit by our alumna at Vanguard
- On September 29 there is an important
- 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
- 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
- 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.
- 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.
- 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
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,
- 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
- 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
- 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
- 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
- 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.
- 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
- 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
- Note the
directives I give to
my TA for
grading your homeworks.
- Note that I have already posted your