CS417 Exam 3

Fall 2014

Paul Krzyzanowski

    Part I – 22 Points

  1. 4 points
    Most databases require the use of read locks as well as write locks. Spanner requires locks for writes but offers lock-free reads. Explain how Spanner supports this. After all, you don't want incoming writes to modify some of the data that is being read since that would violate consistency.
  2. 4 points
    Over time, you add some newer, more powerful computers to your data center. Explain how Amazon Dynamo's virtual nodes allow you to handle this hybrid environment of old and new computers.
  3. 5 points
    What is a potential problem of a fail-recover system versus that of a fail-stop system?
  4. 5 points

    Alice has Bob's X.509 digital certificate. She validated it to ensure that it is legitimate. How does she now use it to establish a secure communication channel so she and Bob can exchange encrypted messages?

    Alice does not need to authenticate Bob - she just needs to communicate with him. Explain the steps necessary. If any encryption or decryption is done, explain what key is used.

  5. 5 points

    We discussed a two-dimensional content-addressable network (CAN). Consider a one-dimensional version.

    Explain how a query is forwarded at a node.

    Write your answer in the form of pseudocode or a flowchart explaining what happens when an arbitrary node gets a lookup(key) request.

  6. Part II – 78 points – 3 points each

    For each statement, select the most appropriate answer.

  7. A superstep in the Bulk Synchronous Parallel framework is the execution of:
    User-defined functions in parallel until a point is reached where any one function needs to send a message.
    User-defined functions in parallel, each starting with reading a set of input messages and progressing until it generates output messages or is done.
    Several such sequences with a checkpoint at the end.
    Several such sequences until there is no more input data.
  8. A Pregel algorithm completes when:
    A predefined number of supersteps has completed.
    No vertex outputs any data.
    No vertex receives any data.
    Every vertex votes to halt.
  9. Pregel implements this type of group message ordering:
    Global time ordering
    Total ordering
    Partial (causal) ordering
    Barriers
  10. How does a commit wait differ from a regular commit?
    The transaction waits until all locks are released.
    The transaction waits until all sub-transactions have completed.
    The transaction waits until the transaction state has been written to the write-ahead log.
    The transaction waits until the timestamp of the commit is guaranteed to be in the past.
  11. Spanner's TrueTime provides clients with:
    The exact absolute time regardless of where they are.
    The exact time adjusted for each client's local time zone.
    The absolute time along with uncertainty bounds.
    A globally unique monotonically increasing timestamp.
  12. To ensure that transactions are serialized, Spanner uses:
    The TrueTime API and commit wait.
    Strict two-phase locking.
    Paxos consensus.
    Two-phase commit protocol.
  13. As a rough definition, consistent hashing means:
    As long as the size of the hash table stays the same, a key will repeatedly hash to the same value.
    Most keys will hash to the same value as the size of the hash table changes.
    Each key is guaranteed to hash to a unique value, ensuring there are no collisions.
    If key K1 is greater than another key K2 then hash(K1) > hash(K2).
  14. The purpose of a finger table in the Chord DHT is to:
    Enable a node to reach its predecessor node as well as its successor node.
    Reduce the number of hops without storing a list of all machines at every node.
    Provide a mechanism for fault tolerance, so that <key, value> data can be replicated at N successor nodes.
    Handle the case where a hash results in a collision and multiple keys must be stored at the same node.
  15. Dynamo uses vector clocks to:
    Make sure that all client updates to a key are serialized.
    Provide a multi-version key-value store, allowing a client to retrieve old versions of data.
    Present the client with multiple values for a key if there were concurrent updates to the key.
    Provide fault-tolerant replication of a key across multiple nodes.
  16. A separate network is sometimes used for a cluster heartbeat to:
    Help distinguish network faults from computer faults.
    Avoid adding extra traffic to the main network.
    Ensure that heartbeat messages can go onto the network without collisions.
    Clearly distinguish signaling traffic from data traffic.
  17. A clustered file system is a:
    Network file system service that spans multiple computers and provides a file access service.
    File system that uses a disk that is simultaneously shared across multiple computers.
    Network file system that resides on a dedicated file server and is used by all members of the cluster.
    Collection of individual file systems that provides the illusion of one large file system.
  18. Which system uses warm failover?
    Chubby
    Bigtable
    Pregel
    MapReduce
  19. A overlay caching network such as Akamai uses:
    Multihoming at the origin server to ensure the original site is connected via multiple ISPs.
    Proxy servers at the client to cache frequently accessed content.
    Load balancers at the origin servers to handle high volumes of requests.
    Dynamic DNS to map domain names to servers
  20. A CDN using a caching overlay network does not offer:
    Caching of static content on edge servers.
    The ability to replicate the origin server within the network to accelerate dynamic content.
    Alternate routing choices to the orgin server instead of direct IP routing.
    Security benefits due isolating the origin and ability to handle high volumes of traffic.
  21. The transport system in Akamai's CDN:
    Encrypts content for secure transport.
    Finds the most efficient routes to the origin servers
    Queues content requests for delayed access if the network is too congested.
    Uses multiple network links concurrently to achieve higher bandwidth.
  22. Suppose you can test all combinations of a 32-bit key in one second. How long will it take you to test all combinations of a 40-bit key?
    40/32 = 1.25 seconds
    (40-32) = 8 seconds
    28 = 256 seconds
    (240 - 232) = 1.09 x 1012 seconds
  23. An advantage of using a public key algorithm for secure communication is:
    A message can be securely delivered to many recipients at once.
    It is far more secure than using a symmetric algorithm.
    It is much faster than using a symmetric algorithm.
    You do not need to have a shared secret key.
  24. A hybrid cryptosystem:
    Combines encryption with digital signatures.
    Relays messages through a trusted third party.
    Applies two layers of encryption for added security.
    Uses public key cryptography to encrypt a session key.
  25. Hashed passwords in the Password Authentication Protocol (PAP):
    Reduce the value of stealing a password file.
    Enable a password to be sent securely over a network.
    Ensure that a password has not been maliciously modified.
    Protect the user from a man-in-the-middle attack.
  26. With Kerberos, how does Bob know that Alice is authorized to talk with him? Alice sends Bob a ticket that:
    Is encrypted with Bob's secret key.
    Is encrypted with Bob's public key.
    Contains an authorization token that Bob can present to Kerberos.
    Is encrypted with Alice's private key.
  27. OAuth:
    Relies on HTTP redirection to allow a user to specify access permissions to a particular service.
    Is a centralized authorization service that manages access rights among services from multiple vendors.
    Is a protocol to securely obtain user IDs and passwords to services that an application needs to access.
    Is a protocol designed to authenticate users using multi-factor authentication prior to accessing a service.
  28. How does a service validate an OpenID token that is returned after a user authenticates with the Identity Provider?
    It decrypts it with its private key.
    It sends it to the identity provider (authorization server).
    It asks the user to decrypt it.
    It asks the user to validate the signature.
  29. You need stateful inspection in a packet filtering firewall to:
    Drop all packets from the Internet whose source address matches that of an internal computer.
    Allow only UDP requests to a streaming media server.
    Permit return traffic only in response to outbound messages.
    Deny all TCP traffic to port 80 (HTTP) on a specific machine.
  30. Which services would not run on a computer in the DMZ?
    Web server for serving your organization's web pages.
    Mail server for accepting incoming email for your organization.
    Web caching proxy for outbound web surfing.
    FTP server for providing file access to external users.
  31. Transport mode differs from tunnel mode in that:
    Tunnel mode provides a bidirectional communication channel.
    Transport mode is responsible for optimally routing the packet to its destination.
    Tunnel mode encapsulates the entire IP packet and prepends a new IP header.
    Transport mode encrypts the entire IP packet while tunnel mode encrypts only the data.
  32. Which statement is not generally true about VPNs?
    Using a VPN is faster than not using one.
    A VPN enables multiple LANs (local area networks) to communicate over the public Internet.
    Using a VPN is cheaper than using a leased line (private network).
    VPNs encrypt packet data.
Last modified March 24, 2020.
recycled pixels