Distributed Computing Fundamentals Simulations And Advanced Topics 2nd Edition Hagit Attiya, Jennifer Welch - Solutions

Unlock the comprehensive understanding of "Distributed Computing Fundamentals Simulations And Advanced Topics 2nd Edition" by Hagit Attiya and Jennifer Welch with our expertly-crafted solutions. Access a vast repository of questions and answers, complete with a solution manual that offers detailed, step-by-step answers. Whether you're searching for an instructor manual or a solutions PDF, our resources provide clear, solved problems to enhance your learning experience. Dive into chapter solutions and utilize our test bank for effective study sessions. Discover the convenience of free download options for your textbook needs and ace your exams with our online answers key.

16.15 Prove that in a solo execution of any approximate agreement algorithm, the processor must decide on its input value.
16.14 Prove Theorem 16.12.
16.13 Modify the code of the approximate agreement algorithm to use only a single snapshot object, with possibly unbounded number of values in each segment.
16.12 Extend the simulation of Section 5.3.2 to prove: If there is a k-set consensus algorithm for a system of n > k processors that tolerates the failure of k processors, then there is a wait-free k-set consensus algorithm for a system of k processors.
16.11 Extend Lemma 16.6 to any k >2. That is, prove that if the restricted degree of a non-imaginary node in B is 1, then it corresponds to an execution in which {0,, -1} are decided.
16.10 Prove, by induction on k > 2, that an odd number of nodes in B have restricted degree 1.Hint: Add an imaginary node connected to all nodes corresponding to block executions with an unseen processor; use the inductive hypothesis on k to prove that the restricted degree of the imaginary node is
16.9 Explain how the definition of block executions should be modified so that the proof of Theorem 16.7 holds also when processors communicate by ordinary read and write operations, rather than update and scan operations.
16.8 Let A be a k-set consensus algorithm for three processors. Show a one-to-one correspondence between the block executions of A in which p is unseen and the block executions of a k-set consensus algorithm A' for two processors. Hint: A' behaves like A behaves in block executions that do not
16.7 Extend the proof of Exercise 16.6 to show that in B there is no non-imaginary node whose restricted degree is 3.
16.17 Use Lemma 16.8 to prove Lemma 16.9 and Lemma 16.10.
16.18 Prove that Algorithm 53 is correct even if processors use only an array of atomic single-writer multi-reader registers.
16.19 Modify the approximate agreement algorithm (Algorithm 54) and its cor- rectness proof so that maxRound is calculated only in the first asynchronous round.
16.29 Explain why Algorithm 58 needs a flag. Hint: Assume that many processors (more than k) exit the critical section and are now in the remainder; now consider what happens when some processor wishes to enter the critical section.
16.27 Show an execution of Algorithm 57 with more than k participating processors (concurrently), in which some processor does not terminate.
16.16 Complete the proof of Lemma 16.8.
16.26 Prove the termination property of Algorithm 57, when k processors or less participate concurrently.
16.25 Prove that [1..2k+1] is the new name space used by Algorithm 57, even when more than k processors participate concurrently.
16.24 Prove the uniqueness property of Algorithm 57, even when more than k processors participate concurrently.
16.23 Prove that there is no wait-free renaming algorithm with new name space of size n. Hint: Follow the ideas used to prove that there is no wait-free algorithm for solving consensus (Theorem 5.18).
16.22 Describe an execution of Algorithm 56 that uses name n + f.
16.21 Prove Lemma 16.17.
16.20 Present an execution of the renaming algorithm (Algorithm 55) in which some process takes an exponential number of steps before deciding.
16.28 Show an execution of Algorithm 57 with 2k participating processors (concur- rently), in which all processors terminate.
16.6 Prove that the restricted degree of a non-imaginary node in B3 cannot be 3. Hint: Consider a non-imaginary node and its adjacent nodes, as described in Figure 16.7, and try to determine the decisions of all three processors in the four block executions corresponding to these nodes.
16.5 Prove that for a system with n processors there is a finite number of block executions.
15.5 Prove that CN(fetch&inc)= 2.
15.4 Prove that CN(stack)= 2.
15.3 Prove that CN(test&set)= 2.
15.2 Prove that Algorithm 47 is a wait-free consensus algorithm for any number of processors.
15.1 Prove that Algorithm 46 is a wait-free consensus algorithm for two processors. What happens if three processors (or more) use this algorithm?
15.6 The wait-free consensus algorithm for two processors using a FIFO queue relies on the fact that the queue was nonempty initially. Present a two- processor wait-free consensus algorithm that uses two queues that are initially empty and read/write objects.
15.7 Show that the consensus number of an augmented queue, which allows peek operations, that is, reading the head of the queue without removing it, is infinite.
16.4 Find a formula for the number of block executions with two processors, assuming that each processor always takes exactly s steps before deciding.
16.3 Consider the following block execution for four processors: {Po, P2, P3}, {P2, P3}, {Po}, {P1}, {P1}) 1. Which processor is unseen in a? 2. Is po seen in block 1 of a? 3. Is pa last seen in block 3 of a? 4. Construct the unique execution aa, for every i = 0, 1, 2, 3.
16.2 For both cases considered in the proof of Lemma 16.3, prove that p; distinguishes between a and a'. 02 P2 Po P1 Fig. 16.7 Illustration for Exercise 16.6.
16.1 Prove that in a solo execution of any k-set consensus algorithm, the processor must decide on its input value.
15.19 A way to slightly reduce the memory requirements of Algorithm 51 is to have all processors use the same pool of records. Develop the details of this algorithm, which requires O(n) records.
15.18 Show an execution of Algorithm 51, where n records belonging to the same processor are not released.
15.16 Consider the same modification as in Exercise 15.14 to Algorithm 51: Add an iteration of the for loop (of Lines 5-6) inside the while loop (of Lines 7-16). What is the step complexity of the new algorithm? Are there situations in which this modification has improved step complexity?
15.15 Present a universal wait-free algorithm for simulating an n-processor object type with nondeterministic operations, using n-processor consensus objects; follow the outline in Section 15.3.5. Present the correctness proof for this algorithm.
15.14 Consider the following modification to Algorithm 50: Add an iteration of the for loop (of Lines 3-4) inside the while loop (of Lines 5-13). What is the step complexity of the new algorithm? Are there situations in which this modification has improved step complexity?
15.13 Consider the following modification to Algorithm 50: First try to thread your own operation and only then try to help other processors. Show that the modified algorithm is not wait-free.
15.12 Prove Lemma 15.8.
15.11 Prove the linearizability property of Algorithm 49.
15.10 Prove the linearizability property of Algorithm 48.
15.9 Show that consensus numbers also determine the existence of nonblocking simulations. That is, prove that if CN(X) = m and CN(Y) = n > m, then there is no nonblocking simulation of Y by X in a system with more than m processors.
15.8 Show that for every integer m 1, there exists an object with consensus number m. Hint: Consider a variation of an augmented queue that can hold up to m values; once a processor attempts to enqueue the (n + 1)st value, the queue "breaks" and returns a special response to every subsequent
16.30 Specify the k-exclusion and k-assignment problems using the model of Chap- ter 7. Then describe and prove correct the k-assignment algorithm mentioned in Section 16.4.2 using the layered model.
17.8 oP is a failure detector that guarantees that eventually each processor's sus- pected list contains exactly the faulty processors. Can you use oP to simulate 12? Can you use to simulate op? Either give algorithms or give impossibility proofs. Assume a message pass- ing system with crash
17.7 Suppose that the accuracy property of the S failure detector is strength- ened to require that eventually no nonfaulty processor is suspected by any nonfaulty processor. Either show that consensus cannot be solved in an asyn- chronous system with this stronger failure detector when n 2f or
17.6 Suppose that the completeness property of the S failure detector is weak- ened to require that eventually every crashed processor is suspected by some nonfaulty processor (instead of every one). Either show how to convert this weaker failure detector into S in an asynchronous system with n >
17.5 Modify the proof of Theorem 17.2, to show that consensus cannot be solved using the 2 failure detector in an asynchronous system if n
17.4 Expand the ideas presented in Section 17.3.2 to show a simulation of a shared register in a message-passing system, with any number of failures, assuming failure detector S. Hint: Follow Theorem 10.21.
17.3 Directly derive a consensus algorithm for message-passing systems, with any number of faulty processors, using S. Hint: Follow Algorithm 15.
14.1 Prove that every processor terminates Algorithm 41 after sending n messages.
17.2 Show optimizations to the message and time complexity of the simulation of shared memory by message passing in the context of Theorem 17.3.
15.17 Complete the correctness proof for Algorithm 51.
17.1 Modify the proof of Theorem 17.2 to show that nonfaulty processors must continue to send messages in order to solve consensus with S.
14.14 Prove that randomized consensus with probability 1 is possible only if n > 3f +1, when there are Byzantine failures. Hint: Extend the proof of Theorem 5.8, noting that every finite execution has at least one extension that terminates.
14.13 Extend Algorithm 44 to tolerate f>n/3 Byzantine failures, using asyn- chronous identical Byzantine failures and a modified version of validate from Chapter 12. Assume the existence of a common coin procedure that tolerates f Byzantine failures, with bias p.
14.12 Modify the pseudocode of Algorithm 44 so that processors terminate one phase after deciding. Prove that the modified algorithm solves randomized consensus.
14.11 Suppose we have a more restricted model, in which processors can choose random values only with uniform probability distributions (on a bounded range). Show how to pick 0 with probability 1/n and 1 with probability 1-1/n, as needed for Algorithm 45.
14.10 Prove Lemma 14.4.
14.9 Prove that n 2f+1 is a necessary condition for solving randomized consensus in an asynchronous systems, in the presence of crash failures. Hint: Modify the proof for Theorem 10.22.
14.8 Calculate the average message complexity of the common coin procedure of Algorithm 45.
14.7 Calculate the average message complexity of the randomized consensus al- gorithm (Algorithm 44), given a common coin with bias p > 0.
14.6 Complete the details of the proof of Theorem 14.3. Try to prove a stronger result showing that there is no randomized leader election algorithm that knows n within a factor larger than 2. Formally, prove that there is no randomized leader election algorithm that works both for rings of size n
14.5 Show that for synchronous anonymous ring algorithms, there is only a single adversary.
14.4 Prove that both the one-shot and the iterated synchronous leader election algorithms (Algorithm 41 and its extension) have the same performance in the asynchronous case as they do in the synchronous.
14.3 Modify Algorithm 41 so that each message contains a single pseudo-identifier: The termination condition for the algorithm (Lines 6 and 7) needs to be modified.
14.2 Prove that at most one processor terminates Algorithm 41 as a leader.
13.2 Show that if the hardware clock is within a linear envelope of real time and the adjusted clock is within a linear envelope of the hardware clock, then the adjusted clock is within a linear envelope of real time. Calculate the validity parameter of the adjusted clocks with respect to real
13.3 What happens to Theorem 13.3 if there is no drift? What happens to the result? That is, if there is no drift but there are Byzantine failures, do we need n > 3f to keep the adjusted clocks synchronized?
13.4 Prove that if a scale(a, s), then a = scale(a', }).
13.5 In the text it was shown that clock synchronization is impossible for three processors, one of which can be Byzantine. Extend this result to show that n must be larger than 3f, for any value of f (not just f = 1). Hint: Do not try to modify the previous proof. Instead use a reduction, as in
13.6 Complete the second case in the proof of Lemma 13.10 by showing that the difference between a nonfaulty epoch k clock and a nonfaulty epoch k + 1 clock is never more than .
13.7 Complete the third case in the proof of Lemma 13.10 by showing that the difference between two nonfaulty epoch k + 1 clocks is never more than c.
13.8 Complete the algebra in the proof of Lemma 13.11 by showing that kP (1+)k(P2)(1 + p)-2
13.9 Show that the reliable broadcast simulation of Algorithm 23 does not work in the presence of Byzantine failures.
13.10 Work out the details sketched at the end of Section 13.3.2 for handling Byzan- tine failures in the clock synchronization algorithm and the effect on the performance. Try to find ways to reduce the cost of validating the messages of this algorithm.
13.1 Prove that the rate at which two hardware clocks of nonfaulty processors drift from each other is p(2+ p)(1 + p)-1 that is, prove: max 1,3 |HC (At) -HC; (At)| p(2+p)(1+p)-1
5.8 Consider the exponential message consensus algorithm described in Sec- tion 5.2.4. By the result of Section 5.2.3, the algorithm does not work cor- rectly if n 6 and f = 2. Construct an execution for this system in which the algorithm violates the conditions of the consensus problem.
5.7 Show that, if the input set has more than two elements, the validity condition given in Section 5.2.2 is not equivalent to requiring that every nonfaulty decision be the input of some processor. In particular, design an algorithm that satisfies the validity condition of Section 5.2.2 but does
5.6 Present a synchronous algorithm for solving the k-set consensus problem in the presence of f = n 1 crash failures using an algorithm for consensus as a black box. Using Algorithm 15 as the black box, the round complexity of the algorithm should be (+1), and its message complexity should be
5.5 Define the k-set consensus problem as follows. Each processor starts with some arbitrary integer value ; and should output an integer value y; such that: Validity: y = {0,..., n-1}, and k-Agreement: the number of different output values is at most k. Show that Algorithm 18 solves the k-set
5.4 Design a consensus algorithm for crash failures with the following early stopping property: If f' processors fail in an execution, then the algorithm terminates within O(f') rounds. Hint: Processors need not decide in the same round.
5.3 (a) Modify Algorithm 15 to achieve consensus within f rounds, in the case f=n-1.(b) Show that is a lower bound on the number of rounds required in this case. Algorithm 18 k-set consensus algorithm in the presence of crash failures: code for processor pi, 0in-1. Initially V = {x} 1: round r, 1rs
5.2 Consider a synchronous system in which processors fail by clean crashes, that is, in a round, a processor either sends all its messages or none. Design an algorithm that solves the consensus problem in one round.
5.1 Show that for two-element input sets, the validity condition given in Sec- tion 5.1.2 is equivalent to requiring that every nonfaulty decision be the input of some processor.
6.1 Consider the execution in Figure 6.14. (a) Assign logical timestamps to the events.(b) Assign vector timestamps to the events. Po P1 P2 Z Fig. 6.14 Execution for Exercise 6.1.
5.9 Repeat Exercise 5.8 for the polynomial message algorithm of Section 5.2.5. P3
5.10 Prove that 203 in the proof of Theorem 5.7.
5.26 An alternative version of the consensus problem requires that the input value of one distinguished processor (called the general) be distributed to all the other processors (called the lieutenants); this problem is known as single-source consensus. In more detail, the conditions to be
5.25 Modify Algorithm 17 (and its correctness proof) so that get-read skips steps that are known to be computed (based on lastpair).
5.24 Prove that Algorithm 17 correctly simulates an n-processor consensus algo- rithm with two processors.
5.23 Argue why the restricted form of the algorithms assumed in Section 5.3.2 does not lose any generality.
5.22 Can consensus be solved in an asynchronous shared memory system with n > 2 processors, two of which may fail by crashing, if we allow read/write operations, in addition to test&set operations?
5.21 Show that consensus cannot be solved in an asynchronous shared memory system with only test&set registers, with n > 2 processors, two of which may fail by crashing.
5.20 Show that the consensus problem cannot be solved in an asynchronous system with only test&set registers and three processors, if two processors may fail by crashing. The proof may follow Section 5.3.1: 1. Define C {pup} but p; and pj. C' to mean that C is similar to C' for all processors 2.
5.19 Consider an asynchronous shared memory system in which there are only test&set registers (as defined in Chapter 4) and two processors. Show that it is possible to solve consensus in this system even if one processor can crash.

Showing 1 - 100 of 222

Distributed Computing Fundamentals Simulations And Advanced Topics 2nd Edition Hagit Attiya, Jennifer Welch - Solutions

Step by Step Answers