The space complexity of unbounded timestamps

The timestamp problem captures a fundamental aspect of asynchronous distributed computing. It allows processes to label events throughout the system with timestamps that provide information about the real-time ordering of those events. We consider the space complexity of wait-free implementations of timestamps from shared read-write registers in a system of n processes. We prove an lower bound on the number of registers required. If the timestamps are elements of a nowhere dense set, for example the integers, we prove a stronger, and tight, lower bound of n. However, if timestamps are not from a nowhere dense set, this bound can be beaten: we give an implementation that uses n − 1 (single-writer) registers. We also consider the special case of anonymous implementations, where processes are programmed identically and do not have unique identifiers. In contrast to the general case, we prove anonymous timestamp implementations require n registers. We also give an implementation to prove that this lower bound is tight. This is the first anonymous timestamp implementation that uses a finite number of registers.     

Asynchronous bounded lifetime failure detectors

A failure detector provides processes with a single primitive that, each time it is invoked, returns to the invoking process information related to failures. This research note extends failure detectors by allowing processes to invoke an additional primitive whose effect is to limit the time scope of some properties offered by the failure detector. This simple addition makes possible to weaken the definition of failure detector classes without weakening their power. Two distributed computing problems are used to illustrate the benefit of such an approach, namely the consensus problem and the construction of an atomic register.     

The weakest failure detector to solve nonuniform consensus

We determine the weakest failure detector to solve nonuniform consensus in any environment, i.e., regardless of the number of faulty processes. Together with previous results, this closes all aspects of the following question: What is the weakest failure detector to solve (uniform or nonuniform) consensus in any environment?     

When consensus meets self-stabilization

This paper presents a shared-memory self-stabilizing failure detector, asynchronous consensus and replicated state-machine algorithm suite, the components of which can be started in an arbitrary state and converge to act as a virtual state-machine. Self-stabilizing algorithms can cope with transient faults. Transient faults can alter the system state to an arbitrary state and hence, cause a temporary violation of the safety property of the consensus. Started in an arbitrary state, the long lived, memory bounded and self-stabilizing failure detector, asynchronous consensus, and replicated state-machine suite, presented in the paper, recovers to satisfy eventual safety and eventual liveness requirements. Several new techniques and paradigms are introduced. The bounded memory failure detector abstracts away synchronization assumptions using bounded heartbeat counters combined with a balance–unbalance mechanism. The practically infinite paradigm is introduced in the scope of self-stabilization, where an execution of, say, 2⁶⁴ sequential steps is regarded as (practically) infinite. Finally, we present the first self-stabilizing wait-free reset mechanism that ensures eventual safety and can be used to implement efficient self-stabilizing timestamps that are of independent interest.     

An impossibility about failure detectors in the iterated immediate snapshot model

The Iterated Immediate Snapshot model (IIS) is an asynchronous computation model where processes communicate through a sequence of one-shot Immediate Snapshot (IS) objects. It is known that this model is equivalent to the usual asynchronous read/write shared memory model, for wait-free task solvability. Its interest lies in the fact that its runs are more structured and easier to analyze than the runs in the shared memory model. As the IIS model and the shared memory model are equivalent for wait-free task solvability, a natural question is the following: Are they still equivalent for wait-free task solvability, when they are enriched with the same failure detector? The paper shows that the answer to this question is “no”.     

Implementing the weakest failure detector for solving the consensus problem

The concept of unreliable failure detector was introduced by Chandra and Toueg as a mechanism that provides information about process failures. This mechanism has been used to solve several agreement problems, such as the consensus problem. In this paper, algorithms that implement failure detectors in partially synchronous systems are presented. First two simple algorithms of the weakest class to solve the consensus problem, namely the Eventually Strong class (?S), are presented. While the first algorithm is wait-free, the second algorithm is f-resilient, where f is a known upper bound on the number of faulty processes. Both algorithms guarantee that, eventually, all the correct processes agree permanently on a common correct process, i.e. they also implement a failure detector of the class Omega (Ω). They are also shown to be optimal in terms of the number of communication links used forever. Additionally, a wait-free algorithm that implements a failure detector of the Eventually Perfect class (?P) is presented. This algorithm is shown to be optimal in terms of the number of bidirectional links used forever.     

一种新的用于分布共享存储系统的存储器一致性算法

ＳＶＭ系统或称ＤＳＭ系统是在基于分布存储器的多处理机上，实现物理上分布但逻辑上共享的存储系统．它集共享存储器易于编程和分布存储器可扩充性好于一体，为ＭＰＰ计算机的使用带来了方便．本文首先介绍了ＳＶＭ系统的数据一致性问题及其解决办法，然后提出了一种新的固定分布管理算法ＮＦＤＭＡ，并对此算法作了分析，最后与李凯的固定分布管理算法作了比较．     

