CS 417 Exam 2

Spring 2008

    Part I – 26 Points

  1. 4 points
    Explain the difference between logical and physical clocks.
  2. 4 points
    What problem with Lamport clocks to vector clocks solve?
  3. 3 points
    A client's clock reads 3:20:00. The server's clock reads 3:10:00 when they synchronize using the Berkeley algorithm. Assume message delays are negligible. What is the time at the client after synchronization?
  4. 3 points
    A client's clock reads 3:20:00. The server's clock reads 3:10:00 when they synchronize using Cristian's algorithm. Assume message delays are negligible. What is the time at the client after synchronization?
  5. 6 points
    Some networks, such as cable TV Internet service, provide an asymmetric bandwidth. For example, a cable modem may provide 12 Mbps downstream service but only 1 Mbps upstream. Cristian's algorithm assumes symmetric delays to and from the server.
    (a) Reformulate the algorithm to accommodate asymmetric delays, where TS is the server's time, Ta is the time the request was sent, Tb is the time the response was received, U is the upstream bandwidth, and D is the downstream bandwidth.
    (b) You are on a network with a 9 Mbps downstream bandwidth and a 1 Mbps upstream bandwidth. Your client makes a request at 9:10:00.0 and gets a response 200 msec later. If the time on the server is 8:42:00.0, what would the time be set to on your client?
    [Note that 1000 msec = 1 sec; time is expressed as HH:MM:SS.msec]
  6. 5 points
    Explain how Alice can send a digitally-signed document to Bob and Charles such that only Bob and Charles can read the message and only Charles can validate the signature. You cannot replicate the document (assume it's huge and you wouldn't want to). Use a combination of public key and symmetric cryptography but no trusted third party in your solution.

    7. PART II – 63 points – 3 points each

    For each statement, select the most appropriate answer.

  7. The Coda distributed file system does not support:
    (a) Tokens for file locking.
    (b) Disconnected clients.
    (c) Replicated servers.
    (d) Session semantics.
  8. The purpose of DFS tokens is to:
    (a) Give the server control over which actions clients can perform and how they may cache data.
    (b) Ensure mutual exclusion is granted when servers are accessed.
    (c) Support read/write replication on servers through token exchange.
    (d) To avoid the overhead of having clients cache file data.
  9. SMB is best characterized as a:
    (a) Remote call, connection-oriented file system.
    (b) Remote call, connectionless file system.
    (c) File upload/download, connectionless file system.
    (d) File upload/download, connection-oriented file system.
  10. Opportunistic locks, or oplocks:
    (a) Tell the client how it may cache file data and attributes.
    (b) Are a first-come, first-served mechanism for locking a file.
    (c) Allow clients to grab locks on a remote file under CIFS.
    (d) Guarantee exclusive access to a file once it is open.
  11. Alice has a remote file open on her system with a Level 1 oplock. Bob tries to open the file from another system. The most likely scenario is:
    (a) Alice's oplock will be revoked and Bob will be able to share the file.
    (b) Bob's request will fail.
    (c) Bob will be blocked until Alice releases her lock.
    (d) Alice's oplock will be revoked and she will no longer have access to the file.
  12. Which of the following is not a valid description of the ACID properties of transactions?
    (a) Atomic: If a transaction cannot complete in its entirety, a subset of its operations may be visible as long as they are performed in a serial order.
    (b) Consistent: Invariants must hold after the transaction.
    (c) Isolated: If two or more transactions are running at the same time, the final result appears as if all transactions run sequentially.
    (d) Durable: once a transaction commits, the results are made permanent.
  13. At the end of the first phase of a two-phase commit protocol:
    (a) The coordinator has asked all cohorts if they have completed the transaction.
    (b) The coordinator has delivered all the prepare to commit requests to all cohorts.
    (c) The coordinator has received all agree or abort responses to a prepare to commit request.
    (d) The coordinator delivered a commit or abort directive to all cohorts.
  14. The two-phase commit protocol is an example of:
    (a) An atomic multicast.
    (b) A reliable multicast.
    (c) A causally-ordered multicast.
    (d) An unreliable multicast.
  15. A synchronization subnet is:
    (a) The collection of NTP servers on the Internet.
    (b) An IP multicast group used for clock synchronization
    (c) The set of machines addressed by an NTP server operating in multicast mode
    (d) The set of NTP servers with which you are currently synchronizing.
  16. IP multicast uses:
    (a) Unreliable multicast.
    (b) Reliable multicast.
    (c) Atomic multicast.
    (d) User-selectable reliability.
  17. False sharing in a distributed shared memory system arises because:
    (a) Unrelated data is shared between multiple systems but resides on the same memory page.
    (b) One distribute memory page is mapped onto two or more systems at the same time.
    (c) Two or more distributed memory pages are mapped onto the same system.
    (d) Bad message ordering makes it appear that data is shared when, in reality, it is not.
  18. A distributed directory in a distributed shared memory system:
    (a) Ensures cache coherence in a sequentially coherent memory system.
    (b) Allows concurrent queries and updates to a memory page.
    (c) Is necessary for systems that employ caching.
    (d) Distributes the load of looking up page owners.
  19. Concurrency control deals with:
    (a) A distributed monitoring system that allows the control of processes on different nodes.
    (b) Starting and stopping processes on a collection of computers.
    (c) Taking a sequential process and breaking it into a collection of processes to maximize concurrency.
    (d) Running processes concurrently while giving the results that would be obtained through serial execution.
  20. Compared to two-phase locking, strict two-phase locking:
    (a) Relies on a lock manager.
    (b) Avoids having transactions read uncommitted data.
    (c) Does not allow a transaction to get new locks after it has released a lock.
    (d) Is vulnerable to cascading aborts.
  21. The ring election algorithm works by:
    (a) Having all nodes in a ring of processors send a message to a coordinator who will elect the leader.
    (b) Sending a token around a set of nodes. Whoever has the token is the coordinator.
    (c) Sending a message around all available nodes and choosing the first one on the resultant list.
    (d) Building a list of all live nodes and choosing the largest numbered node in the list.
  22. Which event is concurrent with the vector clock (2, 8, 4)?
    (a) (3, 9, 5)
    (b) (3, 8, 4)
    (c) (1, 7, 3)
    (d) (4, 8, 2)
  23. If a DES key is 56 bits, a triple-DES key is:
    (a) 56 bits
    (b) 112 bits
    (c) 144 bits
    (d) 224 bits
  24. The Diffie-Hellman algorithm is:
    (a) A public key cipher .
    (b) A symmetric cipher.
    (c) A substitution cipher.
    (d) Not an encryption algorithm.
  25. Which statement about the Vigenère ciphers is not true?
    (a) It is a block cipher that uses a secret key.
    (b) It is a polyalphabetic substitution cipher.
    (c) It is a collection of Cæsar ciphers.
    (d) It attempts to be resilient to frequency analysis.
  26. A hybrid cryptosystem uses:
    (a) A combination of public key and symmetric cryptography.
    (b) A combination of substitution and transposition ciphers.
    (c) Multiple layers of encryption.
    (d) Any of the above.
  27. The Ricart & Agrawala distributed mutual exclusion algorithm is:
    (a) More efficient and more fault tolerant than a centralized algorithm.
    (b) More efficient but less fault tolerant than a centralized algorithm.
    (c) Less efficient but more fault tolerant than a centralized algorithm.
    (d) Less efficient and less fault tolerant than a centralized algorithm.

    PART III – 11 points

    For each statement, select whether it is true or false.

  28. The Simple Network Time Protocol (SNTP) uses Cristian's algorithm for synchronization.
    [True] [False]
  29. With other things being equal, a lower stratum is preferable to a high one in NTP.
    [True] [False]
  30. Resolution is a client-initiated operation in Coda to bring replicated volumes in sync.
    [True] [False]
  31. A Level 1 oplock allows a client to cache file attributes and delay writes to the server.
    [True] [False]
  32. Hoarding is a way a user to control the Coda cache on the client.
    [True] [False]
  33. Split brain refers to a situation where an election algorithm that elects two coordinators.
    [True] [False]
  34. DES is a block cipher.
    [True] [False]
  35. Berkeley's xFS is a distributed file system with no central servers.
    [True] [False]
  36. A private workspace (and shadow blocks) is used to simplify aborts and keep operations isolated during a transaction.
    [True] [False]
  37. There are less than 256 valid keys for the C?sar cipher.
    [True] [False]
  38. A hash function is a form of a restricted cipher.
    [True] [False]