Questions and Answers of Fundamentals Simulations And Advanced Topics

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
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
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
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
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
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
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
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
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
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.
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
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
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
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?
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
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).
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
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
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
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
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.
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
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
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
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
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
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
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.
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
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
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:
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
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
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
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.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

Showing 1 - 100 of 222