Decentralized train control is ideal in that by distributing computation load over multiple cars, it allows extensibility to, for example, newly installed modules. Besides, compared to centralized control, the delay occurring in cooperative control over multiple devices can be significantly reduced. A technical challenge here is that the legacy software program has a monolithic structure and thus is not amenable to distributed execution. In this paper we present our attempt to tackle this challenge. In the attempt we proceed in two steps. First, we perform a reconstruction of the architecture of the control software. Specifically we decompose the existing software system into several modules that perform independent functions. Second, we devise a mechanism that can manage distributed execution of these modules. A timeliness analysis shows that the new architecture can accommodate addition of new features that the existing architecture could not perform without violating real-time deadlines.

There have been many bug prediction models built with historical metrics, which are mined from version histories of software modules. Many studies have reported the effectiveness of these historical metrics. For prediction levels, most studies have targeted package and file levels. Prediction on a fine-grained level, which represents the method level, is required because there may be interesting results compared to coarse-grained (package and file levels) prediction. These results include good performance when considering quality assurance efforts, and new findings about the correlations between bugs and histories. However, fine-grained prediction has been a challenge because obtaining method histories from existing version control systems is a difficult problem. To tackle this problem, we have developed a fine-grained version control system for Java, Historage. With this system, we target Java software and conduct fine-grained prediction with well-known historical metrics. The results indicate that fine-grained (method-level) prediction outperforms coarse-grained (package and file levels) prediction when taking the efforts necessary to find bugs into account. Using a correlation analysis, we show that past bug information does not contribute to method-level bug prediction.

This paper proposes a model checking-based approach to verification of asynchronous consensus algorithms, an important class of distributed fault-tolerant algorithms. The proposed approach can be used to verify these algorithms against agreement, which is the key safety property of this class of algorithms. A consensus algorithm typically has runs of unbounded length and unbounded queues or sets of messages in transit, thus its state space is often infinite. This property makes application of model checking difficult, because model checking is based on state space exploration. Our approach can limit the use of model checking to a single round of an algorithm, by using a finite state model that over approximates the behavior of any single round. As a result, the problem of infinite state spaces can be circumvented. In case studies, two consensus algorithms are verified using this approach.

Gossip is a scalable and easy-to-deploy broadcast method for distributed systems. In gossip a broadcast message is disseminated through repeated information exchanges between randomly chosen nodes. Gossip can also achieve high reliability using a large amount of redundant messages, but this also incurs high load on the network. This paper proposes a new gossip algorithm which incorporates network coding techniques to mitigate the high load. With random linear coding, each message propagated in the new algorithm is randomly generated from the broadcast message. Unlike in ordinary gossip, this feature prevents nodes from receiving an identical message more than once, allowing to achieve the same reliability at a lower message cost.

Triple modular redundancy (TMR) is a well-known technique for building fault-tolerant systems. In TMR, a module unit is triplicated, and the outputs of these three units are compared by a voter. In this paper we consider systems that consist of multiple TMR units in series. Only recently has it been found that even such simple systems can be configured into various structures. We propose (i) a method of calculating the reliability of cascaded TMR systems and (ii) an algorithm for finding a structure that maximizes reliability. The algorithm uses the branch and bound search algorithm, where candidate solutions are evaluated by means of the proposed reliability calculation method. We also show that some new structures have optimal reliability within some ranges of voter and module reliability.

This paper presents an approach to facilitating model checking of consensus protocols, a class of distributed protocols. Model checking is a successful formal verification method. However its application to these protocols is still not a common practice because of the following problems. First, model checking requires non-negligible users' efforts in representing the protocol under verification in the input language of a model checker. Second, these protocols usually induce an infinite state space, making model checking infeasible. To alleviate these problems, the proposed approach provides (i) a language for concisely describing consensus protocols and (ii) a translator from the proposed language to a mathematical formula that symbolically represents the entire behavior of the protocol. Once the formula is generated, one can model check the protocol by checking the satisfiability of the formula with a satisfiability modulo theories (SMT) solver. Several case studies demonstrate the usefulness of the proposed approach both in correctness proving and bug hunting.

Testing is essential to ensure the dependability of software systems. This paper proposes an automatic test case generation method using the NuSMV model checker. We consider state-transition testing based on Statechart specifications. Given a Statechart specification, our proposed method can automatically generate test cases that cover all states or all transitions in the Statechart. Finding such test cases requires traversing the state space of the system under test. In practice, however, the state space can often be very large and thus a fast search method is required. To this end our method makes full use of NuSMV. We devise a technique for modeling and analyzing Statecharts so that test cases can be extracted from the counterexamples produced by the model checker. The feasibility of our method is demonstrated through case studies.

Fault-prone module detection is important for assurance of software quality. We have proposed a novel approach for detecting fault-prone modules using spam filtering technique, named Fault-proneness filtering. In order to show the effectiveness of fault-proneness filtering, we conducted comparative study with a static code analysis tool, PMD. In the study, Fault-proneness filtering obtains higher F1than PMD.

