Uma Estratégia de Testes Logarítmica para o Algoritmo Hi-ADSD
Abstract
The Hierarchical Adaptive Distributed System-level Diagnosis (Hi- ADSD) is a distributed diagnosis algorithm that creates a virtual topology based on a hypercube. A hypercube is a scalable structure by definition, presenting important topological features like: symmetry, logarithmic diameter and good fault tolerance properties. The latency of the algorithm executed on a system with N nodes is at most log2^2 N However, the number of executed tests in the worst case is quadratic. This work presents a new testing strategy for the Hi-ADSD algorithm, which guarantees that at most N log2 N tests are executed at each log2 N testing rounds. The maximum latency is mantained in log2^2 N testing rounds. The algorithm is adapted to the new testing strategy. Furthermore, the use of timestamps is adopted to allow each node to retrieve diagnosis information from several other nodes, thus reducing the average latency. The new algorithm is specified, formal proofs are given, and experimental results obtained by simulations are presented and compared with the Hi-ADSD algorithm.
References
Duarte Jr., E., Ziwich, R., and Albini, L. (2011). A survey of comparison-based system-level diagnosis. ACM Computing Surveys.
Duarte Jr., E. P., Albini, L., Brawerman, A., and Guedes, A. (2009). A hierarquical distributed fault diagnosis algorithm based on clusters with detours. In Network Operations and Management Symposium, 2009. LANOMS 2009. Latin American, pages 1–6.
Duarte Jr., E. P. and Nanya, T. (1998). A Hierarquical Adaptive Distributed System-Level Diagnosis Algotithm. IEEE Transactions on Computers., 47(1):34–45.
Hakimi, S. L. and Nakajima, K. (1984). On Adaptive System Diagnosis. IEEE Transactions on Computers., C-33(3):234–240.
Hosseini, S. H., Kuhl, J. G., and Reddy, S. M. (1984). A Diagnosis Algorithm for Distributed Computing Systems with Dynamic Failure and Repair. IEEE Transactions on Computers., C-33(3):223–233.
LaForge, L., Korver, K., and Fadali, M. (2003). What designers of bus and network architectures should know about hypercubes. Computers, IEEE Transactions on, 52(4):525–544.
MacDougall, M. (1987). Simulating computer systems: techniques and tools. MIT Press, Cambridge, MA, USA.
Masson, G., Blough, D., and Sullivan, G. (1996). Fault-tolerant computer system design. chapter System diagnosis, pages 478–536. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
Preparata, F., Metze, G., and Chien, R. T. (1967). On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers., 16:848–854.
