15-498 Test #1

Return to the Test #1 index

15-498 Test #1 -- Master Copy

Synchronization of Physical Clocks
1. Assume that the real-time clocks within some population of N workstations can drift, at most, 10 seconds per day. Consider the task of synchronizing these clocks, to within 0.01 seconds of each other, using each of Cristian's Algorithm and The Berkeley Algorithm.
  How many messages are required for each approach?
2. Assume that the real-time clocks within some population of N workstations can drift, at most, 10 seconds per day. Consider the task of synchronizing these clocks, to within 0.01 seconds of each other, using each of Cristian's Algorithm and The Berkeley Algorithm.
  How frequently should the clocks be synchronized for each approach?
Logical Time
1. In class, we discussed Lamport Logical Time as a technique for ordering events in a distributed system. Is it true that if Event_A on one host has a Lamport time stamp lower than Event_B on another host that Event_A occured in real time before Event_B?
  If this is true, please explain how Lamport Logical Time maintains this invariant. If it is not true, please explain why this isn't necessarily the case and please draw a figure depicting one such example.
2. In class we discussed Lamport Logical Time and a vector time protocol based on the same event counting scheme. Do these two approaches necessarily order events in the same way?
  If so, please explain why this must be the case. If not, please explain why not and provide a simple figure to illustrate one such case.
3. In class we discussed using a host id, such as IP address, to break ties and impose a total ordering on Lamport time stamps.
  This approach, on its face, is unfair. Some hosts are more likely to win than others. Why don't we just assign random numbers to these events to break the tie, or, more precisely, order concurrent events randomly? Would this approach provide for a total ordering? Why or why not?
  Hint: Although the answer isn't dependent on the type of communication, it might help to consider multicast.
4. In class we discussed using a host id, such as IP address, to break ties and impose a total ordering on Lamport time stamps.
  This approach, on its face, is unfair -- some hosts are more likely to win than others. Why don't we just use the physical time on the receiving host at the time of receipt to break the tie, e.g. order concurrent events in the order that they were received? Would this approach provide for a total ordering of events? Why or why not?
  Hint: Although the answer isn't dependent on the type of communication, it might help to consider multicast.
Vector Time and Causality
1. In class we discussed detecting causality violations in unicast communications and also the design of a multicast protocol that ensures causal ordering.
  Please design a unicast protocol that ensures causal ordering of messages among hosts and describe the resulting approach.
2. In class we discussed vector timestamps as a tool for detecting causality violations, but we didn't discuss certain trade-offs present in the design of the approach. The algorithm that we discussed in class sends the full vector of timestamps with each message. This can be wasteful if the sending processor has received very few messages since the last time it sent a message to the same host. In this case, most (if not all) of the entries remain unchanged.
  A protocol can be designed that reduces the size of the vector timestamp by sending fewer of these uninteresting entries, but this savings comes at the expense of overhead, including storage and processing, on each host.
  Please assume that the hosts have plenty of processing power and O(P^2) space available to store state information related to the timestamp protocol. Operating under these assumptions, design an algorithm for compressed vector timestamps that reduces the size of the vector timestamps as much as possible, without affecting the utility of the timestamping. Please describe the resulting approach.
3. In class we discussed vector timestamps as a tool for detecting causality violations, but we didn't discuss certain trade-offs present in the design of the approach. The algorithm that we discussed in class sends the full vector of timestamps with each message. This can be wasteful if the sending processor has received very few messages since the last time it sent a message to the same host. In this case, most (if not all) of the entries remain unchanged.
  A protocol can be designed that reduces the size of the vector timestamp by sending fewer of these uninteresting entries, but this savings comes at the expense of overhead, including storage and processing, on each host.
  Please assume that the hosts have plenty of processing power and O(P) space available to store state information related to the timestamp protocol. Operating under these assumptions, design an algorithm for compressed vector timestamps that reduces the size of the vector timestamps as much as possible, without affecting the utility of the timestamping. Please describe the resulting approach.
Semantics of Middleware Communications
1. In class we discussed Sun's implementation of RPC. This implementation supports a blocking request-reply paradigm. In other words, the request is blocked until the reply is received.
  Please discuss the costs and benefits of a non-blocking RPC implemention. Your discussion should include both elements important to the application developer and also to the implementor of the RPC package.
2. The Java RMI system implements a blocking paradigm for remote method invocation. In other words, the caller is blocked until the remote method executes and returns the result. Consider a non-blocking version of the RMI. Specifically, assume that after a remote method is invoked, the flow of control in the caller continues, and that the calling thread is informed about the availability of the result via an exception. The exception handler (catch block) then takes appropriate action.
  Please describe the impact of the cost and beneifts of this approach to the RMI, both from the perspective of the RMI implementor and the application developer. You may neglect the case where the return type is void.
