A distance bounding protocol enables one party to determine a practical upper bound on the distance to another party. It is an effective countermeasure against mafia fraud attacks (a.k.a. relay attacks) which do not alter messages between users but only relay messages. The main idea of distance bounding protocols is to repeat fast bit exchanges. One party sends a challenge bit and another party answers with a response bit and vice versa. By measuring the round-trip time between the challenge and the response, an upper bound on the distance between users can be calculated. If messages are relayed, the round-trip time increases and thus mafia fraud attacks can be detected. We introduce an efficient distance bounding protocol for mutual authentication. It enjoys a reduced false acceptance rate under mafia fraud attacks and does not require an extra confirmation message after the fast bit exchange phase.

The problem of finding an optimal product sequence for sequential multiplication of a chain of matrices (the matrix chain ordering problem, MCOP) is well-known. We consider the problem of finding an optimal product schedule for evaluating a chain of matrix products on a parallel computer (the matrix chain scheduling problem, MCSP). The difference between MCSP and MCOP is that MCOP pertains to a product sequence for single processor systems and MCSP pertains to a sequence of concurrent matrix products for parallel systems. The approach of parallelizing each matrix product after finding an optimal product sequence for single processor systems does not always guarantee minimum evaluation time on parallel systems since each parallelized matrix product may use processors inefficiently. We introduce a new processor scheduling algorithm for MCSP which reduces the evaluation time of a chain of matrix products on a parallel computer, even at the expense of a slight increase in the total number of operations. Given a chain of n matrices and a matrix product utilizing at most P/k processors in a P-processor system, the proposed algorithm approaches k(n-1)/(n+klog(k)-k) times the performance of parallel evaluation using the optimal sequence found for MCOP. Experiments performed on a Fujitsu AP1000 multicomputer also show that the proposed algorithm significantly decreases the time required to evaluate a chain of matrix products in parallel systems.

Fault-tolerant computer systems are being used increasingly in such applications as e-commerce, banking, and stock trading, where privacy and integrity of data are as important as the uninterrupted operation of the service provided. While much attention has been paid to the protection of data explicitly communicated over the Internet, there are also other sources of information leakage that must be addressed. This paper addresses one such source of information leakage caused by checkpointing, which is a common method used to provide continued operation in the presence of faults. Checkpointing requires communication of memory state information, which may contain sensitive data, over the network to a reliable backing store. Although the method of encrypting all of this memory state information can protect the data, such a simplistic method is an overkill that can result in a significant slowdown of the target application. This paper examines ways to combine the operations required to perform incremental checkpointing with those required to encrypt this memory state data. Analysis and experimentation on an actual system are used to show that the proposed secure checkpointing schemes are feasible and require a relatively low level of overhead.

Presents an efficient and robust algorithm to compute the intersection curve of two ringed surfaces, each being the sweep /spl cup//sub u/C/sup u/ generated by a moving circle. Given two ringed surfaces /spl cup//sub u/C/sub 1//sup u/ and /spl cup//sub v/C/sub 2//sup v/, we formulate the condition C/sub 1//sup u//spl cap/C/sub 2//sup v//spl ne/O (i.e. that the intersection of the two circles C/sub 1//sup u/ and C/sub 2//sup v/ is non-empty) as a bivariate equation /spl lambda/(u,v)= 0 of relatively low degree. Except for some redundant solutions and degenerate cases, there is a rational map from each solution of /spl lambda/(u,v)=0 to the intersection point C/sub 1//sup u//spl cap/C/sub 2//sup v/. Thus, it is trivial to construct the intersection curve once we have computed the zero-set of /spl lambda/(u,v)=0. We also analyze some exceptional cases and consider how to construct the corresponding intersection curves.

