CS 417 Exam 2
Fall 2007
- 5 points
How does a replicated Coda server discover that it has out-of-date files? - 9 points
Suppose the round-trip delay of sending a message to a time server and getting a response back is R. The time value returned by the server is TS. The time at the client when it sent the request is TC.
(a) Express the formula for the new time on the client, T, using Cristian’s algorithm.T =
(b) If the best-case round-trip delay to the server is TB and the error of the clock on the server is ±ES. What is the error on the client after it synchronizes its clock with the server?E = ±
- 5 points
Vector timestamps assume that every participating process knows the group membership from the start. A new process cannot just jump in and send a message to anyone in the group. Propose a modified algorithm that does not require a priori knowledge of the group. Specifically, explain how a timestamp is defined and what happens when a message arrives from a previously unseen process. [Hint: don’t use a central coordinator.] - 7 points
(a) Prove that a cryptographic hash function, no matter how good, will always be vulnerable to collisions.
(b) Why is this not a huge concern? - 5 points
What is the purpose of the client modification log in Coda? - 10 points
(a) How can Alice generate a digital signature for a message that anybody can validate?
(b) How can Alice generate a digital signature for a message that only Bob can validate? - 8 points
(a) How can Alice pass a symmetric key securely to Bob using only symmetric cryptography and a trusted third party (Trent)?
(b) How can Alice pass a symmetric key securely to Bob using public key cryptography? - Which file system is best suited for concurrent file sharing:
(a) NFS
(b) AFS
(c) Coda
(d) CIFS - An oplock, or opportunistic lock, in CIFS is:
(a) Requested by a client to ensure that it gets exclusive access to a region of the file.
(b) Granted by the server and tells the client how it may cache file data.
(c) Requested by the client to share a region of a file with another client.
(d) Requested by the client to grab an exclusive lock on a file when the opportunity arises, even if the process has to wait to get the lock. - Berkeley’s xFS project demonstrates that:
(a) A distributed file system can be built on a serverless peer-to-peer infrastructure.
(b) A highly scalable filesystem can be designed through distributed caching.
(c) A fault-tolerant file system can be built using replicated servers.
(d) A client can relay file system requests through other clients rather than contacting the server directly. - A two-phase commit protocol implements:
(a) Atomic multicast.
(b) Reliable multicast.
(c) Unreliable multicast.
(d) Disjoint multicast. - Events on process P1 have the following Lamport timestamps:
a: 1, b: 3, c: 4.
Events on process P2 have the following Lamport timestamps:
d: 1, e: 2, f: 5.
Which set of events is definitely causally related? Choose the best answer.
(a) a, b, c
(b) a, e, b, c
(c) d, e, b, c, f
(d) It is impossible to tell whether any of the events are causally related. - A linear compensating function:
(a) Speeds up or slows down the rate at which a clock ticks.
(b) Adjusts a clock in steadily decreasing intervals until it asymptotically approaches the correct time.
(c) Adds a constant offset to the value of the system clock.
(d) Compensates for the irregularities of a quartz oscillator and ensures that the system clock ticks at a constant rate. - A synchronization subnet is:
(a) A dedicated subnet on an IP network that is used for synchronizing processes.
(b) A dedicated subnet on an IP network that is used only for time synchronization.
(c) Any subset of the synchronization network.
(d) The set of all systems that are time servers. - Which mutual exclusion algorithm requires the least amount of network traffic for groups of over 1,000 machines:
(a) Centralized
(b) Token Ring
(c) Ricart & Agrawala
(d) Lamport’s - IP multicast provides the following message ordering:
(a) Totally-ordered
(b) Causally-ordered
(c) Sync-ordered
(d) Unordered - With entry consistency:
(a) Only the data associated with the synchronization object is acquired and made consistent at the acquirer.
(b) All shared data is acquired and made consistent at the acquirer.
(c) Any shared data is made consistent at the acquirer after completing the release operation.
(d) Any shared data is made consistent at all cached nodes immediately after it is modified. - Which of the following is not a substitution cipher
(a) Alberti
(b) Vigenère
(c) Staff
(d) Rotor machine - The Diffie-Hellman algorithm is best described as one that:
(a) Uses public key cryptography to allow a user to send a session key securely to another user.
(b) Uses public key cryptography to transmit a session key and symmetric cryptography to encrypt the conversation.
(c) Uses symmetric cryptography to establish a session key between two parties.
(d) Allows two users to derive the same key. - Frequency analysis is used to:
(a) Identify the scrambling sequence in a transposition cipher.
(b) Identify the substitution alphabet in a substitution cipher.
(c) Identify the key in a symmetric encryption algorithm.
(d) Identify the key in a public-key encryption algorithm. - The time on a client is 11:18:00. The time on the server is 11:21:00. Using the Berkeley algorithm, the client’s clock will be adjusted to:
(a) 11:18:00
(b) 11:19:30
(c) 11:21:00
(d) 11:22:30 - False sharing in a distributed shared memory system refers to :
(a) Unrelated data that is used by two processors being mapped to the same memory page.
(b) Creating the illusion of a shared page by moving it between processors on demand.
(c) The directory entry for a page showing multiple copysets that no longer hold the page.
(d) Extraneous pages being cached on the system. - Which vector timestamp is concurrent with (2, 1, 3)?
(a) (2, 1, 4)
(b) (3, 2, 4)
(c) (1, 0, 2)
(d) (1, 2, 3)
Part I – 36 Points
PART II – 51 points
For each statement, select the most appropriate answer.