Fault-prone module detection in source code is important for assurance of software quality. Most previous fault-prone detection approaches have been based on software metrics. Such approaches, however, have difficulties in collecting the metrics and in constructing mathematical models based on the metrics. To mitigate such difficulties, we have proposed a novel approach for detecting fault-prone modules using a spam-filtering technique, named Fault-Prone Filtering. In our approach, fault-prone modules are detected in such a way that the source code modules are considered as text files and are applied to the spam filter directly. In practice, we use the training only errors procedure and apply this procedure to fault-prone. Since no pre-training is required, this procedure can be applied to an actual development field immediately. This paper describes an extension of the training only errors procedures. We introduce a precise unit of training, "modified lines of code," instead of methods. In addition, we introduce the dynamic threshold for classification. The result of the experiment shows that our extension leads to twice the precision with about the same recall, and improves 15% on the best F1 measurement.

This paper describes a novel approach to detect variability in a software product line from its change history such that software changes are converted to vectors and a factor analysis is applied. To show the applicability of our approach, we conducted experimental applications using a software repository of automotive engine control software. As a result of the experiments, variability is detected from the change history of products.

We consider systems comprised of multiple triple modular redundancy (TMR) units in series. Only recently have researchers found that even such simple systems can be configured into various structures. We develop an algorithm for finding a structure that maximizes reliability. Using this algorithm we show that new structures have optimal reliability within some ranges of voter and module reliability.

Model checking is a successful formal verification technique; however, its application to fault-tolerant distributed algorithms is still not common practice. One major reason for this is that model checking requires non-negligible users¿ efforts in representing the algorithm to be verified in the input language of a model checker. To alleviate this problem we propose an approach which encompasses (i) a language for concisely describing fault-tolerant distributed algorithms and (ii) a translator from the proposed language to PROMELA, the input language of the SPIN model checker. To demonstrate the feasibility of our approach, we show the results of an experiment where we described and verified several algorithms for consensus, a well-known distributed agreement problem.

The fault-prone module detection in source code is of importance for assurance of software quality. Most of previous conventional fault-prone detection approaches have been based on using software metrics. Such approaches, however, have difficulties in collecting the metrics and constructing mathematical models based on the metrics. In order to mitigate such difficulties, we propose a novel approach for detecting fault-prone modules using a spam filtering technique. Because of the increase of needs for spam e-mail detection, the spam filtering technique has been progressed as a convenient and effective technique for text mining. In our approach, fault-prone modules are detected in a way that the source code modules are considered as text files and are applied to the spam filter directly. In order to show the usefulness of our approach, we conducted an experiment using source code repository of a Java based open source development. The result of experiment shows that our approach can classify more than 70% of software modules correctly.

In overlay networks, which are virtual networks for P2P applications, topology mismatching is known as a serious problem to be solved. So far several distributed algorithms have been proposed to reduce link cost caused by this problem. However, they often create long routes with a large number of hops, especially for long distance communications. In this paper, we propose a distributed algorithm to address this issue. This algorithm designates nodes in an overlay network as special nodes with some probability. A special node iteratively exchanges one of its links with a new, longer distance link, instead of a shorter one. The new links are extensively used for long distance communications. The simulation studies show that in the overlay networks constructed by this algorithm, the number of hops per route is reduced for long distance communications, at the cost of a slight increase in link cost.

The fault-prone module detection in source code is of importance for assurance of software quality. Most of previous fault-prone detection approaches are based on software metrics. Such approaches, however, have difficulties in collecting the metrics and constructing mathematical models based on the metrics. In order to mitigate such difficulties, we propose a novel approach for detecting fault-prone modules using a spam filtering technique, named Fault-Prone Filtering. Because of the increase of needs for spam e-mail detection, the spam filtering technique has been progressed as a convenient and effective technique for text mining. In our approach, fault-prone modules are detected in a way that the source code modules are considered as text files and are applied to the spam filter directly. This paper describes the training on errors procedure to apply fault-prone filtering in practice. Since no pre-training is required, this procedure can be applied to actual development field immediately. In order to show the usefulness of our approach, we conducted an experiment using a large source code repository of Java based open source project. The result of experiment shows that our approach can classify about 85% of software modules correctly. The result also indicates that fault-prone modules can be detected relatively low cost at an early stage.

The software projects are considered to be successful if the cost and the duration are within the estimated ones and the quality is satisfactory. To attain project success, the project management, in which the final status of project is estimated, must be incorporated.In this paper, we consider estimation of the final status(that is, successful or unsuccessful) of project by applying Bayesian classifier to metrics data collected from project. In order to attain high estimation accuracy rate, we must select only a set of appropriate metrics to be applied. Here we consider two selection methods: the first method by the experts and the second method by the statistical test.Then we conducted an experiment using 28 project data and 29 metrics data in an organization of a certain company. The result showed that the method by the test gave higher accuracy rates than the method by the experts, and Bayesian classifier with the test method is effective to estimate project success.

This paper presents a framework to specify and verify integrated services of a home network system (HNS). We first develop a modeling language to describe the HNS and the integrated services. Complementing our previous work, the language captures each appliance as an object consisting of properties and methods, encapsulating the underlying protocols and platforms. We then present a method that verifies the integrated services with symbolic model checking, by translating the proposed language into the SMV (symbolic model verifier) language. Thus, it is possible to validate if the integrated service is specified as intended, automatically and exhaustively. Using the proposed framework, service developers can effectively detect design flaws in a single integrated service, as well as feature interactions among multiple services, in early stages of service development.

