Mid Term Solution

Mid Term Distributed System

CS582s 08

DISTRIBUTED SYSTEMS – CS582S08 MID TERM - 29 APRIL 2009 TOTAL TIME: 75 MINUTES SHARP TH

ROLL NO: _____________________________________ SIGNATURE: ___________________________________ CONFIRM SIGNATURE: ____________________________

SOME RULES: 1. WRITE BRIEF, CLEAR AND TO THE POINT ANSWERS. 2. TRY TO FIT YOUR ANSWER IN THE GIVEN SPACE. 3. NO SHARING OF NOTES/CALCULATOR. 4. NO DISCUSSIONS.

1|Page

Mid Term Distributed System

CS582s 08

BRIEF QUESTIONS 1. What are Client and Server Stubs and how are they used in remote procedure calls? (2)

Client and server stubs are light weight wrappers/proxies that make the remote procedure call transparent. They are responsible for packing/unpacking the arguments, return values and actual communication between client and server. They primarily provide local implementation of the remote object

2. You can use RPC between modules written in different programming languages. What challenges do you have to solve as an RPC designer to enable this? (2) System byte order issues, calling convention differences, size of data types, conversion of data types

3. Is it possible to implement exactly once semantic using RPC? Briefly explain your answer (2)

No it is not possible to implement exactly once semantics. Since there are no guarantees for the underlying network a single request may be delivered multiple times and if we don’t receive an acknowledgement there is no way to tell whether the acknowledgement was lost or the server crashed, furthermore it would be impossible to say if the server crashed before executing the request or after

4. With examples explain the difference between iterative name resolution and recursive name resolution. (2) Iterative: Caching is done on client side, state is maintained on the client side, and communication cost is higher since client has to send multiple requests to the servers Recursive: Caching is done on server, state is maintained on server and communication cost is low

5. What is an idempotent operation? (3) An operation which when performed multiple times, has no further effect on its subject after the first time it is performed

6. Discuss whether the following operations are idempotent?

2|Page

Mid Term Distributed System

CS582s 08

a. Write a block of data into a file (2) This is an idempotent operation ( assuming a stateless server), since the effect of the write are local only to the block and do not effect the state for others

b.

Request the number of users currently logged into a remote system (2) This is an idempotent operation since it does not change the state of the system in anyway ( read operation)

c.

Deposit money into a bank account (2) This is not an idempotent operation since if the operation were performed multiple times it would add the money to the account multiple times hence it is not an idempotent operation

7.

In which invocation semantics of RPC is an idempotent operation required? (3) In at least once invocation semantics

8. Which of the parameter passing semantics (call by value or call by reference) is more difficult to implement using RPC. (2)

Call by reference is more difficult to implement since we are passing pointers across process boundaries this involves issues with copying data

NOT SO BRIEF QUESTION The use of replication and caching in distributed systems improves performance and reliability, but it requires attention to consistency of data. We define the term “strict consistency” to mean that a read will always return the data that was most recently written. For each of the systems that follow, indicate whether it provides strict consistency (strict) and if so provide a single sentence explaining why, or indicate that it does not provide strict consistency (non-strict) and if not provide a single sentence explaining when/how such inconsistent information is returned. The Domain Name System (4)

3|Page

Mid Term Distributed System

CS582s 08

The domain name system does not provide strict consistency. This is caused because of the caching of the results. The cached entries are removed from the cache after a certain “timeout” period. So if an entry is changed the systems do not remove it from the cache till the timeout period has elapsed which causes the system to return older data.

A Stock-ticker System using Quorum-based Reads and Writes (4) Such a system will be strictly consistent because we will always read from (n-k) +1 machines (where k is the write quorum). This guarantees that we will always read the most recently written data

Airline Ticketing System (4) Such a system will be a strictly consistent system since we will need to use transactions for the purpose of reservations/ cancellations etc.

Online banking system (4) Such a system will be a strictly consistent system since we will need to use transactions

Internet Routing System (4) The internet routing system is not a strictly consistent system. Since it uses a gossip protocol to update its state. Furthermore nodes can go offline and come online at any instant. When a nodes comes online its state would be inconsistent with the rest of the system causing older results to be returned

4|Page

Mid Term Distributed System

CS582s 08

TWOFACEDBOOK.COM A large successful social network TwoFacedbook.com stores several pieces of your personal information and publishes them to your friends. Initially, this was limited to your work or college info, any pictures or videos you might want to share and wall on which your friends can post comments. This information needs to be replicated such that a single failure of server does not cause your information to be lost. Moreover, since most of this information was largely static in nature, the engineering team at TwoFacedBook.com decided that a fixed degree of replication of information will do the trick. a. Every so often, you notice a message saying “no donut for you” instead of getting someone’s profile page. Assuming that servers at the TwoFacedBook.com never crash, what can be a reason for such unavailability of system? (5) The current system uses transactions. During the transaction the reads may be blocked due to proceeding writes causing the read requests to time out.

