CS 5204 - Fall, 2009
Problem Set 8
20 points
Assigned: November 4, 2009
Due: November 10, 2009 (noon)
.1. (6 points) Kerberos
Develop a secure protocol by
means of which a user could change the password by which the user is
authenticated to the Kerberos system. The protocol must be safe against
replay attacks.
2. (8 points) Simple Vector Clocks. A variation of the vector clock
scheme requires less information be sent with each message. In this
scheme, each node maintains a vector of times as in the vector clocks
approach. Let C[k,j] represent the jth position in the vector
maintained by node k. When a sender transmits a message it sends only
the single value that represents its own local time. That is, node k
transmit with each message it sends the timestamp C[k,k]. The vector on
a node j is updated according to the following rules:
- rule 1: increment C[j,j] by d (d > 0) for each local event (including send and receive events)
- rule 2: on receipt of a message from node k, set C[j,k] = max( C[j,k], t) where t is the timestamp of the message
(a) Are simple vector clocks as powerful as Lamports clocks. That is,
if a and b are two events such that if event a "happend before" event b then the clock
time assigned to event a is less than the clock time assigned to event b?
Explain why or give a counterexample.
(b) Are simple vector clocks as powerful as vector clocks? That is, event a "happend before" event b if and only if
the clock time assigned to event a is less than the clock time assigned to event b?
Explain why or a counterexample.
3. (6 points) The Birman-Schiper-Stephenson protocol relies on message
broadcasting. Demonstrate the need for this requirement by showing an
example where the algorithm fails to work correctly if messages are not broadcast.