DOC PREVIEW
U of I CS 425 - HOMEWORK

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Homework 1 (Time, Synchronization and Global State) - 100 PointsCS425/ECE 428 Distributed Systems, Fall 2009, Instructor: Klara NahrstedtOut: Thursday, September 3, Due Date: Thursday, September 17Instructions: (1) Please, hand in hardcopy solutions that are typed (you may use your favoriteword processor). We will not accept handwritten solutions. Figures and equations (if any) maybe drawn by hand. (2) Please, start each problem on a fresh sheet and type your name at thetop of each sheet. (3) Homework will be due at the beginning of class on the day of thedeadline. Relevant Reading for this Homework: Sections 11.1-11.51. (10 Points) At 10:27:540 (hr, min, 1/100 sec.), server B requests time from the time-server A. At 10:27:610, server B receives a reply from timeserver A with the timestamp of 10:27:375. a. (5 Points) Find out the drift of B’s clock with respect to the time-server A‘s clock (assume there is no processing time at the time-server for time service).b. (2 Points) Is B’s clock going too fast or too slow? If the answer is yes, by how much is the clock going too fast or too slow?c. (3 Points) How should B adjust its clock?2. (5 Points) In the symmetric mode of synchronization in NTP, suppose you are given that server A and server B are connected by a symmetric channel, i.e., the channel shows the same (but unknown) message delay both ways, i.e., the A to B delays is the same as B to A delay. Show using the equations for analyzing the NTP protocol, that under this situation, one can estimate the clock skew accurately (i.e., with an error of 0). 3. (20 Points) Consider Figure 1 that shows four processes (P1, P2, P3, P4) with events a, b, c, … and messages communicating between them. Assume that initial logical clock values are all initialized to 0.a. (5 Points) List the Lamport timestamps for each event shown in Figure 1. Assume that each process maintains a logical clock as a single integer value as a Lamport clock. Provide Lamport clock for all labeled events (but consider all labeled and unlabeled events).b. (10 Points) List the Vector Clock timestamps for each event shown in Figure 1. . Provide Vector clock for all labeled events (but consider all labeled and unlabeled events).c. (5 Points) Is there the potential for a causal violation? Explain why. Figure 1: Four Processes P1, P2, P3, P4 run events a,b,c,d,…. to send and receive messages 4. (35 Points) Consider Figure 2 showing three processes P1, P2, P3. a. (5 Points) Is the run <e11, e22, e23, e32 e24, e33> a linearization of events? Explain why orwhy not. b. (5 Points) Is the cut, shown by curve X, a consistent cut? Why? c. (10 Points) Determine two other consistent cuts in Figure 2 and specify their frontiers. d. (15 Points) In the Figure 2, determine all the events that happen before event e24 (asper Lamport’s Happened-Before relation). Also determine the events that are concurrent with event e24. Figure 2: Three Processes run events to send and receive messages with a Cut X through the processes. P1P2P3e11e12e13e14e21e22e23e24e31e32e33e34X5. (10 Points) a, b, and c are events and no two events belong to the same process. Prove or disprove (give counter-example) the following: a. (5 Points) a is concurrent with b and b is before c implies that a is before c. b. (5 Points) a is concurrent with b and b is concurrent with c implies that a is concurrent with c. 6. (10 Points) Give an example where the Lamport’s clock algorithm comes short (i.e., the Lamport’s algorithm cannot clearly conclude that event e happens before e’, even those L(e)< L(e’), where L(e) is the Lamport’s timestamp of the event e), and the vector clock algorithm concludes clearly that event e happened before e’ or NOT. 7. (10 Points) If the FIFO channel assumption in the Chandy-Lamport algorithm is violated, then which step of the proof for the Chandy-Lamport algorithm given a consistent cut, breaks down (see Textbook/Coulouris et al, 4th


View Full Document

U of I CS 425 - HOMEWORK

Documents in this Course
Lecture 8

Lecture 8

23 pages

TIPS

TIPS

3 pages

The Grid

The Grid

41 pages

Lecture 4

Lecture 4

27 pages

Lecture 4

Lecture 4

20 pages

The Grid

The Grid

41 pages

LECTURE 5

LECTURE 5

25 pages

Multicast

Multicast

23 pages

LECTURE

LECTURE

34 pages

Load more
Download HOMEWORK
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view HOMEWORK and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view HOMEWORK 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?