Summary form only given. The dependability of an information system critically relies on that of its software. Reportedly, however, 70% of software projects fail in various ways. Obviously the system developed by a failed project can be problematic in assuring dependability. Clarifying the reasons why software projects fail and taking preventive measures are therefore key to successful development of dependable information systems. We present the results of our attempt to address this important issue. In this research attempt: (1) we designed a questionnaire that can be used to collect necessary data from software engineers. (2) We developed an analysis method that can identify reasons for project failures from the results of the questionnaire. This method uses a Bayesian classifier as its basis. (3) We conducted a large-scale experiment using field data obtained from industry. The results suggest that our method is useful to predict the success or failure of a software development project.

This paper proposes a self-organizing technique for enhancing the coverage of wireless micro-sensor networks after an initial random placement of sensors. A randomized back-off delay time is introduced to resolve the problem of simultaneous movement of sensors in the neighborhood which leads to unnecessary excessive movement and hence consume more sensors' energy. A sensor node relocates itself when the time calculated through randomized back-off delay computation is reached. The new location of the sensor is determined by a virtual force-directed algorithm where virtual attractive or repulsive forces exerted by other sensors or obstacles are used to guide the sensor to the desired location. The proposed self-organizing algorithm for sensor placement is proved to be effective through simulation.

Combinatorial testing is a specification-based testing criterion, which requires that for each t-way combination of input parameters of a system, every combination of valid values of these t parameters be covered by at least one test case. This approach is motivated by the observation that in many applications a significant number of faults are caused by interactions of a smaller number of parameters. We propose new test generation algorithms for combinatorial testing based on two artificial life techniques: a genetic algorithm (GA) and an ant colony algorithm (ACA). The usefulness of these algorithms is demonstrated through experiments. In the case t = 3 in particular, our algorithms exhibited impressive results.

Gossip-based multicast schemes have attracted increasing interest, because they are easy to deploy and resilient to failures. However, traditional gossip-based protocols rely on each process having knowledge of the global membership, thus limiting their scalability. To overcome this problem several protocols have been developed that can operate with processes having only a partial view of the global membership. We discuss the effects of partial views on the reliability of gossip-based multicast protocols. Specifically, we identify three desirable properties for views and show constructions of views satisfying these properties. Numerical results obtained show that reliability can be considerably affected by views adopted, especially in the presence of faulty processes.

The programmable service for Internet telephony (VoIP) allows end-users or third parties to define their own customized services. However, it imposes a serious drawback that service description created by end-users is likely to contain problems that are semantically ambiguous or inconsistent. To cope with this problem, we have so far proposed semantic warnings, which are the guidelines to guarantee the semantic correctness for the CPL (call processing language) programmable service environment. We evaluate the proposed semantic warnings with practical VoIP system, VOCAL (Vovida open communication application library). In the experiment, the proposed warnings revealed a semantic redundancy in a ready-made feature of VOCAL. It is also shown that customized features containing the semantic warnings often led VOCAL to problematic situations. Thus, the proposed warnings can help feature provisioning system to detect semantic flaws in programmable service environment.

Recent software systems contain a lot of functions to provide various services. According to this tendency, it is difficult to ensure software quality and to eliminate crucial faults by conventional software testing methods. Especially, in the conventional method, the detail level of test items are widely varied, according to the engineers' skill, and this causes an immature software quality. In this paper, we discuss the effects of test engineer skill on test item generation, and propose a new test item generation method, that enables the generation of test items for illegal behavior of the system. The proposed method can generate test items based on use-case analysis, deviation analysis for legal behavior, and fault tree analysis for system fault situations. From the result of the experimental applications, we confirmed that test items for illegal behavior of the system were effectively generated, and also the proposed method could effectively assist test item generation by poorly skilled engineers.

To predict software quality, we must consider various factors because software development consists of various activities, which the software reliability growth model (SRGM) does not consider. In this paper, we propose a model to predict the final quality of a software product by using the Bayesian belief network (BBN) model. By using the BBN, we can construct a prediction model that focuses on the structure of the software development process explicitly representing complex relationships between metrics, and handling uncertain metrics, such as residual faults in the software products. In order to evaluate the constructed model, we perform an empirical experiment based on the metrics data collected from development projects in a certain company. As a result of the empirical evaluation, we confirm that the proposed model can predict the amount of residual faults that the SRGM cannot handle.

According to a progress of the software process improvement, the time series data on the number of faults detected by the software testing are collected extensively. In this paper, we perform statistical analyses of relationships between the time series data and the field quality of software products. At first, we apply the rank correlation coefficient /spl tau/ to the time series data collected from actual software testing in a certain company, and classify these data into four types of trends: strict increasing, almost increasing, almost decreasing, and strict decreasing. We then investigate, for each type of trend, the field quality of software products developed by the corresponding software projects. As a result of statistical analyses, we showed that software projects having trend of almost or strict decreasing in the number of faults detected by the software testing could produce the software products with high quality.