Recently, TwoFacedbook.com has changed its service and now support a feature using which you can regularly broadcast your updates to your friends, such “I am starting lunch”, “I just finished lunch”, “I just washed by hands after lunch”, “I feel great after the lunch” etc. etc. With this change, the CTO of TwoFacedbook.com has started arguing that with the new feature of “dynamic broadcasts” the company will need to fundamentally change the way it synchronizes the multiple copies of the data it keeps. b. Can you speculate what the CTO has in his mind for the new architecture and why? (5) A quorum based scheme optimized for writes since now a single update would need to be written to multiple users a small write quorum would be needed to make sure that the system remains available otherwise the system would be continuously busy with writes and would not be available for users.

WHAT'S IN A NAME? THAT WHICH WE CALL A ROSE BY ANY OTHER NAME WOULD SMELL AS SWEET

5|Page

Mid Term Distributed System

CS582s 08

Q.2 Could you please comment on the naming space for variables used by a language such as Java (8, 2 each) 1. Are the names pure or impure? The names are impure

2. Does it allow relative or absolute name? Comment with respect to correctness and ease of programming. It allows for both relative and absolute naming

3. Is there a class of names for which there are functions with a closure property? Give an example. No

4. Is binding of names early or late? Late binding

LUMS DIRECT INWARD DIALING LUMS is now introducing DID numbers for all its extensions. DID, which stands for Direct Inward Dialing, will allow people outside LUMS to directly call people on their extensions rather than first dialing the LUMS number and then dialing a local extension. For instance, where now someone needs to call 042-5722670 ext 4421 to reach someone at lums, with DID numbers, they can call the person directly at a number such as 5904421.

6|Page

Mid Term Distributed System

CS582s 08

Currently, office extension numbers are currently derived from the office of the user. For instance, office 421’s extension is 4421. An interesting property of DID numbers is their use as “numbers for life”, which means that the person retains the number for life, even if he moves his office or location. a. Is DID a pure or an impure name? (5) A DID is a pure name since it does not have any information about the person or the location of the person

b. Can you use a hierarchical scheme to resolve such a number? (5) No. Using a hierarchical scheme in such a system would mean allotting the number based on a certain feature such as location etc which is clearly not the case.

c. In a country like Pakistan, where exchanges go down regularly, will you use a recursive or an iterative scheme for resolving the number (5) In Pakistan an iterative scheme would make more sense since we could cache the intermediate servers and we would still be able to resolve the numbers if the top level servers went down

ATM FIASCO One fine day Mr. Cakes had to pay Rs. 2000 to Mr. Bakes by 12:00 pm. Mr. Cakes had no money in his wallet so he went to the ATM of his bank near Barket Market. He inserted his ATM card, entered his PIN code and entered Rs. 2000 as amount. After a minute’s wait, the machine displayed “Sorry, your transaction failed”. Because Mr. Cakes was in a hurry, he decided to head towards LUMS where Mr. Bakes was waiting and withdrew the amount from some other ATM on the way. So he stopped at another ATM of his bank near Cavalry Bridge. He inserted his ATM card, entered the pin, Rs. 2000 as amount but the system showed “sorry your account details cannot be retrieved”.

7|Page

Mid Term Distributed System

CS582s 08

a. What sequence of events happened above? Please explain each step at the server side carefully, as well as your assumptions in answering the question (5) The first time the transaction started but one of the servers could not commit/ execute the transaction hence aborted. The second time either the link would be unavailable or the account information could have been locked due to locking in the previous phase.

b. Mr. Cakes, disgusted with the service, gave up on taking out the money that day and tried next day. Next day, the system accepted the PIN, started counting the cash, but before spitting out the cash, the electricity went out. When the electricity came back, Mr. Cakes inserted his card again and tried to take out the cash again. This time, the transaction went fine and the cash came out, but his statement showed that he has taken out Rs. 4000 (rather than Rs. 2000 that he actually took out from the ATM machine). Can you please explain what happened here? (5) The first time Mr Cakes used the atm machine. The system started a nested trasaction. The inner transaction was to deduct the amount from his account which was successfully written to the log. But before the atm machine could commit the transaction the machine crashed (electricity) causing the transaction error. On restarting the machine he tried again and this time the transaction was successfully committed but since the previous one was not rolled back it showed the total deducted amount as 4000 instead of 2000

c. Is there any way the situation in part (b) could have been avoided by the system? (5) We can implement logging at the atm machine when the light comes back it can check its logs and request the transaction to be rolled back. We can divide this transaction into two sub transactions 1. Deduct money from the account 2. Dispense cash from the atm machine If 1 fails 2 should not execute, If 2 fails 1 should rollback.

8|Page