CS417 Exam 2

100 points - 3.125 points each. For each statement, select the most appropriate answer.

1. Unlike Ricart & Agrawala's algorithm, timestamps are used in Lamport's mutual exclusion algorithm to:
   (a) Set a timer for a lease based on the sender's time rather than the receiver's time.
   (b) Enable a receiver to discard earlier messages that arrive out of order.
   (c) Ensure queues at all participants remain identical.
   (d) Allow a participant to see if it can have the resource by comparing its timestamp with that of a received message.
2. Which mutual exclusion algorithm does not require a client that wants a resource to send any request message?
   (a) Centralized
   (b) Token ring
   (c) Lamport's
   (d) Ricart & Agrawala
3. Chang and Roberts improves the ring election algorithm by:
   (a) Asking each client to acknowledge a message to avoid lost election messages.
   (b) Terminating concurrent elections.
   (c) Not requiring messages to be circulated among all live group members.
   (d) Using multicasts to reach the entire group at once.
4. The ring election algorithm builds a list of processes. At the end, the leader can be chosen as:
   (a) The lowest-numbered process.
   (b) The first process in the list.
   (c) The last process in the list.
   (d) Any of the above.
5. Paxos' abortable consensus means:
   (a) A proposed value may be rejected.
   (b) A client can choose to stop the consensus algorithm.
   (c) A client may reject the chosen value.
   (d) The state of Paxos can be restored to its values before the algorithm was run.
6. At the end of the first phase of the Paxos protocol, a proposer must:
   (a) Use the value that was returned by the majority of acceptors.
   (b) Propose the value that was provided by the client.
   (c) Use the value of the highest accepted proposal ID that was returned, if any were returned.
   (d) Use any value but it must be one of the proposed values.
7. Unlike Paxos, the Raft protocol:
   (a) Allows a single value to be chosen from a set of proposed values.
   (b) Allows more than one value to be chosen from a set of proposed values.
   (c) Includes group membership management.
   (d) Includes leader election.
8. In Raft, a value is considered committed when:
   (a) The leader adds the value to its log.
   (b) A majority of followers have acknowledged receipt of the value.
   (c) The next term starts.
   (d) A candidate receives a majority of votes.
9. Which of these is not an ACID property of transactions?
   (a) Atomic: All changes are performed as if they were one operation. If anything fails, they are all undone.
   (b) Consistent: Data is in a consistent state before and after the transaction.
   (c) Isolated: Intermediate states of the transaction are invisible to other transactions.
   (d) Distributed: Transactions be broken into multiple sub-transactions that span multiple systems.
10. The three-phase commit protocol was created to:
    (a) Enable participants to abort or commit after timeouts rather than wait for all systems to recover.
    (b) Ensure that the coordinator receives final acknowledgement of whether a transaction was committed or aborted.
    (c) Allow participants to reach commit consensus with each other with no need for a coordinator.
    (d) Fix the problem where some transactions commit while others abort under the two-phase commit protocol.
11. The CAP theorem tells us that:
    (a) A distributed transaction requires at least two sets of messages to get agreement to commit.
    (b) Distributed transactions must use locks to keep other transactions from accessing their data.
    (c) You can only have two out of three: consistency, atomicity, and partition tolerance.
    (d) Highly-available distributed systems will have problems with consistency.
12. The purpose of two-phase locking (2PL) is to:
    (a) Keep transactions from accessing intermediate data from other uncommitted transactions.
    (b) Keep transactions from accessing any data that was modified by other uncommitted transactions.
    (c) Increase concurrency by separating read locks from write locks.
    (d) All of the above.
13. Strong strict two-phase locking (SS2PL) improves on two-phase locking (2PL) by:
    (a) Keeping other transactions from accessing interim data from other uncommitted transactions.
    (b) Keeping other transactions from accessing any data that was modified by other uncommitted transactions.
    (c) Increasing concurrency by separating read locks from write locks.
    (d) All of the above.
14. A commit lock:
    (a) Prevents a transaction from committing until all sub-transactions commit.
    (b) Keeps transactions from acquiring read or write locks on a resource.
    (c) Releases all locks on resources that were used by the transaction.
    (d) Makes modifications on the resource permanent.
15. Multiversion concurrency control (MVCC) enables:
    (a) A transaction to create multiple versions of an object prior to committing.
    (b) Transactions to control the allowable amount of concurrency in the system.
    (c) The use of read locks separate from write locks to increase the level of concurrency.
    (d) Lock-free reads in transactions by accessing versions of data as of the start of the transaction.