A weakest failure detector-based asynchronous consensus protocol for f<n

has been shown to be the weakest realistic failure detector class needed to solve the consensus problem in an asynchronous distributed system prone to f<n process crashes in which communication is by message-passing. However, the only protocol that is known to meet this bound is based on three layers of protocol construction, and is therefore not efficient. This paper presents a surprisingly simple and very efficient direct message-passing implementation of a -based consensus protocol, and proves its correctness.     

Non-blocking atomic commit in asynchronous distributed systems with failure detectors

This paper addresses the Non-Blocking Atomic Commit (NB-AC) problem in asynchronous distributed systems augmented with failure detectors. We first show that, in these systems, NB-AC and Consensus are incomparable. Roughly speaking, there is a failure detector that solves NB-AC but not Consensus and a failure detector that solves Consensus but not NB-AC. Then we introduce the Anonymously Perfect failure detector . We show that, to solve NB-AC, is necessary (while is not), whereas is sufficient when a majority of the processes are correct. We draw from our results some observations on the practical solvability of NB-AC. Received: August 2000 / Accepted: May 2001     

Fast timing-based algorithms

Summary.  Concurrent systems in which there is a known upper bound Δ on memory access time are considered. Two prototypical synchronization problems, mutual exclusion and consensus, are studied, and solutions that have constant (i.e. independent of Δ and the total number of processes) time complexity in the absence of contention are presented. For mutual exclusion, in the absence of contention, a process needs only five accesses to the shared memory to enter its critical section, and in the presence of contention, the winning process may need to delay itself for 4 ⋅ Δ time units. For consensus, in absence of contention, a process decides after four accesses to the shared memory, and in the presence of contention, it may need to delay itself for Δ time units. Received: July 1993/Accepted: February 1996     

A methodology to automatically optimize dynamic memory managers applying grammatical evolution

Modern consumer devices must execute multimedia applications that exhibit high resource utilization. In order to efficiently execute these applications, the dynamic memory subsystem needs to be optimized. This complex task can be tackled in two complementary ways: optimizing the application source code or designing custom dynamic memory management mechanisms. Currently, the first approach has been well established, and several automatic methodologies have been proposed. Regarding the second approach, software engineers often write custom dynamic memory managers from scratch, which is a difficult and error-prone work. This paper presents a novel way to automatically generate custom dynamic memory managers optimizing both performance and memory usage of the target application. The design space is pruned using grammatical evolution converging to the best dynamic memory manager implementation for the target application. Our methodology achieves important improvements (62.55% and 30.62% better on average in performance and memory usage, respectively) when its results are compared to five different general-purpose dynamic memory managers.     

传统报文捕获平台性能影响因素分析

目前网络带宽日益增大,普通网络报文捕获平台已经成为大规模宽带网络的入侵检测系统,宽带网络防火墙,高性能路由器等工程的瓶颈。对于日益发展的高速网络,迫切需要分析出普通报文捕获平台的性能瓶颈,研究出高速通信接口,以便有效地提高主机服务器的响应速度。     

On-line signature verification system with failure to enrol management

In this paper we introduce a new biometric verification system based on on-line signatures and simulate its operation. For this purpose we have split the MCYT signature database in three subsets: one for classifier training, another for system adjustment and a third one for system testing simulating enrolment and verification. This context corresponds to a real operation, where a new user tries to enrol an existing system and must be automatically guided by the system in order to detect the failure to enrol (FTE) situations. The main contribution of this work is the management of FTE situations by means of a new proposal, called intelligent enrolment, which consists of consistency checking in order to automatically reject low quality samples. This strategy enhances the performance of the system to 22% when 8% of the users are left out. In this situation 8% of the people cannot be enroled in the system and must be verified by other biometrics or by human abilities. These people are identified with intelligent enrolment and the situation can be thus managed. In addition we also propose a DCT-based feature extractor with threshold coding and discriminability criteria.     

Using local memory to boost the performance of FFT algorithms on the CRAY-2 supercomputer

