CS 417 Exam 2

Fall 2016

    Part I – 28 Points

  1. 6 POINTS
    What makes a message unstable? How does an unstable message become stable?
  2. 5 POINTS
    Why is a transaction log crucial in providing fault tolerance in a two-phase commit protocol?
    Hint: the answer has nothing to do with aborts.
  3. 5 POINTS
    How does Eric Brewer's CAP theorem affect the design of highly-available systems that can withstand network partitions?
  4. 6 POINTS
    How did callbacks in AFS enable it to scale to support more clients than NFS?
  5. 6 POINTS
    Under what conditions would consistent hashing be unnecessary for a distributed hash table?

  6. PART II – 72 POINTS – 3 POINTS EACH

    For each statement, select the most appropriate answer.

  7. The two-army problem illustrates that:
    Achieving reliable communication between two parties requires the use of a third party.
    You may need to use multiple levels of acknowledgements when using an unreliable asynchronous network.
    You cannot guarantee agreement when communicating via an unreliable, asynchronous network.
    An asynchronous network can be made to look like a synchronous network through the use of timeouts.
  8. In virtual synchrony, the group membership service:
    Is responsible for pinging servers to see if they are still alive.
    Is used to notify servers if a new member joins a group.
    Is a central coordinator that implements reliable multicasts.
    All of the above.
  9. A Paxos proposer may change its mind and pick a different proposal:
    If it receives a higher-numbered proposal from any acceptor.
    If it receives a different proposal number from the majority of acceptors.
    If it receives a delayed but earlier proposal from a client.
    Only after consensus has been reached.
  10. Unlike Paxos, Raft:
    Requires all requests to go through an elected leader.
    Does not require a majority of servers to agree to the proposed value.
    May not always succeed in achieving consensus even with a majority of servers functioning.
    Provides a fault-tolerant framework for consensus.
  11. To achieve consensus, Paxos requires the functioning of:
    The majority of proposers
    The majority of acceptors.
    The majority of learners.
    All of the above.
  12. Which is not an ACID property of transactions?
    Atomic. The intermediate state of a transaction is not visible.
    Consistent. A transaction cannot leave the system in an inconsistent state.
    Isolated. The net effect of concurrent transactions should be the same as if they ran in serial order.
    Distributed. A transaction is made up of sub-transactions running on multiple systems.
  13. The two-phase commit protocol uses two phases to:
    Perform a tentative commit followed by a permanent commit.
    Give a chance for a sub-transaction to request more time.
    Make sure everyone's vote is received before taking action.
    Release resources used by each sub-transaction prior to committing.
  14. The three-phase commit protocol:
    Allows a coordinator to abort all sub-transactions if any one does not respond to a vote.
    Enables a recovery coordinator to query any sub-transaction for the state of the protocol.
    Allows a participant to query another participant to decide to commit or abort if it does not hear from the coordinator.
    All of the above.
  15. Two-phase locking means a transaction:
    First checks if any other transaction holds the lock before requesting it.
    First requests a read lock, followed by a write lock only if it needs to modify the resource.
    Becomes the owner of the lock and can grant it to another transaction when it is finished.
    Cannot request a lock if it already released any lock.
  16. Unlike two-phase locking, strict two-phase locking:
    Prohibits a transaction from getting a lock unless it first checks if it is held by another process.
    Requires a transaction to get a lock for any resource it accesses.
    Ensures that other transactions cannot access uncommitted data.
    Ensures that transactions maintain serial order.
  17. Optimistic concurrency control is a technique that:
    Tries to run all transactions at once.
    Schedules transactions in an optimal sequence to avoid deadlock.
    Does not require transactions to grab locks for resources while they are working on the transaction.
    Requires that, once granted, locks will not be revoked from a transaction.
  18. The main benefit of a stateless file server design is:
    Improved consistency across multiple clients that access the same file.
    Shorter requests for higher throughput.
    Ability for increased client-side caching.
    Simplified recovery from client or server crashes.
  19. The NFS automounter:
    Automatically remounts previously used remote directories after a system crash.
    Enables an NFS server to tell a group of clients to mount specific remote directories.
    Looks at past activity on the client to figure out what remote directories should be mounted in the future.
    Avoids the overhead of mounting remote directories that will not be used.
  20. If two clients modify the same file concurrently using AFS:
    Two distinct versions of the file will be created on the server.
    The last client to close the file overwrites the other client?s changes.
    Changes will be applied to the server in the order that they are made by the clients.
    The last client to open the file will be considered to have the latest version and its changes will win.
  21. Coda?s client modification log is used to:
    Allow servers to keep track of which clients modified which files.
    Make it easy to merge changes to the same file from multiple clients.
    Propagate client changes to the server.
    Provide a version control mechanism on the server.
  22. SMB oplocks (opportunistic locks) are:
    Locks pushed by the server to force a client to wait before opening a file.
    A technique to maximize concurrent file access without getting locks, resolving conflicts when the file is closed.
    Permissions granted by the server to tell the client how it can cache file data.
    Exclusive locks on a region of a file to ensure that only one client can modify data in that region.
  23. Which storage systems keep file metadata (information) and file data on separate servers?
    GFS and Chubby.
    Dropbox and GFS.
    SMB and Chubby.
    AFS and Coda.
  24. GFS minimizes the time spent locking a file during appends by:
    Using optimistic concurrency control techniques.
    Allowing only one process to open a file at any time.
    Using strict two-phase locking.
    Uploading the data fully before making it part of the file.
  25. A DNS referral is used:
    When a domain name moves from one IP address to another.
    To identify another name server that is closer to the query.
    When a name server is no longer responsible for a given domain name.
    To find the root name servers responsible for a domain.
  26. Chubby is typically deployed as a set of five servers:
    To provide replicas in case of failures.
    To distribute load for high-volume operations.
    To provide increased storage capacity.
    All of the above.
  27. A key programming approach in the Google cluster architecture is to:
    Perform queries against a huge database that spans multiple servers but is accessed via a single API.
    Send a query to any one of a huge number of replicated systems for processing.
    Minimize overall load by forwarding queries from one small database to another until the query is resolved.
    Convert a query of a large database into many concurrent queries of small databases and merge the results.
  28. Which provides the most direct access to content?
    Central coordinator.
    Query flooding.
    Content-Addressable Network (CAN).
    Chord with finger tables.
  29. An overlay network:
    Makes access more efficient by using only the fastest network links.
    Allows computers to communicate only with systems they know about.
    Avoids the need for back propagation.
    Reduces latency by establishing direct connections between systems.
  30. GFS file access is most similar to:
    A central coordinator.
    Query flooding.
    A distributed hash table.
    A single, centralized server.