In practical software development, software quality is generally evaluated by the number of residual defects. To keep the number of residual defects within a permissible value, too much effort is often assigned to software testing. We try to develop a statistical model to determine the amount of testing effort which is needed to assure the field quality. The model explicitly includes design, review, and test (including debug) activities. Firstly, we construct a linear multiple regression model that can clarify the relationship among the number of residual defects and the efforts assigned to design, review, and test activities. We then confirm the applicability of the model by statistical analysis using actual project data. Next, we obtain an equation based on the model to determine the test effort. As parameters in the equation, the permissible number of residual defects, the design effort, and the review effort are included. Then, the equation determines the test effort that is needed to assure the permissible residual defects. Finally, we conduct an experimental evaluation using actual project data and show the usefulness of the equation.

Feature interaction is a kind of inconsistent conflict between multiple communication services and considered an obstacle to developing reliable telephony systems. In this paper we present an automatic method for detecting feature interactions in service specifications. This method uses bounded model checking, a SAT-based automatic verification technique.

Testing is a crucial part of the development of software systems. In this paper, we consider testing of an implementation that is intended to satisfy a Boolean formula. In the literature, specification-based testing has been suggested for this purpose. Typically, such methods first hypothesize a fault class and then generate tests. However, there is almost no research that justifies fault classes proposed previously. Moreover, specifications amenable to automatic test generation are not always available to testers in practice. Based on these observations, we examine the applicability of non-specification-based approaches, which need no specification in the form of a Boolean formula to create tests. We compare a specification-based approach to three non-specification-based approaches, namely, random testing, antirandom testing, and combinatorial testing. The results of an experiment show that combinatorial testing is often comparative to specification-based testing and is superior to both random testing and antirandom testing.

In a previous paper, Kuhn [1999] showed that faults in Boolean specifications constitute a hierarchy with respect to detectability, and drew the conclusion that missing condition faults should be hypothesized to generate tests. However this conclusion was premature, since the relationships between missing condition faults and faults in other classes have not been sufficiently analyzed. In this note, we investigate such relationships, aiming to complement the work of Kuhn. As a result, we obtain an extended hierarchy of fault classes and reach a different conclusion.

This paper describes a test process improvement aiming to improve software quality in a large organization that has a large number of software projects. First, we identified activities in the testing process in the organization and analyzed their characteristics. As a result, we identified that dynamic tests have been performed well and static tests have been less performed. Improvement plan was requested that contributes to the product quality without increasing development efforts for the projects. We then decided a plan to introduce static analysis tools and establish the testing process in which static analysis tools are applied as much as possible. Implementation of the improvement plan consists of two steps: introductory and complete application of tools to the organization. The characteristics of this process improvement are not only that tools have been evaluated and confirmed in pilot projects before actual introduction but also procedures have been designed carefully for the application of the tools to projects. The effectiveness of this approach was confirmed in the analysis of applied projects in which static problems were removed successfully before system test.

The needs for accessibility of cellular phones to Web based client-server systems are increasing. For this access, efficient management of the context data must be implemented on the cellular phone. However, physical restrictions of the cellular phone make it difficult to manage context data by applying the conventional methods. Additionally the conventional methods do not show sufficient performance to tolerate heavy accesses from cellular phones. We therefore design a new session management mechanism that enables cellular phone to use Web client-server system efficiently. To do so, we decide to utilize key concepts in the CDS mechanism, which was previously developed by us in order to implement session management on the Web. By utilizing the CDS mechanism, we develop a new session management mechanism that connects cellular phone and Web systems. Then, we can actually implement the session management with high safety and reliability. The result of a benchmark evaluation shows that proposed mechanism has higher performance than the conventional mechanism.

Testing is a crucial part of the development of highly dependable systems. In this paper, we consider the testing of an implementation that is intended to satisfy a Boolean formula. In the literature, specification-based testing has been suggested for this purpose. Typically, such methods first hypothesise a fault class and then generate tests. However, there is almost no research that justifies the fault classes proposed previously. Moreover, the specifications available for automatic test generation are not always available to testers in practice. Based on these observations, we examine the applicability of non-specification-based approaches, which need no specification in the form of a Boolean formula to create tests. We compare a specification-based approach to two non-specification-based approaches, namely random testing and combinatorial testing, which is an emerging technique based on combinatorial designs. The results of an experiment show that combinatorial testing is often comparative to specification-based testing and is always much superior to random testing.

A distributed system is said to be self-stabilizing if it converges to safe states regardless of its initial state. In this paper we present our results of using symbolic model checking to verify distributed algorithms against the self-stabilizing property. In general, the most difficult problem with model checking is state explosion; it is especially serious in verifying the self-stabilizing property, since it requires the examination of all possible initial states. So far applying model checking to self-stabilizing algorithms has not been successful due to the problem of state explosion. In order to overcome this difficulty, we propose to use symbolic model checking for this purpose. Symbolic model checking is a verification method which uses Ordered Binary Decision Diagrams (OBDDs) to compactly represent state spaces. Unlike other model checking techniques, this method has the advantage that most of its computations do not depend on the initial states. We show how to verify the correctness of algorithms by means of SMV, a well-known symbolic model checker. By applying the proposed approach to several algorithms in the literature, we demonstrate empirically that the state spaces of self-stabilizing algorithms can be represented by OBDDs very efficiently. Through these case studies, we also demonstrate the usefulness of the proposed approach in detecting errors.