One of the many interesting architectural features of the CRAY-2 supercomputer is that each processor has access to 16K 64-bit words of local memory. This is in addition to the extremely large, 268-million-word common memory that is accessible by all four processors. By using local memory judiciously, it is possible to achieve increased performance on the CRAY-2. This is partly because accesses to local memory can be done simultaneously with accesses to common memory and other operations. Also, it is slightly faster to start up a vector access to local memory, and a processor does not have to compete with other processors when accessing its local memory. In this paper, we present an algorithm for computing the fast Fourier transform that takes advantage of the CRAY-2's local memory. It operates by solving subproblems, which are themselves Fourier transforms, entirely within local memory. By doing so it achieves a performance increase of between 25 and 40 percent over an equivalent algorithm that uses only common memory, and for some input sizes is able to outperform the CRAY-2 library FFT.     

Application of AC plasma display panels to radiation detectors

Radiation detector proposals that use plasma display panels are rare. In this work, we confirmed a radiation detector that uses plasma display panels that are focused on the breakdown voltage shift in the ramp waveform. We adapted the cell structures, gas contents, and waveforms of plasma display panels (AC‐PDPs) for radiation detectors. Hard X‐rays and gamma rays induce electron emission into the discharge gas, resulting in generating electrons, electron multiplication, and charge accumulation on dielectrics. The radiation dose rate of hard X‐rays and gamma rays (Cs137) is measured as a breakdown voltage shift between anodes and cathodes. For gamma rays, the detection sensitivity in this experiment is not as high as in the case of hard X‐rays, but the detector can locate gamma rays. These results suggest that adapted AC‐PDPs can detect both hard X‐rays and gamma rays and can be used in a large two‐dimensional radiation detector.     

Using asynchrony and zero degradation to speed up indulgent consensus protocols

Existing consensus protocols suffer from slowdowns caused by the failures of processes and the mistakes made by the underlying oracles. In this paper, we propose two novel techniques to circumvent such slowdowns in failure-detector-based consensus protocols. The first technique guarantees the Round-Zero-Degradation (RZD) property (an extension of the Zero-Degradation property) in order to avoid the slowdown caused by a failed coordinator process. The second technique, named “Look-Ahead”, helps speed up the execution of the consensus protocol by making use of the messages delivered before their receivers enter the corresponding phases or rounds. The first technique is effective only when the underlying failure detector makes no or few mistakes, while the second technique always works well regardless of the performance of the failure detector. Moreover, Look-Ahead is a general technique and can be applied to consensus protocols based on any kind of oracle. By applying the two proposed techniques, several consensus protocols are developed. The simulation results show that the RZD technique is effective even if the error rate of the failure detector reaches about 15%, while the Look-Ahead technique can always improve the performance in all cases.     

The Failure Trace Archive: Enabling the comparison of failure measurements and models of distributed systems

With the increasing presence, scale, and complexity of distributed systems, resource failures are becoming an important and practical topic of computer science research. While numerous failure models and failure-aware algorithms exist, their comparison has been hampered by the lack of public failure data sets and data processing tools. To facilitate the design, validation, and comparison of fault-tolerant models and algorithms, we have created the Failure Trace Archive (FTA)—an online, public repository of failure traces collected from diverse parallel and distributed systems. In this work, we first describe the design of the archive, in particular of the standard FTA data format, and the design of a toolbox that facilitates automated analysis of trace data sets. We also discuss the use of the FTA for various current and future purposes. Second, after applying the toolbox to nine failure traces collected from distributed systems used in various application domains (e.g., HPC, Internet operation, and various online applications), we present a comparative analysis of failures in various distributed systems. Our analysis presents various statistical insights and typical statistical modeling results for the availability of individual resources in various distributed systems. The analysis results underline the need for public availability of trace data from different distributed systems. Last, we show how different interpretations of the meaning of failure data can result in different conclusions for failure modeling and job scheduling in distributed systems. Our results for different interpretations show evidence that there may be a need for further revisiting existing failure-aware algorithms, when applied for general rather than for domain-specific distributed systems.     

BP网络在设备故障诊断中的应用与实现

神经网络技术为电子设备故障诊断提供了一种新的推理诊断方法。本文分析和介绍了BP人工神经网络的结构和学习算法，并加以实现。利用该方法，对测得的样本数据进行实验分析，证明此系统具有推理效率及准确性较高的特点。     

Innovations generation in the presence of unknown inputs: Application to robust failure detection

The first step in innovations-based failure detection is the construction of an innovations generator, i.e. a filter which, in the absence of failures from the inputs and the outputs of the system, generates a zero-mean white process with known covariance called innovations. A decision on whether a failure has occurred is then made by monitoring and applying statistical tests to this innovations process. In this paper, a method for constructing innovations in the case where the model contains unknown inputs and disturbances is presented. The solution is complete in the sense that it covers ‘singular’ cases.