Proactive resource allocation for asynchronous real-time distributed systems in the presence of processor failures

We present two proactive resource allocation algorithms, RBA^*-FT and OBA-FT, for fault-tolerant asynchronous real-time distributed systems. The algorithms consider an application model where task timeliness is specified by Jensen's benefit functions and the anticipated application workload during future time intervals is described by adaptation functions. In addition, we assume that reliability functions of processors are available a priori. Given these models, our objective is to maximize aggregate task benefit and minimize aggregate missed deadline ratio in the presence of processor failures. Since determining the optimal solution is computationally intractable, the algorithms heuristically compute sub-optimal resource allocations, but in polynomial time. Experimental results reveal that RBA^*-FT and OBA-FT outperform their non-fault-tolerant counterparts in the presence of processor failures. Furthermore, RBA^*-FT performs better than OBA-FT, although OBA-FT incurs better worst-case and amortized computational costs. Finally, we observe that both algorithms robustly withstand errors in the estimation of anticipated failures.     

Fault-accommodation with intelligent sensors

Optimal sensor fault-accommodation is considered for faults modelled by an increase in measurement noise. This noise is taken to be bounded and its probabilistic properties unknown. It is assumed that intelligent (e.g. self-validating) instrumentation is in use and estimates of the noise bounds are available. The fault-tolerant controller is designed to optimize a noise rejection and a nominal reference tracking index and leads to a mixed norm minimization problem (l₁/l₂). We exploit known results and a particular feedback configuration to show that it is possible to optimize simultaneously without a trade-off the two performance indices. The results are applied to systems where the presence of auxiliary measurements allows for an optimal fault-accommodation strategy. Using properties of the optimal solution, we define a factorization for the optimal controller alternative to the Youla parametrization, leading to an algorithm which is optimal, transparent and efficient.     

Self-stabilizing depth-first token circulation on networks

Summary This paper proposes a self-stabilizing protocol which circulates a token on a connected network in nondeterministic depth-first-search order, rooted at a special node. Starting with any initial state in which the network may have no token at all or more than one token, the protocol eventually makes the system stabilize in states having exactly one circulating token. With a slight modification to the protocol —by removing nondeterminism in the search — a depth-first-search tree on the network can be constructed. The proposed protocol runs on systems that allow parallel operations. Shing-Tsaan Huang was born in Taiwan on September 4, 1949. He got his Ph.D. degree in 1985 from Department of Computer Science, University of Maryland at College Park. Before he pursued his Ph.D. degree, he had worked several years in the computer industry in Taiwan. Professor Huang is currently the chairman of the Department of Computer Science, Tsing Hua University, Taiwan, Republic of China. His research interests include interconnection networks, operating systems and distributed computing. He is a senior member of the IEEE Computer Society and a member of the Association for Computing Machinery. Nian-Shing Chen was born in Taiwan on October 21, 1961. He received his Ph.D. degree in computer science from National Tsing Hua University in 1990. Dr. Chen is currently an associate professor with the Department of Information Management at Sun Yat-Sen University of Taiwan. His research interests include distributed systems, computer networks, computer viruses and expert systems. He is a member of IEEE and Phi Tau Phi honorary society.This research is supported by National Science Council of the Republic of China under the contract NSC81-0408-E-007-05 and NSC82-0408-E-007-027     

Automated synthesis of multiple analog circuits using evolutionary computation for redundancy-based fault-tolerance

Analog circuits are one of the most important parts of modern electronic systems and the failure of electronic hardware presents a critical threat to the completion of modern aircraft, spacecraft, and robot missions. Compared to digital circuits, designing fault-tolerant analog circuits is a difficult and knowledge-intensive task. A simple but powerful method for robustness is a redundancy approach to use multiple circuits instead of single one. For example, if component failures occur, other redundant components can replace the functions of broken parts and the system can still work. However, there are several research issues to make the redundant system automatically. In this paper, we used evolutionary computation to generate multiple analog circuits automatically and then we combined the solutions to generate robust outputs. Evolutionary computation is a natural way to produce multiple redundant solutions because it is a population-based search. Experimental results on the evolution of the low-pass, high-pass and band-stop filters show that the combination of multiple evolved analog circuits produces results that are more robust than those of the best single circuit.     

Accelerating incremental checkpointing for extreme-scale computing

