CS 417 Exam 2

Spring 2009

    Part I – 25 Points

  1. 5 points
    The town of Karlsfeld in Bavaria just completed repair on the clock in its town center. The clock now needs to be set but nobody has the time so they send Otto on a walk to the neighboring town, Munich, to get the time.

    When Otto leaves, the time on the town clock reads 2:00 (this was wrong). He arrives in Munich a few hours later and notes that the clock in Munich reads 11:20. He has some lunch and leaves for home, noting that the time on the clock is now 12:10. When he arrives back in Karlsfeld, the time on the town clock is now 8:40. Using Cristian's algorithm (SNTP), to what time should the clock be set?

  2. 4 points
    How does operating in disconnected mode with a Coda file system differ from normal operation? What happens when the client reconnects to the network?
  3. 4 points
    What does a callback promise under AFS do?
  4. 4 points
    What do vector clocks do that Lamport clocks cannot?
  5. 4 points
    What is the difference between global time ordering and total ordering?
  6. 4 points
    Explain how the token ring algorithm ensures that starvation does not occur even though the algorithm does not guarantee first-come, first-served processing of requests?

    7. PART II – 75 points – 3 points each

    For each statement, select the most appropriate answer. You may omit one question. Please indicate your choice clearly.

  7. How does an AFS client manage to perform long term caching and ensure that the cached files are not out-of-date?
    (a) It periodically checks with the server.
    (b) It checks with the server whenever a process opens a file.
    (c) The server informs each client if any files have been modified.
    (d) It is guaranteed to have the latest version of a file because the file is downloaded whenever a process opens a file.
  8. The purpose of CIFS oplocks is to:
    (a) provide file locking in a distributed environment.
    (b) ensure that only one client at a time can access a file.
    (c) ensure that local file access gets priority over remote access.
    (d) control how clients cache file data in a distributed environment.
  9. Which of the following is not a valid key size under Triple-DES (normal DES is 56 bits)?
    (a) 56 bits
    (b) 112 bits
    (c) 168 bits
    (d) 224 bits
  10. Which is not a type of multicast?
    (a) Reliable
    (b) Atomic
    (c) Global
    (d) Unreliable
  11. Which is not a valid token type under DFS?
    (a) Read
    (b) Write
    (c) Status
    (d) Block
  12. What is hoarding?
    (a) Resetting timestamps of all events in Lamport's algorithm.
    (b) In AFS, a term for user caching of entire volumes.
    (c) In CODA, a term for user directed caching.
    (d) Flooding the network with queries to locate a file on another server.
  13. Two events, a and b, are considered concurrent if:
    (a) they take place at the same time.
    (b) there is no causal relationship such that a→b or b→a.
    (c) they occur on different processors.
    (d) events a and b have different Lamport timestamps.
  14. Which multicast technique ensures that all clients get the data, even if the sender dies partway through the multicast and needs to be rebooted?
    (a) Atomic multicast.
    (b) Totally ordered reliable multicast.
    (c) Causally ordered reliable multicast
    (d) Sync-ordered reliable multicast.
  15. Sync ordering requires that all messages sent prior to the sync have to be processed before the sync is complete:
    (a) in the order that they were sent.
    (b) but the order is unimportant.
    (c) in the order of timestamps on the messages.
    (d) in the same order by all receivers.
  16. IP multicast is an example of:
    (a) totally ordered reliable multicast.
    (b) unordered, unreliable multicast.
    (c) unordered, reliable multicast.
    (d) totally ordered unreliable multicast.
  17. Which event is concurrent with the vector timestamp (1, 1, 0, 1, 1, 0, 0, 0)?
    (a) (1, 1, 0, 1, 1, 1, 0, 0)
    (b) (1, 0, 0, 1, 1, 0, 0, 0)
    (c) (1, 1, 0, 1, 0, 0, 0, 0)
    (d) (1, 1, 0, 1, 0, 0, 0, 1)
  18. A distributed hash table relies on:
    (a) mapping a hash of a query key onto a machine that holds the corresponding data.
    (b) speeding up the time to compute a hash by distributing the work among several machines.
    (c) forwarding a search from one machine to another until the machine with the needed part of the table is located.
    (d) flooding a network with a request key and waiting for a machine that holds the hash of the key responds.
  19. OpenID does not provide which of the following services?
    (a) Single Sign On (SSO).
    (b) Identity attribute exchange.
    (c) Authentication.
    (d) Authorization.
  20. What is the main communication method between the user, ID Provider, and Relying Party (service’s web site) in OpenID?
    (a) Client-side inter-domain communication.
    (b) Point-to-point HTTP.
    (c) HTTP redirect.
    (d) RESTfull API.
  21. In OpenID, what key does the ID Provider use to sign its assertion?
    (a) Its own private key.
    (b) A symmetric key that has been communicated with the Relying Party (service’s web site) during the course of the protocol.
    (c) The symmetric key that is given to the ID Provider by the user during user registration.
    (d) The public key of the Relying Party (service’s web site).
  22. In Lamport’s mutual exclusion algorithm, a process can access a resource when it:
    (a) sees it has the lowest timestamp in its list of requestors who want that resource.
    (b) sends a multicast request to access the resource and everyone else responds.
    (c) requests and receives a token granting access to that resource.
    (d) sends a request to a central server and receives a grant message.
  23. A ring election algorithm relies on:
    (a) building up a message containing the IDs of all live processes and selecting the one with the largest process ID.
    (b) circulating a token through a logical a ring of processes. The current holder of the token is the leader.
    (c) sending messages to all processes ahead of the current process in the ring to have them decide on the leader.
    (d) all processes arranged in a logical ring contact a coordinator to identify the leader.
  24. Sequential consistency in a cache coherent shared memory system requires that:
    (a) a read cannot take place until a previous write operation is acknowledged by all members caching the page.
    (b) a read operation cannot be issued until a previous read operation has completed.
    (c) a distributed directory must be present to keep track of page ownership.
    (d) only one process can write to the page but there could be multiple readers.
  25. Release consistency improves performance by:
    (a) delaying propagating any or invalidations until the end of the critical section.
    (b) allowing multiple processes to modify memory at the same time.
    (c) managing individual objects (regions of memory) within the shared memory space.
    (d) having memory write operations immediately invalidate all other cached copies of the page that was modified.
  26. Which of these statements about rotor machines is false? A rotor machine:
    (a) is less vulnerable to a frequency analysis attack than a monoalphabetic substitution cipher. (T)
    (b) is a form of a polyalphabetic substitution cipher . (T)
    (c) is a form of a transposition cipher. (F)
    (d) is a stream cipher. (T)
  27. A one-time pad is provably secure but:
    (a) is computationally prohibitively expensive for normal use.
    (b) is a block cipher and not a stream cipher.
    (c) requires a key that is as long as the message.
    (d) takes about 100× longer to encrypt a message than it does to decrypt.
  28. How does a symmetric encryption algorithm differ from a public key algorithm? A symmetric algorithm:
    (a) uses the same algorithm to decrypt as to encrypt whereas a public key system uses different algorithms.
    (b) uses one key to encrypt and decrypt while a public key algorithm requires two different keys.
    (c) takes the same time to encrypt as it does to decrypt while a public key algorithm takes much longer to encrypt.
    (d) uses a secret algorithm, whereas a public key algorithm is published. For the following questions, select the file system that best describes the statement.
  29. It extends HTTP to support file system operations
    (a) DFS
    (b) Berkeley xFS
    (c) WebDAV
    (d) GFS (Google File System)
  30. It uses a model of one master server that holds file metadata and multiple replicated servers that hold data chunks.
    (a) DFS
    (b) Berkeley xFS
    (c) WebDAV
    (d) GFS (Google File System)
  31. It is a serverless distributed file system; all data is distributed among peer nodes.
    (a) DFS
    (b) Berkeley xFS
    (c) WebDAV
    (d) GFS (Google File System)
  32. It uses tokens to control client-side operations and caching.
    (a) DFS
    (b) Berkeley xFS
    (c) WebDAV
    (d) GFS (Google File System)