Even for electrical appliances, testing for illegal behaviors becomes difficult since the software system in an electrical appliance has already, become large in size. Actually the conventional method cannot generate sufficient test items for illegal behaviors. But testing illegal behaviors becomes more and more important, since the failure of electrical appliances would cause fatal effects on our daily life. We therefore propose a new method for generating appropriate test items to check illegal behaviors, which consists of the following steps: (1) describe software behavior using use case notation; (2) analyze illegal behavior by the deviation analysis technique; (3) construct a software fault tree using the above information; and (4) generate test items from the software fault tree. This paper also reports the experimental applications to actual development of an electrical appliance. The evaluation results identified that all necessary, test items for illegal behaviors are included in the resultant test items.

The authors identify key attributes of projects in which the number of problem reports after release is remarkable in the communication software. After several interviews with software project managers, we derived candidate attributes of importance to the projects. To find out the most influential attributes of the projects, we conducted statistical analysis using a set of metrics data related to the candidate attributes and the number of problem reports after release. As a result we successfully found that two metrics concerning the origin's quality and the changes in specification are useful to estimate the field quality.

Proposes new scheduling algorithms to achieve fault security in multiprocessor systems. We consider the scheduling of parallel programs represented by directed acyclic graphs with arbitrary computation and communication costs. A schedule is said to be 1-fault-secure if the system either produces correct output for a parallel program or it detects the presence of any single fault in the system. Although several 1-fault-secure scheduling algorithms have been proposed so far, they can all only be applied to a class of tree-structured task graphs with a uniform computation cost. In contrast, the proposed algorithms can generate a 1-fault-secure schedule for any given task graph with arbitrary computation costs. Applying the new algorithms to two kinds of practical task graphs (Gaussian elimination and LU-decomposition), we conduct simulations. Experimental results show that the proposed algorithms achieves 1-fault security at the cost of a small increase in schedule length.

During the process of software development, senior managers often find indications that projects are risky and take appropriate actions to recover them from this dangerous status. If senior managers fail to detect such risks, it is possible that such projects may collapse completely.

High productivity is required for industrial systems that are to produce large amounts of low-price products. Most industrial systems are sequentially controlled because materials and parts are processed and constructed step by step. A new method of sequential control is needed to increase productivity, and a new technique to schedule the start time of each process is also needed because of frequent adjustment of production lines and their equipment. Intelligent devices such as intelligent sensors and actuators used in the latest industrial systems have embedded high-performance processors and contain software modules. These devices cooperate and control processing robots and production lines. Advanced sequential control is proposed for sequential control systems consisting of distributed software modules. Processing time can be minimized and productivity increased by intelligent scheduling for advanced sequential control, and this paper describes a new method for adjusting the starting times of production processes automatically. This method shortens the time margin and decreases the total processing time. This paper also describes a processing flow diagram that makes it easy to adjust the starting time of each process. The effectiveness of this intelligent scheduling and start-time-adjustment has been demonstrated by using them to optimize the operation of a system for testing disk plates.

Discusses the estimation of the effort needed to update programs according to a given requirement change. In object-oriented prototyping development (OO prototyping), the requirement changes occur frequently and regularly. Thus, a simple and fast estimation of effort is strongly required by both developers and managers. However, existing estimation methods cannot be applied to OO prototyping. Therefore, we propose a straightforward approach to effort estimation, which reflects the specific properties of OO prototyping. First, we analyze the following characteristics of OO prototyping: (1) updating activities consist of creation, deletion and modification; (2) the target to be updated has four kinds of types (void type, basic type, library type and custom type); and (3) the degree of information hiding is classified into private, protected and public. Then, we present a new formula E(P,/spl sigma/) to calculate the effort needed to update a program P according to a set of requirement changes /spl sigma/. The formula E(P,/spl sigma/) includes the weighting parameters w/sub upd/, w/sub type/ and w/sub inf-h/ according to the characteristics (1), (2) and (3), respectively. Finally, we conduct experimental evaluations by applying the formula E(P,/spl sigma/) to actual project data in a certain company. The evaluation results prove statistically (to some extent) the validity of the proposed approach.

The Function Point Method, estimation by analogy, and algorithmic modeling are three of the most commonly applied methods used to estimate the costs and worker hours needed for a software development project. These methods, however, require a deep and wide expertise in particular areas and may still result in unacceptable discrepancies between the estimated costs and the actual costs. The paper presents a framework for a top-down cost estimation method (TCE). The method is based on the assumption that different types of software have different intrinsic complexities. We expect that this method will produce easier, faster, and more accurate estimations in the early stages of a software project.

The use of quorums is a well-known approach to achieving mutual exclusion in distributed environments. In this paper, we propose a new availability evaluation method for quorum-based mutual exclusion schemes in the presence of failures. Most of the previously proposed methods take neither the topology of systems nor link failures into consideration, and exhaustive state enumeration has been the only approach that can deal with them so far. By incorporating a notion called Minimal Quorum Spanning Trees, this method can efficiently evaluate the availability of quorum-based mutual exclusion schemes in general topology networks with unreliable nodes and links. Through experimental results, we show the superiority of the proposed method over exhaustive state enumeration.

