Recursive Energy Efficient Agreement Shachar Meir, David Peleg Abstract Agreement is a foundational problem in distributed computing that have been studied extensively for over four decades. Recently, Meir, Mirault, Peleg and Robinson introduced the notion of Energy Efficient Agreement , where the goal is to solve Agreement while minimizing the number of round a party participates in, thereby reducing the energy cost per participant. We show a recursive Agreement algorithm that has O ⁡ ( log ⁡ f ) O(\log f) active rounds per participant, where f < n fc . If all non-faulty processors start with the same input v , then \mbox{\tt RCA}[Q_{2w},v_{in}] returns v at any processor in H_{2w} , since it satisfies validity by the induction hypothesis (since |Q_{2w}|<|Q_{w}| ). Thus, every non-faulty processor in Q_{2w+1} runs \mbox{\tt RCA}[Q_{2w+1},v_{in}^{\prime}] with input v (since it either receives v from a processor in H_{2w} , or it uses its own input v_{in}=v ). By the induction hypothesis, \mbox{\tt RCA}[Q_{2w+1},v_{in}^{\prime}] also satisfies validity and every processor in H_{2w+1} returns v . Hence, every non-faulty processor in Q_{w} sets v_{out}\leftarrow v and outputs v . ∎ Lemma 4.2 . Algorithm \mbox{\tt RCA}[Q_{w},v_{in}] satisfies agreement. Proof. We prove the claim by induction on the size of Q_{w} . For the induction basis, if |Q_{w}|\leq c , then the algorithm runs a crash agreement and agreement is guaranteed. Now consider |Q_{w}|>c . By the induction hypothesis, \mbox{\tt RCA}[Q_{2w},v_{in}] satisfies agreement. Let v be the decision value of \mbox{\tt RCA}[Q_{2w},v_{in}] . We consider the following two cases. (a) HD_{2w}\neq\emptyset : In this case, there exists a processor p\in HD_{2w} that broadcasts v successfully during the dissemination step. Hence, every processor in Q_{2w+1} executes \mbox{\tt RCA}[Q_{2w+1},v_{in}^{\prime}] with input v , and by the validity of \mbox{\tt RCA}[Q_{2w+1},v_{in}^{\prime}] , every processor in H_{2w+1} returns v from \mbox{\tt RCA}[Q_{2w+1},v_{in}^{\prime}] . Hence, every non-faulty processor in Q_{w} sets v_{out}\leftarrow v and returns v from the execution of \mbox{\tt RCA}[Q_{w},v_{in}] . (b) HD_{2w}=\emptyset : In this case, every processor in H_{2w} crashed before the start of \mbox{\tt RCA}[Q_{2w+1},v_{in}^{\prime}] , therefore H_{w}\subseteq H_{2w+1} . By the induction hypothesis, \mbox{\tt RCA}[Q_{2w+1},v_{in}^{\prime}] guarantees agreement. Let v be the decision value of \mbox{\tt RCA}[Q_{2w+1},v_{in}^{\prime}] . Hence, every processor in H_{w}\subseteq H_{2w+1} sets v_{out}\leftarrow v and returns v from the execution of \mbox{\tt RCA}[Q_{w},v_{in}] . Thus, agreement is satisfied by the execution of \mbox{\tt RCA}[Q_{w},v_{in}] . ∎ Complexity. The time complexity of Algorithm 2 is O(|Q|)=O(n) , since the Time complexity follows the formula T(n)=O(1)+2T(n/2) . where T(x)=O(1) for every 0c . We consider two cases. (1) p\in Q_{2w} : Then p receives all of its messages before or during the execution of \mbox{\tt RCA}[Q_{2w},v_{in}] in Line 2 . Since \mbox{\tt RCA}[Q_{2w},v_{in}] satisfies 1-preference by the induction hypothesis, every processor p^{\prime}\in H_{2w} returns 1. Hence, p decides 1 . (2) p\in Q_{2w+1} : Then p either has input 1, or it receives 1 after the first recursive call in Line 2 . \bullet If the input of p is 1, then it successfully sends 1 to every processor in Q_{2w} , before the execution of the first recursive call in Line 2 . Hence, \mbox{\tt RCA}[Q_{2w},v_{in}] returns 1 at every processor p\in H_{2w} . Therefore, p runs the second recursive call \mbox{\tt RCA}[Q_{2w+1},v_{in}] in Line 2 with v_{in}=1 (because it either uses its own input value which is 1, or it uses the decision value of the first recursive call which is also 1). By the induction hypothesis, \mbox{\tt RCA}[Q_{2w+1},v_{in}] satisfies 1-preference, hence it returns 1 at every p^{\prime}\in H_{2w+1} . Therefore, p decides 1. \bullet If p receives 1 after the first recursive call, then it runs \mbox{\tt RCA}[Q_{2w+1},v_{in}] with v_{in}=1 and again by the induction hypothesis, \mbox{\tt RCA}[Q_{2w+1},1] returns 1 at every processor p^{\prime}\in H_{2w+1} . Therefore, p decides 1. ∎