16. Deadlock does not require:
    (a) An exclusive lock on a resource.
    (b) Waiting on a resource while having a lock on a resource.
    (c) The ability for a coordinator to release a process's lock on a resource.
    (d) A circular hold and wait dependency.
17. Phantom deadlocks can be avoided by:
    (a) Querying each participant for pending release messages.
    (b) Using of two-phase locking.
    (c) Using strong strict two-phase locking.
    (d) Constructing a global wait-for graph.
18. Which technique will abort a process because of deadlock?
    (a) Edge chasing.
    (b) Wait-die.
    (c) Wound-wait.
    (d) All of the above.
19. On Linux, remote files can be accessed seamlessly because:
    (a) The client module is installed as a file system type under the Virtual File System (VFS) layer.
    (b) Applications are compiled with APIs to enable them to access remote files.
    (c) The system call interface in the GNU C library (glibc) can tell if programs are trying to access remote files.
    (d) Clients always access locally cached files and do not have to interact with servers directly.
20. Which file system uses a download-upload rather than a remote access model?
    (a) NFS
    (b) Coda
    (c) SMB
    (d) GFS
21. An AFS server uses callbacks to:
    (a) Inform clients that a cached copy of their files is invalid.
    (b) Ask clients to upload the latest version of their file.
    (c) Let a client know that another client is accessing the same file.
    (d) Tell a client that another a client has released a lock on a file they want to open.
22. An SMB oplock, or lease:
    (a) Enforces mutual exclusion, so other clients cannot access the remote file.
    (b) Allows a client to perform groups of file system operations with no intervening operations from other clients.
    (c) Tells a client how it may cache data for a remote file.
    (d) Is a discretionary lock that other clients can check to see whether a client locked access to a file.
23. A client modification log (CML) in Coda is:
    (a) Used by the server to track the changes clients made to files to allow rollback.
    (b) A server-managed list of files downloaded by clients so cache invalidations can be sent if those files change.
    (c) An optimization on the server to send only the changed parts of files to clients instead of full downloads.
    (d) The list of files that were modified on a client while it was disconnected.
24. The design of Google Chubby can best be described as:
    (a) One active master with multiple replicas as backups that do not process client requests.
    (b) One master with multiple replicas, with client requests load balanced among all live systems.
    (c) A set of replicas, each holding a different part of the file system name space.
    (d) A peer-to-peer distributed hash table.
25. Chubby does not permit this operation:
    (a) Lock a file.
    (b) Read a range of bytes from a file.
    (c) Subscribe to receive notification of events, such as the modification of a file.
    (d) Delete a file.
26. Which statement is not true about the Google File System, GFS?
    (a) A file's contents can be bigger than the capacity of any one server.
    (b) Information about files is stored on a different server from file contents.
    (c) File contents can be replicated by the file system
    (d) The metadata of all the files is distributed among multiple servers.
27. The defining characteristic of a parallel file system is:
    (a) File data is replicated across multiple servers for high availability.
    (b) The file system can process multiple requests concurrently.
    (c) File contents are distributed among multiple servers.
    (d) Multiple file systems are combined together to appear as one.
28. Notification servers in Dropbox:
    (a) Were used by clients to inform servers of new files.
    (b) Provided a group collaboration feature so users could add messages about shared files.
    (c) Were an optimization to keep clients from polling.
    (d) Allowed a client to be told when its uploads have completed.
29. Consistent hashing is usually implemented by:
    (a) Using a hash function where all existing key values remain the same when the number of buckets increases.
    (b) Creating a hash function that generates a unique value for each key.
    (c) Keeping the number of buckets constant even if the hash function changes.
    (d) Having a bucket be responsible for a range of hash values.
30. A node in a three-dimensional Content Addressable Network (CAN) must know of:
    (a) 3 neighbors.
    (b) 6 neighbors.
    (c) 8 neighbors.
    (d) 12 neighbors.
31. Amazon Dynamo is called a zero-hop DHT because:
    (a) A collision-free hash function is used.
    (b) Consistent hashing allows the system to grow.
    (c) Clients know the complete set of servers and can directly contact the one that holds the data they need.
    (d) Each server node maintains a finger table that identifies other nodes.
32. Vector clocks are used in Amazon Dynamo to:
    (a) Impose a total ordering of all get and put operations in the system.
    (b) Disallow concurrent updates of the same object by choosing the earliest writer.
    (c) Determine the sequence of write operations across multiple objects.
    (d) Identify conflicting versions of the same object stored on different servers.