The use of quorums is a well-known approach to achieving mutual exclusion in distributed computing systems. This approach works based on a coterie, a special set of node groups where any pair of the node groups shares at least one common node. Each node group in a coterie is called a quorum. Mutual exclusion is ensured by imposing that a node gets consensus from all nodes in at least one of the quorums before it enters a critical section. In a quorum-based mutual exclusion scheme, the delay for reaching consensus depends critically on the coterie adopted and, thus, it is important to find a coterie with small delay. Fu (1997) introduced two related measures called max-delay and mean-delay. The former measure represents the largest delay among all nodes, while the latter is the arithmetic mean of the delays. She proposed polynomial-time algorithms for finding max-delay and mean-delay optimal coteries when the network topology is a tree or a ring. In this paper, we first propose a polynomial-time algorithm for finding max-delay optimal coteries and, then, modify the algorithm so as to reduce the mean-delay of generated coteries. Unlike the previous algorithms, the proposed algorithms can be applied to systems with arbitrary topology.

Responsive communication protocols must incorporate both real-time and fault-tolerant properties. In this paper, we propose a new method for detecting design faults in specifications of responsive communication protocols based on real-time temporal logic. We also present a case study where a connection establishment protocol for a plant control system is dealt with.

This paper discusses how a backup virtual path (VP) between each pair of a source node and a destination node is set up such that when some nodes and links in primary VP's fail, primary VP's are changed to backup VP's rapidly. Then, this paper proposes a multiagent-based method for such rapid restoration from primary VP's to backup VP's. The proposed method consists of the following three steps. The first step enumerates candidates of backup VP between each pair of a source node and a destination node. In the second step, capacities of shared links in backup VP candidates between different pairs of a source node and a destination node are obtained. The last step determines a backup VP with the minimum capacities of shared links between each pair of a source node and a destination node. The proposed method has potentially good adaptability for change of both network resource such as topology and link capacity and resource requirements such as capacities of primary VP and backup VP.

This paper discusses the effects of estimation accuracy for software development cost on both the quality of the delivered code and the productivity of the development team. The estimation accuracy is measured by metric RE (relative error). The quality and productivity are measured by metrics FQ (field quality) and TP (team productivity). Using actual project data on thirty-one projects at a certain company, the following are verified by correlation analysis and testing of statistical hypotheses. There is a high correlation between the faithfulness of the development plan to standards and the value of RE (a coefficient of correlation between them is -0.60). Both FQ and TP are significantly different between projects with -10%<RE<+10% and projects with RE/spl ges/+10% (the level of significance is chosen as 0.05).

The responsiveness verification of a given communication protocol is to check whether the given protocol can recover from any abnormal state to a normal state within a permissible time or not. In order to make practical discussions, we assume that the lower and upper bounds of execution time are given for each message transfer and event. We propose a new responsiveness verification method which executes several events concurrently based on residual times of events, and develop a simulator which implements the proposed method. Then we present an experience which applies the simulator to the design of an actual connection establishment protocol for a certain plant control system. The system adopts the client server model and real time constraints exist on connection establishments. In the experience, we first specify the protocol straightforwardly. Then we apply the simulator to the specification and detect design faults against responsiveness. Next, we revise the specification successfully based on the state sequences generated by the simulator. The results of the experience conclude that the proposed method is effective for the case study.

We propose a new scheduling algorithm for achieving fault tolerance in multiprocessor systems. The new algorithm partitions a parallel program into subsets of tasks based on some characteristics of a task graph. Then for each subset, the algorithm duplicates and schedules its tasks successively. Applying the proposed algorithm to three kinds of practical task graphs (Gaussian elimination, Laplace equation solver and LU decomposition), we conduct simulations. Experimental results show that fault tolerance can be achieved at the cost of a small degree of time redundancy, and that performance in the case of a processor failure is improved compared to a previous algorithm.

In order to manage software projects quantitatively, we have presented a new model far software project based on generalized stochastic Petri-net model which can take influence of human factors into account, and we have already developed software project simulator based on GSPN model. This paper proposes methods for calculating model parameters in the new model and estimating the number of faults in the design and debug phases of software process. Then we present experimental evaluation of proposed method using a data of actual software development project on a certain company. As the result of case study, we confirmed its effectiveness with respect to estimating the number of faults in the software process.

This paper discusses safety analysis of design documents constructed by object-oriented development approaches. In our previously proposed method, whether design documents satisfy safety requirements is checked using some information tables, and these safety requirements are assumed to be given in advance. However, any systematic method that can derive such safety requirements from requirements specification and safety standards has not been developed. To overcome this problem, we propose a new FTA (Fault Tree Analysis)-based technique to derive safety requirements from requirements specification, component library, and design documents. Then, we apply the proposed method to typical examples taken from previous reports.

Design of practical routing protocols is complex and difficult due to complicated requirements of fault tolerance and flexibility. The protocol is defined to be fault-tolerant if messages can be rerouted via another path when the communication channel fails. In this paper, we propose a new synthesis method for generating a fault-tolerant routing protocol for a given service specification and a network topology. The routing protocol thus obtained adopts a multipath routing augmented with sets, where each set stores the next nodes for routing, and updates the sets according to network topology changes. Additionally, the routing protocol can attain flexibility by the multipath routing mechanism in the sense that only a small amount of changes is needed for addition or deletion of nodes. Finally, we show the effectiveness of the proposed method through an application to a typical routing service of message delivery from a source node to a destination node.

