CS417 Exam 2

Fall 2017

Paul Krzyzanowski

Part I - 16 points

    6 Points

  1. Explain what happens in each of the two phases of a two phase commit protocol (just the main points; no details about what to log).

    2. 5 Points

  2. Explain why Eric Brewer's CAP theorem led to the use of an eventual consistency model in many distributed systems.

    3. 5 Points

  3. False deadlock cannot be solved simply by imposing total ordering on messages. Explain why.

    4. Part II

    84 points - 3 points each.

    For each statement, select the most appropriate answer.

  4. As opposed to locks, leases:
    (a) Have expiration times.
    (b) Are long-term while locks are short-term.
    (c) Allow multiple clients to access a resource for reading.
    (d) Can be distributed while locks are centralized.
  5. Ricart & Agrawala's mutual exclusion algorithm differs from Lamport's because it:
    (a) Uses more messages than Lamport's since each message needs to be acknowledged.
    (b) Uses fewer messages than Lamport's since a system does not reply until it agrees to grant access to a resource.
    (c) Does not require the use of Lamport timestamps.
    (d) Requires a system to contact all group members to request access to a resource.
  6. A bully election algorithm elects:
    (a) The client who can send the most messages in a given time interval.
    (b) The client who discovered a dead leader and sends the first election message.
    (c) The client who has the highest-numbered process ID and responds to messages.
    (d) The client that gets a majority vote.
  7. One advantage that the Chang and Roberts algorithm has over the ring algorithm is:
    (a) It is guaranteed to complete.
    (b) It is resistant to partitioning.
    (c) It will never allow concurrent elections to pick different winners.
    (d) It creates smaller messages.
  8. If an acceptor starts up in the middle of the Paxos protocol, how does it get information about the current proposal number?
    (a) A proposer will send it during the second (accept) phase.
    (b) It queries all other live acceptors for the number.
    (c) It queries any other live acceptor for the number.
    (d) A learner will send it the last valid proposal number.
  9. Once an acceptor makes a promise on a received proposal, it will:
    (a) Not accept proposals with higher sequence numbers.
    (b) Not accept proposals with lower sequence numbers.
    (c) Not accept any other incoming proposals.
    (d) Accept any future proposals, regardless of their number.
  10. One way in which Raft differs from Paxos is that:
    (a) There is no need for majorities.
    (b) In some cases, the resultant value might not be one of the proposed values.
    (c) A single leader to receive all client requests is a requirement.
    (d) The protocol might fail to achieve consensus and will need to be restarted.
  11. When Raft servers hold an election, the winner is generally:
    (a) The server with the highest process number.
    (b) The server that picks the highest random number.
    (c) Chosen by a leader, who propagates the choice to a majority of followers.
    (d) The server where a majority of the group members receive its election message first.
  12. The three-phase commit protocol inserts a new phase to:
    (a) Give a participant the chance to change its mind about committing.
    (b) Tell a participant the vote but not have it commit its sub-transaction.
    (c) Tell each participant that it can release any locks it has on resources.
    (d) Ask a participant if it is ready to commit or needs to abort.
  13. A problem with two-phase locking that is fixed by strict two-phase locking is:
    (a) Since locks are advisory, other transactions may be able to access that locked data.
    (b) A transaction could read data that was modified by a transaction that did not yet commit.
    (c) Deadlock can occur.
    (d) The lock manager may die between the first and second phase.
  14. The use of separate read locks and write locks:
    (a) Allows multiple transactions to acquire write locks to write the same resource concurrently.
    (b) Allows multiple transactions to acquire read locks to read the same resource concurrently.
    (c) Is a form of two-phase locking that separates locks based on their type.
    (d) All of the above.
  15. What condition is NOT necessary for deadlock?
    (a) A transaction holding exclusive locks on one or more resources.
    (b) The ability for a transaction to preempt another one to obtain a lock.
    (c) A transaction waiting on locks for one or more resources.
    (d) A circular dependency of transactions waiting for locks on resources.
  16. Edge chasing is a technique to:
    (a) Make sure that release messages are delivered before lock messages.
    (b) Allow older transactions to complete before new ones start.
    (c) Schedule transactions so that they will never access the same resource concurrently.
    (d) Determine if a cycle of waiting on resource locks exists.
  17. NFS's validation technique ensures that cached data is purged when:
    (a) The server informs the client that its cached contents are no longer valid.
    (b) The client releases a lock on the remote file.
    (c) The client closes the file.
    (d) The server is contacted for new data and the client discovers the file's modification time changed.
  18. Session semantics on a file mean that:
    (a) Only one client can read a file at a time.
    (b) You can grab a single lock to get exclusive access to multiple files at the same time.
    (c) Writes from multiple clients will occur in the order in which they were issued.
    (d) Nobody sees your writes until you close the file.
  19. Under the Coda file system, a client has to write changes to:
    (a) A master server, which then propagates them to replicas.
    (b) Any server hosting the volume, which will then propagate them to other replicas.
    (c) The client modification log, which are then sent to the cell directory server.
    (d) All available servers with a copy of the volume.
  20. A Coda Client Modification Log (CML) is used by:
    (a) Servers to inform clients which files have been modified by other clients.
    (b) Servers to keep a log of which clients have made changes to files.
    (c) Clients to upload a list of changes to a file instead of uploading the entire file to a server.
    (d) Clients during periods of disconnection to track which files have been modified.
  21. SMB oplocks:
    (a) Allow the client to lock a region of a remote file.
    (b) Provide a general-purpose distributed mutual exclusion service for files and other resources.
    (c) Are a mechanism for the server to lock clients out while changes are being made to a file.
    (d) Tell the client how it can cache file data.
  22. A key to Chubby's good performance is:
    (a) Distributing data across multiple replicas.
    (b) Using exceptionally large block sizes in its file system.
    (c) Caching all file data in memory on the server.
    (d) Disallowing clients from locking any file managed by Chubby.
  23. A notification server in Dropbox is conceptually similar to:
    (a) SMB oplocks.
    (b) AFS callbacks.
    (c) NFS read-aheads.
    (d) GFS master.
  24. A design aspect of parallel file systems is:
    (a) File data is spread across multiple servers.
    (b) Multiple clients can access the same file data concurrently.
    (c) The file system uses huge block sizes.
    (d) The same file data is replicated on multiple servers.
  25. GFS separates data flow from control flow to:
    (a) Reduce the amount of time that a chunk needs to be locked.
    (b) Allow the master to decide which chunkservers will host which replicas.
    (c) Enable clients to write data at the same time that the master handles file creation.
    (d) Enable processing to take place on the data as it is being written to the servers.
  26. Consistent hashing means:
    (a) The hash result will never be greater than the table size.
    (b) A hash function on a key, H(k), returns the same value each time.
    (c) Most keys will not have to be remapped if the table size changes.
    (d) The hash function can only accept valid keys.
  27. In a Chord ring with 16 nodes, each node would need a finger table with this many entries:
    (a) 4
    (b) 5
    (c) 15
    (d) 16
  28. The average hop count in a one-dimensional content-addressable network of N nodes is:
    (a) N/2
    (b) √N
    (c) log2N
    (d) N2
  29. Each node in a three-dimensional content-addressable network must know about at most this many neighbors:
    (a) 2
    (b) 4
    (c) 6
    (d) 8
  30. Virtual nodes in Dynamo:
    (a) Enable the use of virtual machines that can be brought in to handle extra load during peak traffic times.
    (b) Are empty placeholder nodes in the ring between physical successor nodes.
    (c) Allow control of load distribution by assigning varying numbers of virtual nodes to physical nodes.
    (d) Each manage one logical block of a content-addressable network.
  31. Dynamo's optimistic replication means:
    (a) Dynamo uses rack-aware logic to create replicas on systems closest to the original node.
    (b) Applications can safely assume that their data will be replicated.
    (c) Replicas are not guaranteed to be identical at all times.
    (d) Applications can assume that all replicas will be updated atomically, ensuring ACID semantics.
Last modified March 24, 2020.

© Paul Krzyzanowski. All rights reserved.

For questions or comments about this site, contact Paul Krzyzanowski, gro.kp@ofnibew

recycled pixels

The entire contents of this site are protected by copyright under national and international law. No part of this site may be copied, reproduced, stored in a retrieval system, or transmitted, in any form, or by any means whether electronic, mechanical or otherwise without the prior written consent of the copyright holder. If there is something on this page that you want to use, please let me know. Any opinions expressed on this page do not necessarily reflect the opinions of my employers and may not even reflect my own.

Page design derived from: HTML5 UP.