Concern is beginning to grow in the high-performance computing (HPC) community regarding the reliability of future large-scale systems. Disk-based coordinated checkpoint/restart has been the dominant fault tolerance mechanism in HPC systems for the past 30 years. Checkpoint performance is so fundamental to scalability that nearly all capability applications have custom checkpoint strategies to minimize state and reduce checkpoint time. One well-known optimization to traditional checkpoint/restart is incremental checkpointing, which has a number of known limitations. To address these limitations, we describe libhashckpt, a hybrid incremental checkpointing solution that uses both page protection and hashing on GPUs to determine changes in application data with very low overhead. Using real capability workloads and a model outlining the viability and application efficiency increase of this technique, we show that hash-based incremental checkpointing can have significantly lower overheads and increased efficiency than traditional coordinated checkpointing approaches at the scales expected for future extreme-class systems.     

Low-latency atomic broadcast in the presence of contention

The Atomic Broadcast algorithm described in this paper can deliver messages in two communication steps, even if multiple processes broadcast at the same time. It tags all broadcast messages with the local real time, and delivers all messages in the order of these timestamps. Both positive and negative statements are used: “m broadcast at time 51” vs. “no messages broadcast between times 31 and 51”. To prevent crashed processes from blocking the system, the -elected leader broadcasts negative statements on behalf of the processes it suspects () to have crashed. A new cheap Generic Broadcast algorithm is used to ensure consistency between conflicting statements. It requires only a majority of correct processes (n > 2f) and, in failure-free runs, delivers all non-conflicting messages in two steps. The main algorithm satisfies several new lower bounds, which are proved in this paper.     

无数据缓存的容错环形NoC

提出一种分层双组双环NoC拓扑结构,该结构中链路分为两组环网,其中有一组环网为主环,另一组为备用环网,用于NoC网络的容错.每组环网中包含一个控制环和一个数据环,控制环采用包的形式交换结点之间路由、链路错误和差错控制信息,数据环用电路交换方式进行数据通信.针对以上NoC拓扑结构,提出交换结点无需缓冲区的三级流水线结构,使得各个IP之间的数据通信延时最小.环网中采用时分复用和优先级相结合的机制,实现了公平路由和带宽的空分复用.仿真结果表明,该结构可以有效避免拥塞、死锁和饥饿,保证带宽充分利用,与理论分析一致.     

Conference key agreement protocol with non-interactive fault-tolerance over broadcast network

Most conventional conference key agreement protocols have not been concerned with a practical situation. There may exist some malicious conferees who attempt to block conference initiation for some purposes, e.g. commercial, political or military benefit. Instances where conference must be launched immediately due to emergency, efficient detection of malicious behavior would be needed. Recently, Tzeng (IEEE Trans. Comput. 51(4):373–379, 2002) proposed a fault-tolerant conference key agreement protocol to address the issue where a conference key can be established among conferees even though malicious conferees exist. However, his protocol might be complex and inefficient during fault-detection. In the case where a malicious conferee exists and a fault-tolerant mechanism is launched, complicated interactions between conferees will be required. In this paper, we introduce a novel strategy, where any malicious conferee may be identified and removed from the conferee list without any interaction. With such a non-interactive fault-tolerance, conferences could be established and started efficiently. A complete example of our protocol will be given to describe the fascinating fault-tolerance. We analyse the security of our protocol regarding four aspects, i.e. correctness, fault-tolerance, active attack and passive attack. The comparisons of performance between our protocol and that of Tzeng are also shown. As a whole, the advantage of our protocol is superior to that of Tzeng under the situation where malicious conferees exist.

Dependency mining-based causal message logging

In fault-tolerant computing, the approach of causal message logging provides on-demand stable logging and enables the independent recovery of nodes. It imposes the requirement that the dependency between non-deterministic events needs to be known for nodes. The dependency information is disseminated through messages. A central problem in traditional causal message logging is that if the message logging progress of nodes cannot be effectively tracked, some redundant dependency information will be piggybacked on the messages. In this paper, a dependency mining based approach is proposed. It tries to detect the message logging progress of nodes only from the dependency between non-deterministic events, without needing to piggyback an additional dependency vector or dependency matrix on each message.     

Embedding a fault-free hamiltonian cycle in a class of faulty generalized honeycomb tori

Generalized honeycomb torus (GHT) is recognized as an attractive alternative to existing torus interconnection networks in parallel computing systems. Assume that m and d are integers with m ? 2 and d ? 8. This paper addresses the fault-tolerant hamiltonicity of GHT(m, 2d, d) with fault set F = {(w, y), (x, y)}, where w < x, w + y is even and x + y is odd. We show that such a faulty GHT is hamiltonian by presenting a systematic method for constructing a fault-free hamiltonian cycle. This result reveals another appealing feature of GHTs.