3. RPC and RMI situations generally provide at-most-once semantics. In other words, a remote method or function is guaranteed to occur at most once per invocation. In most cases, application developers would prefer exactly once semantics -- if the truth were known, most probably assume this.
  Please discuss the impact that exactly once semantics would have on the implementation of an IPC system such as Sun's RPC or Java RMI.
4. RPC and RMI situations generally provide at-most-once semantics. In other words, a remote method or function is guaranteed to occur at most once per invocation. In most cases, application developers would prefer exactly once semantics -- if the truth were known, most probably assume this.
  Imagine that, instead of at-most-once semeantics, middleware layers implemented at-least-once semantics. What impact would this have on the life of an application programmer. Would such a middleware layer be more or less convenient? More or less applicable to typical problems?
Middleware Architectures and Mechanisms
1. CORBA provides a mechanism to support distributed objects and remote procedure calls. Despite this, XML-based techiques, including XML-RPC, and especially SOAP, are gaining wide-spread use. Why?
2. Both Java's RMI and CORBA allow the stubs to be packaged with the client application, but each provides a mechanism for a client to interact with a remote object, even without the stub. In the case of Java's RMI, the stub is obtained via HTTP. In the case of CORBA, the necessary information is communicated to the client for the client to construct the method invocation dynamically, without the stub.
  Why do the two architectures take a different approach? What are the costs and benefits of each?
3. Java's RMI considers all parameters, except remote object references to be input parameters. They are passed by copy and not returned. In the context of the Java environment, why is this a necessity? In other words, why can't Java emulate a pass-by-reference as a pass by in-out, as was done in C with RPC?
4. In Java objects are very straight-forward to decompose and reconstruct. .class files provide blue-prints for each type of object, and Java has rich functionality for extracting the properties of an object, including all of its state.
  As a result, it would seem that the serialization of an object for use as a parameter or return value would require nothing from the object, itself. But, it doesn't work this way. Java's RMI can only send Serializable objects as parameters or return values. These classes of objects implement their own serialization methods.
  Assume that .class files could be sent to a client, as needed, via HTTP, as is done with stubs. Why doesn't the Java RMI just parse the objects, flatten the fields, and serialize the objects automatically? In your discussion, you should include at least one example of a problematic type of object.
Mutual Exclusion
1. In class, we discussed several techniques for enforcing mutual exclusion. But, we didn't discuss techniques for enforcing other concurrency control policies.
  Please adapt Maekawa's voting district scheme to solve the "at most n users" mutual exclusion problem. In other words, please adapt it so that it allows not more than "n" users to access the shared resource at a time. Your new design should be as loyal to the original design as is practical.
  If it does not make sense to use an adaptation of Maekawa's protocol for this purpose, please explain the reason.
2. In class, we discussed several techniques for enforcing mutual exclusion. But, we didn't discuss techniques for enforcing other concurrency control policies.
  Please adapt the majority vote scheme to solve the "at most n users" mutual exclusion problem. In other words, please adapt it so that it allows not more than "n" users to access the shared resource at a time. Your new design should be as loyal to the original design as is practical.
  If it does not make sense to use an adaptation of the voting scheme for this purpose, please explain the reason.
3. In class, we discussed several techniques for enforcing mutual exclusion. But, we didn't discuss techniques for enforcing other concurrency control policies. Many of the protocols that we discussed for enfocing mutual exclusion are readily adaptable to the problem of enforcing "at most n users" of a shared resource.
  Consider Raymond's Algorithm Is it a good example of a protocol that can readily be adapted for this purpose? Why or why not?
4. In class, we discussed several techniques for enforcing mutual exclusion. But, we didn't discuss techniques for enforcing other concurrency control policies.
  Please select one among the mutual exclusion protocols from our in class discussion and adapt it to enforce reader-writer locks, instead of mutual exclusion. Needless to say, you should select a protocol which cna be usefully adapted for this purpose. Your new protocol should be as loyal to the original as is practical.
  A read-writer lock allows readers to share an object with other readers, but ensures that a writer excludes both other writers and also readers. Sometimes this protocol is described as "Shared reads, exclusive writes". Readers should starve writers.
Distributed Transactions and Transaction Processing
1. In class we discussed two atomic commit protocols, 2PC and 3PC, three if you count the protocol for total order multicast. We said that each of these protocols is a "blocking protocol."
  What was meant by "blocking protocol"?
  If possible, please define a non-blocking atomic commit protocol. If this is impossible, please offer an intuitive explanation of the reason that this is not possible.
2. If processor power is constraining, which approach will yield a high throughput, concurrent transaction processing by conflict avoidance, or concurrent transaction processing using an optimistic approach? Why?
3. If a transaction stream with a high level of resource sharing is processed by a system with nearly infinite processor power and memory, which approach is better conflict prevention, such as 2PL, or optimistic processing?
4. What are the relative advantages of conflict prevention, such as by 2PL, as compared with conflict avoidance, as we saw with the timestamp protocol?