Recently proposed probabilistic checkpointing has one drawback, naming aliasing. When analyzed, 64-bit signatures show negligible possibility of aliasing. But in practice, the shift-XOR signature generation function used with probabilistic checkpointing shows a high aliasing rate, which limits the practicality of probabilistic checkpointing. In this paper, two enhancements are considered to make probabilistic checkpointing more reliable. One is the signature generation function and the other is the recovery scheme. In the signature generation function part, we propose two signature generation functions: HALF for small block sizes (less than or equal to 256 bytes) and C-HALF(CRC combined HALF) for large block sizes (larger than 256 bytes), which have an aliasing probability similar to analytic results and small overhead. In the recovery scheme part, we propose a recovery scheme which ensures the safety of probabilistic checkpointing. To examine the correctness of previous checkpoints at recovery time, the proposed recovery scheme uses a spare node. We analyze the recovery scheme using a mathematical model. Also an optimal checkpoint interval is derived using the model.

In this paper we propose a real-time communication scheme that can be used in general point-to-point real-time multicomputer systems with wormhole switching. Real-time communication should satisfy the two requirements of predictability and priority handling. Since traditional wormhole switching does not support priority handling which is essential in real-time computing, flit-level preemption is adopted in our wormhole switching. Also, we develop an algorithm to determine the message transmission delay upper bound to predict worst-case message delay. Simulation results show that the delay upper bounds calculated using the proposed algorithm are very close to actual average message transmission delays for messages with high priorities.

In this paper, we consider the mesh with a single bus as a multi-computer topology that enhances the communication capability of the mesh and show that the mesh with a single bus has more salient properties than the mesh, the hypercube, and other mesh variants. These properties are small diameter, relatively small degree, small average distance, suitable for broadcasting, small initial data distribution time, etc. We propose a dynamic load distribution algorithm to utilize the enhanced communication capability of the mesh with a single bus. Also, asynchronous bus control and arbitration logic is designed to support the proposed algorithm efficiently. It is shown through simulation that the proposed dynamic load distribution is superior to the previous receiver-initiated diffusion method known as the best to-date. The proposed algorithm shows better total execution time of tasks and better processor utilization with a smaller number of task migrations.

In this paper, we present the problem of scheduling real-time jobs in a hypercube system and propose a scheduling algorithm. The goals of the proposed scheduling algorithm are to determine whether all jobs can complete their processing before their fixed deadlines in a hypercube system and to find such a schedule. Each job is associated with a computation time, a deadline, and a dimensional requirement. Determining a schedule such that all jobs meet before their respective fixed deadlines in a hypercube system when preemption is not allowed is an NP-complete problem. Hence, we present a heuristic scheduling algorithm for scheduling non-preemptable real-time jobs in a hypercube system. Finally, we evaluate the proposed algorithm using simulation.

For the automated design of PLAs (programmable logic arrays) with a minimum size, computationally efficient procedures are needed that can minimize functions of a large number of variables. For such minimization procedures, excessively long processing time and an excessively large memory requirement are major problems to overcome. An absolute minimization procedure is presented for standard PLAs with reduced computation time and memory space. The improvement achieved by this procedure, which is based on the decomposition of ratio sets, is mainly due to the detection of all essential prime implicants during the derivation of inclusion functions and to the merger of two procedures previously published by R.B. Cutler and S. Muroga (1987) into one efficient procedure.>

A scheme for an easily testable multiplier and the corresponding test generation procedures are presented. To provide 100% controllability of the summand-counter, the summand-generator is modified. The modified summand-generator can be implemented with little hardware overhead. Since the summands are 100% controllable, the summand-counter can be constructed with the minimum number of adder cells. The multiplier is not C-testable, but can be tested with a small numbers of test vectors, i.e. 3n+60 vectors. It requires only one extra input, whereas C-testable multipliers usually require at least four or five extra inputs and more adder cells along with extra circuitry. Using the modified summand-generator, other types of multipliers can be easily constructed to be testable with only one extra input. Test sets for these multipliers can be obtained using the same test generation approach.>

This correspondence describes two efficient algorithms for determining whether or not a given finite-state machine has a synchronizing sequence and a distinguishing sequence, respectively, and compares them with the well-known tree method. Compared with the tree method, these new algorithms are easier to implement and require less memory size. Since they do not require keeping and searching a look-back directory, they allow significant speed improvements.