Consider the consensus problem in a non-totally decentralized control system where the system is partitioned into a set of units. A centralized control method (majority voting) is used for the PEs within each unit and a decentralized method is used to get a global decision among these units. The whole decision process consists of three stages:

(a) Local decision: Each local supervisor does a one-round majority voting on the values collected from its local PEs.

(b) Global decision: A decentralized decision algorithm (for the Byzantine generals problem) is applied at the local supervise level.

(c) Value dispatching: Each local supervisor dispatches its final value to its local PEs.

Assume there are n1 units with n 2

PEs including the local supervisor in each unit. Let m be the number of Byzantine faults (a Byzantine fault can be a local supervisor or a PE) in the system.

(i) Determine the following three cases by defining m in terms of n 1 and n 2 :
• There exists an agreement algorithm among all the healthy nodes.
• There does not exist such an algorithm.
• There may or may not exist such an algorithm depending on the distribution of Byzantine faults.
Justify your results.
(ii) Discuss the selection of n 1 and n 2 when the total number of PEs in the system is given.