SOLVED CS550 Homework 3

1. (5 points) The root node in hierarchical location services may become a potential bottleneck. How can this problem be effectively circumvented?

1. (5 points) In a hierarchical location service with a depth of k, how many location records need to be updated at most when a mobile entity changes its location?

1. (10 points) High-level name servers in DNS, that is, name servers implementing nodes in the DNS name space that are close to the root, generally do not support recursive name resolution. Can we expect much performance improvement if they did?

1. (10 points) Explain how DNS can be used to implement a home-based approach to locating mobile hosts.

1. (10 points) Outline an efficient implementation of globally unique identifiers.

1. (10 points) Consider the behavior of two machines in a distributed system. Both have clocks that are supposed to tick 1000 times per millisecond. One of them actually does tick, but the other ticks only 990 times per millisecond. If UTC updates come in once a minute, what is the maximum clock skew that will occur?

1. (10 points) Many distributed algorithms require the use of a coordinating process. To what extent can such algorithms be considered distributed? Discuss.

1. (10 points) A distributed system may have multiple, independent resources. Imagine that process 0 wants to access resource A and process 1 wants to access resource B. Can Ricart&Agrawalas algorithm lead to deadlocks? Explain your answer.

1. (5 points) Give the Lamport logical time for the above diagram:

1. (5 points) Please give the Vector logical time for the following diagram:

1. (10 points) Consider a personal mailbox for a mobile user, implemented as part of a wide-area distributed database. What kind of client-centric consistency would be most appropriate?
2. (10 points) In the Bully algorithm, a recovering process starts an election and will become the new coordinator if it has a higher identifier than the current incumbent. Is this a necessary feature of the algorithm?

Note: We encourage collaboration between you and your classmates. Discuss various approaches and techniques to better understand the questions. However, we do NOT allow copying solutions or code. This is considered as cheating and falls under IIT code of honor. Penalties will be enforced. Please make sure you write your own solutions.

GOOD LUCK!