CS 417 Exam 2

Spring 2007

    Part I – 36 Points

  1. 6 points
    How does a write-ahead log help achieve atomic reliability in a two-phase commit protocol?
  2. 6 points
    How is reliability achieved in a reliable multicast protocol?
  3. 6 points
    How can Alice pass a symmetric key securely to Bob using public key cryptography?
  4. 12 points
    You can synchronize your computer's clock from one of two network time servers using Cristian's algorithm. In doing so, you obtain the following data:
      Server A Server B
    Error of clock at server ± 4 msec. ± 5 msec.
    Best-case round-trip time 12 msec. 24 msec.
    Timestamp of sending request 4:05:15.000 4:06:15.000
    Timestamp of receiving response 4:05:15.022 4:06:15.028
    Server timestamp received 4:06:22.030 4:07:22.030


    (a) What is the overall clock error on your system if you synchronize from Server A?
    (b) What is the overall clock error on your system if you synchronize from Server B?
    (c) How much should you advance/retard your system's clock based on synchronizing from the server that produces the lowest error? Express your answer as a positive or negative number of minutes, seconds, and decimal seconds (hh:mm:ss.nnn).
  5. 6 points
    How can Alice sign a message that only Bob can validate? The message itself is not encrypted; anyone should be able to read it. However, only Bob should be able to validate Alice's signature.

    6. PART II – 64 points

    For each statement, select the most appropriate answer.

  6. The purpose of the first phase in a two-phase commit protocol is to:
    (a) Send commit/abort directives to all members.
    (b) Get a "commit/abort completed" status from all group members.
    (c) Get a "ready to commit/abort" status from all group members.
    (d) Send "prepare to commit/abort" directives to all group members.
  7. Which of the following is not a condition for deadlock?
    (a) Mutual exclusion.
    (b) Hold-and-wait.
    (c) Preemption.
    (d) Circular wait.
  8. In the Chandy-Misra-Haas deadlock detection algorithm, a process detects a deadlock if:
    (a) It receives a probe from the deadlock coordinator.
    (b) It receives an acknowledgement to a probe from each process holding resources it needs.
    (c) It receives a probe that it originated.
    (d) A probe detects that not all processes waiting on resources are older than this process.
  9. Comparing two Lamport timestamps, L1 and L2, you can tell that:
    (a) If L1 < L2 , then event 1 happened before event 2.
    (b) If event 1 happened before event 2 then L1 < L2 .
    (c) If event 1 has a causal relationship to event 2 and happened before event 2 then L1 < L2 .
    (d) If L1 < L2 , then event 1 happened before event 2 and is causally related to event 2.
  10. Which of the following vector clocks represents a causal series of events?
    (a) (2, 1, 4, 3), (2, 1, 4, 4), (2, 2, 4, 3)
    (b) (2, 1, 4, 3), (3, 2, 5, 4), (3, 3, 4, 4)
    (c) (2, 1, 4, 3), (2, 1, 5, 3), (2, 1, 6, 3)
    (d) (2, 1, 4, 3), (3, 2, 4, 4), (4, 2, 3, 4)
  11. One way to achieve total ordering in messages is to:
    (a) Employ FIFO queues on each process; one for sending and one for receiving messages.
    (b) Delay sending a message until the previous message is acknowledged.
    (c) Assign Lamport timestamps to each message.
    (d) Use a sequence number server.
  12. An ethernet address is obtained from an IP class D multicast address via:
    (a) The address resolution protocol, ARP.
    (b) Copying a subset of the bits of the IP address onto the ethernet address.
    (c) A multicast-aware DNS server that can provide a multicast ethernet address for an IP address.
    (d) This operation makes no sense; there is no such thing as an ethernet multicast address.
  13. Compared with the Ricart & Agrawala mutual exclusion algorithm, Lamport's algorithm:
    (a) Does not rely on delayed responses or grant messages in response to a request.
    (b) Is a true distributed algorithm.
    (c) Does not require reliable multicasting.
    (d) Is more fault-tolerant.
  14. Election algorithms tend to give false results when:
    (a) The network is segmented and one set of nodes becomes separated from another.
    (b) The coordinator is dead.
    (c) Proper message ordering is not imposed.
    (d) Some of the group members are dead.
  15. A distributed directory in a distributed shared memory system:
    (a) Identifies the nodes that have copies of any given memory page.
    (b) Allows a process to translate object IDs to memory locations.
    (c) Provides a filesystem interface to the memory system.
    (d) Allows a node to query for information on the DSM algorithms in use.
  16. A weak consistency model in a distributed shared memory system helps:
    (a) Improve performance.
    (b) Ensure that all memory operations are processed in sequential order.
    (c) Make distributed memory behave exactly like local memory.
    (d) All of the above.
  17. A memory management unit cannot help with this consistency model:
    (a) Weak.
    (b) Entry.
    (c) Sequential.
    (d) Release.
  18. In English text, the letter A occurs 8.2% of the time, T occurs 9.1%, J occurs 0.05%, and Z occurs 0.074% of the time. If you are doing a frequency analysis of ciphertext and see that, in the ciphertext, J occurs consistently 8.2% of the time, Z occurs 9.1%, and A occurs 0.074% of the time, the cipher used is most likely a:
    (a) Transposition cipher.
    (b) Monoalphabetic substitution cipher.
    (c) Alberti polyalphabetic substitution cipher.
    (d) Single-rotor machine.
  19. Looking at another large volume of ciphertext, you notice that for the 1st, 27th, 53rd, 79th, etc. characters, Q occurs 8.2% of the time, L occurs 9.1%, and M occurs 0.05% of the time. For the 2nd, 28th, 54th, 80th, etc. characters of the message, G occurs 8.2% of the time, W occurs 9.1% of the eime, and B occurs 0.05% of the time. The cipher used is most likely a:
    (a) Transposition cipher.
    (b) Monoalphabetic substitution cipher.
    (c) Alberti polyalphabetic substitution cipher.
    (d) Single-rotor machine.
  20. What problem does the Diffie-Hellman algorithm solve?
    (a) Allowing one party to deliver a secret key to another party.
    (b) Avoiding the use of symmetric cryptography by using public and private keys.
    (c) Securely establishing a symmetric key between two parties.
    (d) Providing an encryption algorithm that is stronger than DES.
  21. If you do not use public key cryptography for digital signatures, you will most likely have to:
    (a) Rely on hash functions for the signature.
    (b) Establish a secure link using the Diffie-Hellman algorithm.
    (c) Use a trusted third party that knows everyone’s keys.
    (d) Use private keys instead of public keys.