In this paper, we propose a new model for software projects and an estimation method for the quality, cost and delivery date.The new model consists of Project model and Process model.Project model focuses on three key components: activity, product and developer of the project.Process model includes a set of Activity models, each of which specifies design, coding, review, test, and debug activities respectively using GSPN.Moreover, the new model can take the influence of human factors into account by introducing the concept of "workload".Next, we develop a simulator which supports description of the target process, executes the process described by Activity model and analyses the simulation results statistically.Then, we apply the simulator to real software projects at certain organization and compare the estimated values with actual data.The experimental results show the applicability of the proposed simulator to manage real software project in the future.

The non-deterministic behavior in telecommunication services are well-known as one of the most typical feature interactions, and they should be detected and eliminated from the telecommunication service specifications. The conventional analysis method of this non-determinism is based on reachability analysis. Since the method must exhaustively enumerate all reachable global states, it cannot be applied to the complex communication services which include many users. We propose an alternative method based on a Petri-net model. The method constructs a logically equivalent Petri-net for a given service specification, and obtains a set of states which cause the non-deterministic behavior using rules in the service specification. Then, the method identifies states in the set which are not reachable from the initial state using the P-invariant of the Petri-net, and deletes them from the set. As the P-invariant is utilized as the necessary condition, we must finally apply reachability analysis to states in the resultant set. Since the number of states in the resultant set may be reduced to a relatively small value the new method enables us to analyze the more complex services.

In this paper we propose a new model for conformance testing of real-time protocols. First, we point out necessary properties for the model with respect to the following attributes: (1) the description and testing of the time constraints, (2) time-out processing. Although communicating finite state machine (CFSM) and its extension TCFSM are widely accepted as models for communication protocols, these models do not satisfy the necessary conditions, and are not suitable for testing real-time properties. Then we propose a new model CFSM-T which defines a new time constraint [l,u,d] to resolve time difference between clock (logical time) and timer (physical time) and changes the scope of description to processes only. Finally, we apply it to specify the alternating bit protocol. The result shows that the new model CFSM-T would be an effective model of real-time protocols for protocol conformance testing.

We proposed new metrics for computing the program complexity of object oriented programs (E.M. Kim et al., 1994). In these metrics, we examined program complexity from three dimensional viewpoints in object oriented paradigm: syntax dimension, inheritance dimension and interaction dimension. We have defined attributes to evaluate three viewpoints quantitatively. We present some heuristics for computing actual values of the attributes, for which we have given only definitions in a previous paper. Then, we analytically evaluate the new metrics with regard to E.J. Weyuker's (1988) measurement principles. As a result, it is found that our metrics satisfy essential properties which any measure must have. Finally, we develop the tool to compute the values of the attributes automatically.

We propose a timed reachability analysis method in order to generate system states of two classes of EFSM-based communication protocols; one class C1 consists of events such that the lower and upper bounds are all the same and the other class C2 consists of events such that they may be different. The proposed method enumerates only sequences of system states that are obtained through parallel execution of all possible events. Then, in order to evaluate the efficiency of the proposed method, we develop a verification tool based on the proposed method, and then apply the tool to a broadcasting protocol. The experimental results show that the total number of states generated by the proposed method is much less than that by the previous method.

The trend toward the enrichment of communication services in ISDN and IN has greatly increased the size and complexity of communication protocols which realize the services. A large and complex protocol is constructed by integrating components, each of which corresponds to a subfunction specified in a service specification. The conventional approach to this construction is to integrate components on the protocol level using the existing protocol integration methods. In this approach, the reachability analysis of protocol components is required in the integration stage. So if the size of components becomes large, the integration stage would be a bottleneck because of the state explosion problem of the reachability analysis. Therefore, we propose a new approach to construct the target protocol which, at first integrates components on the service specification level and then transforms an integrated service specification into the target protocol by the protocol synthesis technique. As a result, the construction of the target protocol from the component service specifications can be efficiently effected in a small state space without paying special attention to the timing of protocol messages.

In this paper, we present a routing protocol for finding two node-disjoint paths between each pair of nodes in a computer network. In the proposed protocol, each node in the network has the same procedure, which is driven by local information with respect to the network topology such as an adjacent node on a spanning tree in the network. Thus, the execution of the protocol can continue after changes of the network topology and load. The concept of spanning tree-based kernel construction is introduced to synchronize procedures under the distributed control of the protocol. The routing scheme based on the protocol possesses the enhanced capabilities of alternate routes and load splitting, which cope with failures and load variations in the network. Furthermore, even if topology changes occur which damage the obtained disjoint paths, the paths themselves can be updated efficiently.

This paper describes an actual experience of software process improvement at OMRON corporation.posed procedure are proven to be effective for reclucing the development effort at OM RON corporation.

We try to develop a new design review method to verify bath safety and correctness of software product simultaneously. In the proposed method, we assume that requirement specification and design specification are given, and that designers and verifiers participate to build several kinds of information tables from the specifications. At the beginning, the designers construct a design table based on a design specification, and the verifiers construct two verification tables. One of the verification tables includes semantic information, some of which is taken from the knowledge and experience of the verifiers. Then, by comparing the items of three tables, the verifiers review a given design specification and try to detect faults in it. The information contained in the tables is relatively easily extracted from the requirement and design specifications. Finally, by applying the proposed method to the examples of software design specification, we show that faults can be detected in the design review.

