3.10 Consider an anonymous ring where processors start with binary inputs. 1. Prove there is no uniform synchronous algorithm for computing the AND of the input bits. Hint: Assume by way of contradiction that such an algorithm exists, and consider the execution of the algorithm on the all-ones ring; then embed this ring in a much larger ring with a single 0. 2. Present an asynchronous (nonuniform) algorithm for computing the AND; the algorithm should send O(n) messages in the worst case. 3. Prove that 2(n2) is a lower bound on the message complexity of any asynchronous algorithm that computes the AND. 4. Present a synchronous algorithm for computing the AND; the algorithm should send O(n) messages in the worst case.