Distributed Computing Principles Algorithms And Systems 1st Edition Ajay D. Kshemkalyani, Mukesh Singhal - Solutions

11. Converting between octal and decimal is analogous to the technique of converting between binary and decimal. *(a) Write the polynomial representation of the octal number 70146 as in Figure 3.4. (b) Use the technique of Figure 3.5 to convert 7291 (dec) to octal.
10. Section 3.1 states that you can tell whether a binary number is even or odd only by inspecting the digit in the 1’s place. Is that always possible for an arbitrary base? Explain.
7. With unsigned binary representation, what is the range of numbers as written in binary and in decimal for the following cells?(a) a two-bit cell(b) a three-bit cell(c) a four-bit cell(d) a five-bit cell(e) an n-bit cell in general
6. Convert the following numbers from decimal to binary, assuming unsigned binary representation:(a) 12(b) 35(c) 3(d) 0(e) 27(f) 16
5. Convert the following numbers from decimal to binary, assuming unsigned binary representation:(a) 25(b) 16(c) 1(d) 14(e) 5(f) 41
4. Convert the following numbers from binary to decimal, assuming unsigned binary representation:(a) 10110(b) 10(c) 10101(d) 10000(e) 1111(f) 11110000
3. Convert the following numbers from binary to decimal, assuming unsigned binary representation:(a) 10010(b) 110(c) 1011(d) 1000(e) 11111(f) 1010101
2. Count the next 10 numbers (a) in octal starting from 466, (b) in base 3 starting from 1201, (c)in binary starting from 11011, and (d) in base 5 starting from 3434.
1. Count the next 10 numbers (a) in octal starting from 267, (b) in base 3 starting from 2102, (c)in binary starting from 10101, and (d) in base 5 starting from 2433.
Example 3.3 FIGURE 3.5 converts 22 (dec) to binary. The number 22 divided by 2 is 11 with a remainder of 0, which is written in the right column. Then, 11 divided by 2 is 5, with a remainder of 1. Continuing until the number gets down to 0 produces a column of remainders, which, when read from the
Example 3.2 The unsigned binary number system is analogous to our familiar decimal system.FIGURE 3.3 shows the place values for 58,036 (dec). The figure 58,036 represents six 1’s, three 10’s, no 100’s, eight 1000’s, and five 10,000’s. Starting with the 1’s place from the right, each
FIGURE 3.2(a) shows the place values for 10110 (bin). Starting with the 1’s place on the right (called the least significant bit), each place has a value twice as great as the previous place value. Figure 3.2(b) shows the addition that produces the 22 (dec) value.
12. Examine the impact of unreliable links and node failures on each of the challenges listed in Section 1.8.2.
11. Figure 1.11 shows the emulations among the principal system classes in a failure-free system.(a) Which of these emulations are possible in a failure-prone system? Explain.(b) Which of these emulations are not possible in a failure-prone system? Explain.
10. What are the three aspects of reliability? Is it possible to order them in different ways in terms of importance, based on different applications’ requirements? Justify your answer by giving examples of different applications.
9. Explain why a Receive call cannot be asynchronous.
8. Two interconnection networks are isomorphic if there is a 1:1mapping f between the switches such that for any switches x and y that are connected to each other in adjacent stages in one network, f(x) and f(y) are also connected in the other network.Show that the Omega, Butterfly, and Clos
7. The Baseline Clos network has a interconnection generation function as follows. Let there be M = n/2 switches per stage, and let a switch be denoted by the tuple hx, si, where x ∈ [0,M − 1] and stage s ∈ [0, log2n − 1].There is an edge from switch hx, si to switch hy, s + 1i if (i) y is
6. In Figure 1.4, observe that the paths from input 000 to output 111 and from input 101 to output 110 have a common edge. Therefore, simultaneous transmission over these paths is not possible; one path blocks another. Hence, the Omega and Butterfly networks are classified as blocking
5. Formulate the interconnection function for the Omega network having n inputs and outputs, only in terms of the M = n/2 switch numbers in each stage. (Hint: Follow an approach similar to the Butterfly network formulation.)
4. For the Omega and Butterfly networks shown in Figure 1.4, trace the paths from P5 to M2, and from P6 to M1.
3. Draw the Omega and Butterfly networks for n = 16 inputs and outputs.
2. Identify some distributed applications in the scientific and commercial application areas.For each application, determine which of the motivating factors listed in Section 1.3 are important for building the application over a distributed system.
1. What are the main differences between a parallel system and a distributed system?
Give a rigorous proof of impossibility of a min-process, non-blocking checkpointing algorithm.
Design a checkpointing and recovery algorithm that uses vector clocks, and does not assume any underlying topology (like ring or tree).
Show that in Manivannan-Singhal algorithm, every checkpoint taken is useful.
Show by example that if Koo-Toueg checkpointing algrithm, if processes do not block after taking a tentative checkpoint, then global checkpoint taken by all processes may not be consistent.
Consider the following simple checkpointing algorithm: A process takes a local checkpoint right after sending a message. Show that the last checkpoint at all processes will always be consistent. What are the trade-offs with this method?
5. Consider two consistent cuts whose events are denoted by C1 = C1(1),C1(2), ...,C1(n) and C2 = C2(1),C2(2), ...,C2(n), respectively.Define a third cut, C3 = C3(1),C3(2), ...,C3(n) that is the maximum of C1 and C2; that is, for every k, C3(k) = later of C1(k) and C2(k).Define a fourth cut, C4 =
4. What modifications should be done to the Chandy-Lamport snapshot algorithm so that it records a strongly consistent snapshot (i.e., all channel states are recorded empty).
3. Consider a distributed system where every node has its physical clock and all physical clocks are perfectly synchronized. Give an algorithm to record global state assuming the communication network is reliable. (Note that your algorithm should be simpler than the Chandy-Lamport algorithm.)
2. What good is a distributed snapshot when the system was never in the state represented by the distributed snapshot? Give an application of distributed snapshots.
1. Consider the following simple method to collect a global snapshot (it may not always collect a consistent global snapshot): Initiator process takes its snapshot and broadcasts a request to take snapshot. When some other process receives this request, it takes a snapshot. Channels are not
4. The size of matrix clocks is quadratic with respect to the system size. Hence the message overhead is likely to be substantial. Propose a technique for matrix clocks similar to that of Singhal-Kshemkalyani to decrease the volume of information transmitted in messages and stored at processes.
1. Why is it difficult to keep a synchronized system of physical clocks in distributed systems?
5. Consider the following protocol for Authentication/Key Distribution: (X and Y are two principals, A is a Certificate Authority or a Key Distribution Center, RX is a randon number, and EX means encrypted with the secret key of X.)(a) What does the presence of RX in message 2 assure?(b) What
9. Show that the solution to Equation (18.30) for the degree distribution in the Extended BA model using continuum theory analysis is given by Equation (18.33).
8. Show that the Master-equation approach used to solve for the degree distribution in the extended BA model in Section 18.13.2 gives the solution expressed by Equation (??).
7. Show that Equation (18.23) using the Master-equation approach for the degree distribution in the extended BA model can be solved as Equation (18.24).
6. (Power Law in the Internet. [28]) Show that the number of edges in the Internet graph that obeys the power law for the rank exponent is given as follows. Let the graph have n nodes and rank exponent R. Then: l ∼ 1 2(R+1) (1 − 1 nR+1 )n
5. (CAN.) Identify all the changes to the base CAN protocol to accommodate the optimization of overloading coordinate regions, discussed in Section 18.5.5.
4. (CAN.) Compute the time and message complexity of the distributed region reassignment protocol that is run periodically by the CAN protocol.
3. (Chord.) In the Chord protocol, assume that the successor list at each node has α =(log n)nodes. Show the following.(a) If a Chord ring is initially stable, and if the probability of subsequent failure of each node is 0.5, then Locate_Successor returns the closest functional successor node to
2. (Fault-tolerance in Chord.) Adapt the code in Figure 18.6 so that the nodes manage a successor list or α successors, rather than a single successor.
1. (Replication.) Derive the values of average search size A, Ai, and utilization ui for Squareroot replication. The derived answers should match the entries in Table 18.3.
One weakness of self-stabilization is that it is a global property. A failure that is local to a machine may spread and lead to corrective actions across the entire system. Discuss how this problem can be addressed by local detection and correction of failures [4, 16].
Describe a self-stabilizing mutual exclusion algorithm.
Fault containment is a problem with self-stablizing algorithms. What are fault-containing self-stablizing algorithms [50]? Describe how they solve the problem.
What are the trade-offs in a self-stabilizing system/algorithm?
What is “superstabilization"? What type of guarantees do superstabilization provide?
Give a psuedo-stabilization algorithm. Discuss how it reduces the cost compared to stabilization.
Describe self-stabilizing alternating-bit protocol.
When self-stabilization claims to solve so many problems in fault tolerance in a unified manner, why are people still studying and investigating each of those problems individually?
6. Discuss two biometric based methods for authentication. What are pros and cons of biometric based methods for authentication?
4. Choose two principles given by Needham and Abadi for designing cryptographic protocols.For each, give an example where their principle applies and results in an improved protocol.
3. Consider the following simple method to handle attacks on the password based authentication:If a user fails to login in three successive attempts, the system locks his account suspecting an attack/intrusion. What major problem do you see with this method?
2. What is a nonce? What security problem does it solve?
1. List three attacks/threats that are associated with user authentication on the Internet.
It is well known fact that consensus and atomic broadcast problems cannot be solved deterministically in asynchronous distributed systems even for a single process failure. Then how failure detectors solve these problems?
18. Show how the number of splitters used in the renaming algorithm of Section 14.6.6 can be reduced to n(n − 1)/2.
17. Perform a time complexity analysis of the wait-free renaming algorithm using the atomic snapshot object in asynchronous systems, given in Figure 14.30. Also prove the lower bounds on the size of the name space, as indicated in Section 14.5.6.
16. Adapt the message-passing asynchronous approximate agreement algorithm given in Section 14.5.5 for a shared memory system.
15. Simplify the nonblocking universal algorithm for consensus objects (Figure 14.28) by using the specific Compare&Swap object, but also eliminating the Head array.
14. Perform an average-case time complexity analysis of the nonblocking universal algorithm for consensus objects given in Figure 14.26.
13. Examine the standard stack object, having its standard push and pop operations. What is the consensus number x of the stack? Give the code for achieving 2-process consensus using the stack.
12. (k-Write instruction).(a) Consider the 2-Write instruction that can write two locations atomically. Show how the 2-Write instruction can be used to implement a wait-free 2-consensus protocol. (Hint:structure the solution using a structure similar to that of the protocols for RMW and Swap.)(b)
11. Examine the Test-&-Set instruction in Figure 14.22. What is the consensus number x of this register object? Give an algorithm to achieve consensus for this consensus number.
10. How can the algorithm for asynchronous renaming, given in Figure 14.17, be simplified if a synchronous system is available?
9. Analyze the number of bids for a new name made by each process in the asynchronous renaming algorithm given in Figure 14.17.
8. How can the algorithm for ǫ-agreement, given in Figure 14.13, be simplified if a synchronous system is available? Identify all the changes to the various parameter values. Can a better value be obtained for the convergence rate?
7. In the ǫ-agreement problem, can a correct process halt if it receives f + 1 halting tags from other processes, even before it has completed its precomputed number of rounds? Justify your answer.
6. Prove that the leader election problem is not solvable under a crash failure.
5. Prove that the distributed commit problem is not solvable under a crash failure.Hint: Show a reduction from the consensus problem to the distributed commit problem.
4. Examine the phase-king algorithm for consensus in the face of Byzantine failures, as given in Figure 14.11. This algorithm works when n > 4f. Presumably, the algorithm will fail for 4f ≥ n > 3f, even though this condition is a sufficient condition for the existence of a solution to the
3. Modify the iterative Byzantine Agreement algorithm and the tree data structure specification given in Figure 14.7, as well as the example in Figure 14.8, to now solve the consensus problem.
2. Modify the algorithm in Figure 14.3 to design an early-stopping algorithm for consensus under failstop failures, that terminates within f′ + 1 rounds, where f′, the actual number of stop-failures, is less thanf. Prove the correctness of your algorithm.Hint: A process can be required to send
1. For each of the six ordered pairs of problems among: the Byzantine agreement problem, the Consensus problem, and the Interactive consistency problem, demonstrate a reduction from the former to the latter.
Show that in Kshemkalyani-Singhal algorithm for the P-out-of-Q model, if the weight at the initiator process becomes 1.0, then the intiator is involved in a deadlock.365
Show that in the AND model, false deadlocks can occur due to deadlock resolution in distributed systems [44]. Can something be done about it or they are bound to happen?
Suppose all the processes in the system are assigned priorities which can be used to totally order the processes. Modify the Chandy et al.’s algorithm for the AND model so that when a process detects a deadlock, it also knows the lowest priority deadlocked process.
Consider the following simple approach to handle deadlocks in distributed systems by using“time-outs”: a process that has waited for a specified period for a resource declares that it is deadlocked and aborts to resolve the deadlock. What are the shortcomings of using this method?
12. Determine the average case time complexity of the wait-free atomic snapshot of a shared object, given in Figure 12.33.
11. Peterson’s mutual exclusion algortihm for two processes is shown in Figure 12.34.(a) Show that it satisfies mutual exclusion, progress, and bounded waiting.(b) Use this algorithm as a building block to construct a hierarchical mutual exclusion algorithm for an arbitrary number of processes.
10. Assume that the writer does a single pass from left to right in Construction 6, Figure 12.27, for aMRSWregister. Can the code for the readers be modified to devise a correct algorithm?Justify your answer.
9. Why are two passes needed by the reader in Construction 6, Figure 12.27, for a MRSW atomic register? Why does a single right-to-left pass not suffice?
8. Show that Constructions 1 and 2 (Figure 12.21) work for binary registers as well as integervalued registers.
7. Give a detailed implementation of slow memory, and provide a correctness argument for your implementation. Is the implementation less expensive than that of PRAM consistency which is a stricter consistency model?
6. Give a detailed implementation of PRAM consistency, and provide a correctness argument for your implementation.
5. Give a detailed implementation of causal consistency, and provide a correctness argument for your implementation.
4. • In Figure 12.9(a), analyze whether the execution is linearizable.• In Figure 12.9(b), what forms of memory consistency are satisfied if the two Read operations of P4 return 7 first and then 4?
3. In the algorithm to implement sequential consistency using local Write operations, as given in Figure 12.8, why is a single counter counter sufficient for the algorithm’s correctness?In other words, why is a separate counter counterx not required to track the number of updates issued to each
2. Give a formal proof to justify the correctness of the algorithm in Figure 12.7 that implements sequential consistency using local Read operations.
1. Why do the algorithms for sequential consistency (Section 12.2.2) not require the Read operations to be broadcast?
10. Show the following relationships among the various classes of predicates.(a) The set of stable predicates is a proper subset of the set of observer-independent predicates.(b) The set of disjunctive predicates is a proper subset of the set of observer-independent predicates.
9. Analyze the degree to which the algorithm in Figure 11.16 is resilient to message losses.
8. Determinewhether the interval-based distributed algorithm(Figure 11.16) to detect Possibly(φ)will always detect Possibly(φ), even though the algorithm is correct in principle. If it will not, extend the algorithm to ensure that a solution is always detected if it exists.Hint: Consider the
7. Can the algorithm for global state based detection of a conjunctive predicate (centralized, on-line, Possibly) of Figure 11.9 be modified to detect Definitely(φ)? If yes, give the modified algorithm and show it is correct.
6. For the algorithm in Figure 11.3, answer the following.(a) When can the algorithm begin constructing the global states of level lvl?(b) When are all the global states of level lvl constructed?
5. If it is known that Possibly(φ) is true and Definitely(φ) is false in an execution, then what can be said about Possibly(φ) and about Definitely(φ) in terms of the paths of the state lattice of that execution?

Showing 500 - 600 of 640

Distributed Computing Principles Algorithms And Systems 1st Edition Ajay D. Kshemkalyani, Mukesh Singhal - Solutions

Step by Step Answers