The paper statistically analyzes the relationship between review and software quality and the relationship between review and productivity, utilizing software metrics on 36 actual projects executed in the OMRON Corporation from 1992 to 1994. Firstly, by examining the relationship between review effort and field quality (the number of faults after delivery) of each project, and the relationship between the number of faults detected in review and field quality of each project, we reasoned that: (1) greater review effort helps to increase field quality (decrease the number of faults after delivery); (2) source code review is more effective in order to increase field quality than design review; (3) if more than 10% of total design and programming effort is spent on review, one can achieve a quite stable field quality. We noticed that no relevant effects were recognized in productivity (LOC/staff month) with respect to a review rate of up to 20%. As a result of the analysis above, we recommended that 15% of review effort is a suitable percentage to use as a guideline for our software project management.

We present a new framework for analyzing the scope of metrics to evaluate complexity of object-oriented programs. In this framework, we examine in detail the metrics from the viewpoint of three key aspects in object-oriented paradigm: syntax complexity, inheritance complexity and interaction complexity. For each key aspect, we expand it to five attributes, which can be calculated qualitatively. Then, we apply our framework to conventional metrics for evaluating complexity of object-oriented programs. The metrics include the ones proposed by S.R. Chidamber and C.F. Kemerer (1991), R.C. Sharble and S.S. Cohen (1993), W. Li and S. Henry (1993), and E. Kim (1993). Finally, we present a new metric which satisfies almost all attributes of the proposed framework.>

Protocol synthesis is used to derive a protocol specification based on a service specification. In the previous protocol synthesis methods, if the service specification includes simultaneous transmission of primitives, then the derived protocol specification includes protocol errors of unspecified receptions caused by message collisions. This paper extends a class of derived protocol specifications to include message collisions which often happen in real communication protocols, and proposes a protocol synthesis method such that (1) simultaneous transmission of primitives causing message collisions can be described in the service specifications, and (2) transitions for avoiding protocol errors of unspecified receptions can be generated by new transition synthesis rates. This paper also proposes a verification method for determining a real-time bound in the synthesized protocol specification using the task scheduling algorithm for multiprocessor systems.>

A new metric for evaluating the cost effectiveness of technical reviews is described. The proposed metric is based on the degree to which testing costs are reduced by technical reviews. The metric can be interpreted as combining two conventional metrics. Using an experimental evaluation of the conventional metrics and the proposed metric for data collected in an industrial environment, the authors show the validity and usefulness of the proposed metric. In particular, they present a method to estimate a value of the proposed metric by using only the values obtained at review phase.>

A fault analysis procedure is proposed for software development using JSP (Jackson structured programming). In the procedure, it is assumed that developers submit a fault report, which includes information (such as fault type, cause of fault and product) on actual fault correction activities. The procedure can identify the step in the JSP process at which fault might be introduced. Fault data are then collected from an experimental software development using JSP, and the procedure is applied to the data. The analysis result given by the proposed procedure can interpret the actual fault data quite well.>

Requirement to describing software development processes in formal manners has been increased, and demand for altering and tailoring the process descriptions has been emerged.In this paper, we propose a functional language PDL (Process Description Language), designed to describe various development processes under a certain environment.To create and modify the PDL scripts easily and correctly, we propose a method of stepwise refinement from abstract scripts into concrete scripts.By this method, the abstract definitions of software process flow and product flow initially given as function definitions in PDL, are transformed into the concrete definitions of the tool activations, message displays, and so on.We also discuss an architecture design of a software development environment (Adaptable Software Development Environment), which can be adapted in many ways for designer's requirements.

Scheduling of meetings is one of the basic functions demanded in office automation, since office workers spend much time on meetings. This paper discusses a schedufkng problem of meetings and presents a meeting scheduler for office automation which provides an automatic mechanism for updating a schedule of meetings.

In this paper, we present a new approach for the one-dimensional gate assignment problem. The original minimization problem is transformed into a restricted problem, and then a new heuristic algorithm is applied to it. The solution obtained by the algorithm is interpreted as a solution for the original problem. The whole process of the approach has been implemented and tested with various examples. Experimental results show that our approach can approximately produce optimum solutions.

This paper attempts to design a user-friendly interface which enhances usability of relational database systems. Our approach to usability is to design a semantic data model suitable for a user interface and provide an easy-to-use query language DOMCALC (domain calculus language) which is based on the semantic data model. A query in DOMCALC can be described in terms of intuitive notions, namely domains, instead of relations and attributes. That is, DOMCALC requires for users no knowledge of a conceptual database such as relation names and attribute names. Therefore, the usability based on the semantic data model removes the requirement of knowledge of a conceptual database from users and protects user views from changes in the conceptual database. We also describe an outline of a database system PRIM (Prototype of Laboratory information Management System) which has been developed with the above considerations. This is a step toward the enhancement of usability in relational database systems.

The process of visiting a mini mal number of nodes to retrieve data satisfying the range condition from a binary search tree is called "selective traversal". Driscall and Lien gave an algorithm SELECT for selective traversal which used a MARKER field of 3 bits for each node in the tree. In this paper we present a new algorithm, called INPROC, which uses a MARKER field of 2 bits and runs faster than algorithm SELECT.