Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.09.041 Byline: Zhenyu Zhang (a), Bo Jiang (a), W.K. Chan (b), T.H. Tse (a), Xinming Wang (c) Keywords: Fault localization; Boolean expression; Predicate; Evaluation sequence Abstract: Predicate-based statistical fault-localization techniques find fault-relevant predicates in a program by contrasting the statistics of the evaluation results of individual predicates between failed runs and successful runs. While short-circuit evaluations may occur in program executions, treating predicates as atomic units ignores this fact, masking out various types of useful statistics on dynamic program behavior. In this paper, we differentiate the short-circuit evaluations of individual predicates on individual program statements, producing one set of evaluation sequences per predicate. We then investigate experimentally the effectiveness of using these sequences to locate faults by comparing existing predicate-based techniques with and without such differentiation. We use both the Siemens program suite and four real-life UNIX utility programs as our subjects. The experimental results show that the proposed use of short-circuit evaluations can, on average, improve predicate-based statistical fault-localization techniques while incurring relatively small performance overhead. Author Affiliation: (a) Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong (b) Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Hong Kong (c) Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Kowloon, Hong Kong Article History: Received 2 March 2009; Revised 12 August 2009; Accepted 22 September 2009 Article Note: (footnote) [star] A preliminary version of this paper () has been presented at the 32nd Annual International Computer Software and Applications Conference (COMPSAC 2008).

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.06.056 Byline: Hsien-Chu Wu (a), Chih-Chiang Lee (b), Chwei-Shyong Tsai (c), Yen-Ping Chu (d), Hung-Ruei Chen (c) Keywords: Difference expansion; Digital watermarking; Edge prediction; Reversible data hiding; Steganography Abstract: To enhance the embedding capacity of a reversible data hiding system, in this paper, a novel multiple-base lossless scheme based on JPEG-LS pixel value prediction and reversible difference expansion will be presented. The proposed scheme employs a pixel value prediction mechanism to decrease the distortion caused by the hiding of the secret data. In general, the prediction error value tends to be much smaller in smooth areas than in edge areas, and more secret data embedded in smooth areas still meets better stego-image quality. The multiple-base notational system, on the other hand, is applied to increase the payload of the image. With the system, the payload of each pixel, determined by the complexity of its neighboring pixels, can be very different. In addition, the cover image processed by the proposed scheme can be fully recovered without any distortion. Experimental results, as shown in this paper, have demonstrated that the proposed method is capable of hiding more secret data while keeping the stego-image quality degradation imperceptible. Author Affiliation: (a) Department of Computer Science and Information Engineering, National Taichung Institute of Technology, 129, Section 3, San Min Road, Taichung City, Taiwan, ROC (b) Department of Computer Science and Engineering, National Chung Hsing University, 250, Kuo Kuang Road, Taichung City, Taiwan, ROC (c) Department of Management Information Systems, National Chung Hsing University, 250, Kuo Kuang Road, 402 Taichung, Taiwan, ROC (d) Department of Computer Science and Information Engineering, Tunghai University, 181, Section 3, Taichung Port Road, Situn District, Taichung City, Taiwan, ROC Article History: Received 8 August 2007; Revised 24 April 2009; Accepted 23 June 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.06.018 Byline: W. Eric Wong (a), T.H. Tse (b), Robert L. Glass (c), Victor R. Basili (d), T.Y. Chen (e) Keywords: Top scholars; Top institutions; Systems and software engineering; Research publications Abstract: This paper summarizes a survey of publications in the field of systems and software engineering from 2002 to 2006. The survey is an ongoing, annual event that identifies the top 15 scholars and institutions over a 5-year period. The rankings are calculated based on the number of papers published in TSE, TOSEM, JSS, SPE, EMSE, IST, and Software. The top-ranked institution is Korea Advanced Institute of Science and Technology, Korea, and the top-ranked scholar is Magne JA[cedilla]rgensen of Simula Research Laboratory, Norway. Author Affiliation: (a) Department of Computer Science, The University of Texas at Dallas, Richardson, TX 75083, USA (b) Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong (c) Computing Trends, 18 View Street, Paddington, QLD 4064, Australia (d) Department of Computer Science, University of Maryland, College Park, MD 20742, USA (e) Faculty of Information and Communication Technologies, Swinburne University of Technology, John Street, Melbourne 3122, Australia Article History: Received 5 June 2009; Accepted 5 June 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2008.11.845 Byline: S. Sioutas (a), E. Sakkopoulos (b), Ch. Makris (b), B. Vassiliadis (c), A. Tsakalidis (b), P. Triantafillou (b) Keywords: Web Services Discovery; Peer to Peer overlay networks; Databases Abstract: Service Oriented Computing and its most famous implementation technology Web Services (WS) are becoming an important enabler of networked business models. Discovery mechanisms are a critical factor to the overall utility of Web Services. So far, discovery mechanisms based on the UDDI standard rely on many centralized and area-specific directories, which poses information stress problems such as performance bottlenecks and fault tolerance. In this context, decentralized approaches based on Peer to Peer overlay networks have been proposed by many researchers as a solution. In this paper, we propose a new structured P2P overlay network infrastructure designed for Web Services Discovery. We present theoretical analysis backed up by experimental results, showing that the proposed solution outperforms popular decentralized infrastructures for web discovery, Chord (and some of its successors), BATON (and it's successor) and Skip-Graphs. Author Affiliation: (a) Department of Informatics, Ionian University, 7 Tsirigoti Square, 49100 Corfu, Greece (b) Computer Engineering and Informatics Department, University of Patras, Greece (c) Computer Science, Hellenic Open University, Patras, Greece Article History: Received 18 June 2008; Revised 12 November 2008; Accepted 13 November 2008 Article Note: (footnote) [star] Preliminary version of this paper was presented in Proceedings of IEEE International Conference on Information Technology: Coding and Computing, Next - Generation Web and Grid Systems (IEEE/ITCC 2005), pp. 193-198.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2008.07.038 Byline: Ya-Shu Chen (a), Li-Pin Chang (b), Tei-Wei Kuo (c), Aloysius K. Mok (d) Keywords: Scheduling anomaly; Real-time task scheduling; Process synchronization; Scheduler stability Abstract: This research responds to practical requirements in the porting of embedded software over platforms and the well-known multiprocessor anomaly. In particular, we consider the task scheduling problem when the system configuration changes. With mutual-exclusive resource accessing, we show that new violations of the timing constraints of tasks might occur even when a more powerful processor or device is adopted. The concept of scheduler stability and rules are then proposed to prevent scheduling anomaly from occurring in task executions that might be involved with task synchronization or I/O access. Finally, we explore policies for bounding the duration of scheduling anomalies. Author Affiliation: (a) Department of Electronic Engineering, National Taiwan University of Science and Technology, Taipei 106, Taiwan (b) Department of Computer Science, National Chiao-Tung University, Hsin-Chu 300, Taiwan (c) Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan (d) Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712, USA Article History: Received 8 June 2006; Revised 2 July 2008; Accepted 21 July 2008 Article Note: (footnote) [star] This paper is an extended version of the paper that appeared in .

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.12.564 Byline: Nen-Chung Wang (a), Shian-Zhang Fang (b) Keywords: Group communication; Group key; Key management; Mobile ad hoc networks; Network security Abstract: A mobile ad hoc network (MANET) is a kind of wireless communication infrastructure that does not have base stations or routers. Each node acts as a router and is responsible for dynamically discovering other nodes it can directly communicate with. However, when a message without encryption is sent out through a general tunnel, it may be maliciously attacked. In this paper, we propose a hierarchical key management scheme (HKMS) for secure group communications in MANETs. For the sake of security, we encrypt a packet twice. Due to the frequent changes of the topology of a MANET, we also discuss group maintenance in this paper. Finally, we conducted the security and performance analysis to compare the proposed scheme with Tseng et al.'s [Tseng, Y.-M., Yang, C.-C., Liao, D.-R., 2007. A secure group communication protocol for ad hoc wireless networks. In: Advances in Wireless Ad Hoc and Sensor Networks and Mobile Computing. Book Series Signal and Communication Technology. Springer] and Steiner et al.'s [Steiner, M., Tsudik, G., Waidner, M., 1998. CLIQUES: a new approach to group key agreement. In: Proceedings of the 18th IEEE International Conference on Distributed Computing System. Amsterdam, Netherlands, pp. 380-387] schemes. Author Affiliation: (a) Department of Computer Science and Information Engineering, National United University, Miao-Li 360, Taiwan, ROC (b) Department of Computer Science and Information Engineering, Chaoyang University of Technology, Taichung 413, Taiwan, ROC Article History: Received 11 March 2006; Revised 24 November 2006; Accepted 22 December 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.08.016 Byline: Yuen Tak Yu (a), Man Fai Lau (b), Tsong Yueh Chen (b) Keywords: Black-box testing; Boolean specification; Fault-based testing; Specification-based testing; Test case generation Abstract: A recent theoretical study has proved that the MUMCUT testing strategy (1) guarantees to detect seven types of fault in Boolean specifications in irredundant disjunctive normal form, and (2) requires only a subset of the test sets that satisfy the previously proposed MAX-A and MAX-B strategies, which can detect the same types of fault. This paper complements previous work by investigating various methods for the automatic generation of test cases to satisfy the MUMCUT strategy. We evaluate these methods by using several sets of Boolean expressions, including those derived from real airborne software systems. Our results indicate that the greedy CUN and UCN methods are clearly better than others in consistently producing significantly smaller test sets, whose sizes exhibit linear correlation with the length of the Boolean expressions in irredundant disjunctive normal form. This study provides empirical evidences that the MUMCUT strategy is indeed cost-effective for detecting the faults considered in this paper. Author Affiliation: (a) Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong (b) Faculty of Information and Communication Technologies, Swinburne University of Technology, Hawthorn 3122, Australia Article History: Received 27 February 2003; Revised 17 August 2005; Accepted 19 August 2005 Article Note: (footnote) [star] The work is supported in part by a grant from City University of Hong Kong (project no. 7001233), a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (RGC ref. no. CityU 1083/00E), and Australian Research Council Discovery Grants (project IDs: DP0345147 and DP0558597).

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.08.018 Byline: T.H. Tse (a), T.Y. Chen (b), Robert L. Glass (c) Keywords: Top scholars; Top institutions; Research publications; Systems and software engineering Abstract: This paper presents the findings of a five-year study of the top scholars and institutions in the Systems and Software Engineering field, as measured by the quantity of papers published in the journals of the field in 2000-2004. The top scholar is Hai Zhuge of the Chinese Academy of Sciences, and the top institution is Korea Advanced Institute of Science and Technology. This paper is part of an ongoing study, conducted annually, that identifies the top 15 scholars and institutions in the most recent five-year period. Author Affiliation: (a) Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong (b) Faculty of Information and Communication Technologies, Swinburne University of Technology, John Street, Melbourne 3122, Australia (c) Computing Trends, 18 View St., Brisbane, QLD 4064, Australia Article History: Received 29 July 2005; Revised 2 August 2005; Accepted 13 August 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.07.015 Byline: Kam-Yiu Lam (a), Azgur Ulusoy (b) Keywords: Location-dependent continuous queries; Location update; Moving object database; Location management Abstract: An important feature that is expected to be owned by today's mobile computing systems is the ability of processing location-dependent continuous queries on moving objects. The result of a location-dependent query depends on the current location of the mobile client which has generated the query as well as the locations of the moving objects on which the query has been issued. When a location-dependent query is specified to be continuous, the result of the query can continuously change. In order to provide accurate and timely query results to a client, the location of the client as well as the locations of moving objects in the system has to be closely monitored. Most of the location generation methods proposed in the literature aim to optimize utilization of the limited wireless bandwidth. The issues of correctness and timeliness of query results reported to clients have been largely ignored. In this paper, we propose an adaptive monitoring method (AMM) and a deadline-driven method (DDM) for managing the locations of moving objects. The aim of our methods is to generate location updates with the consideration of maintaining the correctness of query evaluation results without increasing location update workload. Extensive simulation experiments have been conducted to investigate the performance of the proposed methods as compared to a well-known location update generation method, the plain dead-reckoning (pdr). Author Affiliation: (a) Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong (b) Department of Computer Engineering, Bilkent University, Bilkent, Ankara 06800, Turkey Article History: Received 27 January 2004; Revised 1 July 2005; Accepted 15 July 2005 Article Note: (footnote) [star] This work described in this paper was supported by a research grant from the Research Grant Council of Hong Kong Special Administration Region, China [Project No. CityU 1076/02E].

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2004.12.019 Byline: Matthias M. Muller Keywords: Pair programming; Peer reviews; Empirical software engineering; Controlled experiment Abstract: This paper reports on two controlled experiments comparing pair programming with single developers who are assisted by an additional anonymous peer code review phase. The experiments were conducted in the summer semester 2002 and 2003 at the University of Karlsruhe with 38 computer science students. Instead of comparing pair programming to solo programming this study aims at finding a technique by which a single developer produces similar program quality as programmer pairs do but with moderate cost. The study has one major finding concerning the cost of the two development methods. Single developers are as costly as programmer pairs, if both programmer pairs and single developers with an additional review phase are forced to produce programs of similar level of correctness. In conclusion, programmer pairs and single developers become interchangeable in terms of development cost. As this paper reports on the results of small development tasks the comparison could not take into account long time benefits of either technique. Author Affiliation: Department of Computer Science, Fakultat fur Informatik, Universitat Karlsruhe, Am Fasanengarten 5, 76131 Karlsruhe, Germany Article History: Received 3 June 2004; Revised 23 December 2004; Accepted 24 December 2004

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2004.03.034 Byline: Sebastian Danicic (a), Mohammed Daoudi (a), Chris Fox (b), Mark Harman (c), Robert M. Hierons (c), John R. Howroyd (a), Lahcen Ourabya (a), Martin Ward (d) Abstract: Program conditioning consists of identifying and removing a set of statements which cannot be executed when a condition of interest holds at some point in a program. It has been applied to problems in maintenance, testing, re-use and re-engineering. All current approaches to program conditioning rely upon both symbolic execution and reasoning about symbolic predicates. The reasoning can be performed by a 'heavy duty' theorem prover but this may impose unrealistic performance constraints. This paper reports on a lightweight approach to theorem proving using the FermaT Simplify decision procedure. This is used as a component to ConSUS, a program conditioning system for the Wide Spectrum Language WSL. The paper describes the symbolic execution algorithm used by ConSUS, which prunes as it conditions. The paper also provides empirical evidence that conditioning produces a significant reduction in program size and, although exponential in the worst case, the conditioning system has low degree polynomial behaviour in many cases, thereby making it scalable to unit level applications of program conditioning. Author Affiliation: (a) Department of Mathematics and Computer Science, Goldsmiths College, University of London, New Cross, London SE14 6NW, United Kingdom (b) Department of Computer Science, University of Essex, Wivenhoe Park, Colchester, CO4 3SQ, United Kingdom (c) Department of Information Systems and Computing, Brunel University, Uxbridge, Middlesex, UB8 3PH, United Kingdom (d) Software Technology Research Laboratory, De Montfort University, The Gateway, Leicester LE1 9BH, United Kingdom

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2010.04.069 Byline: Shuigeng Zhou (a)(b), Ming Xu (a)(b), Jihong Guan (c) Keywords: Lecture notes; Metasearch engines; Peer-to-peer networks; Content sharing; Query routing Abstract: In this paper, we present a system LESSON for lecture notes searching and sharing, which is dedicated to both instructors and students for effectively supporting their Web-based teaching and learning activities. The LESSON system employs a metasearch engine for lecture notes searching from Web and a peer-to-peer (P2P) overlay network for lecture notes sharing among the users. A metasearch engine provides an unified access to multiple existing component search engines and has better performance than general-purpose search engines. With the help of a P2P overlay network, all computers used by instructors and students can be connected into a virtual society over the Internet and communicate directly with each other for lecture notes sharing, without any centralized server and manipulation. In order to merge results from multiple component search engines into a single ranked list, we design the RSF strategy that takes rank, similarity and features of lecture notes into account. To implement query routing decision for effectively supporting lecture notes sharing, we propose a novel query routing mechanism. Experimental results indicate that the LESSON system has better performance in lecture notes searching from Web than some popular general-purpose search engines and some existing metasearch schemes; while processing queries within the system, it outperforms some typical routing methods. Concretely, it can achieve relatively high query hit rate with low bandwidth consumption in different types of network topologies. Author Affiliation: (a) School of Computer Science, Fudan University, Shanghai 200433, China (b) Shanghai Key Lab of Intelligent Information Processing, Shanghai 200433, China (c) Department of Computer Science & Technology, Tongji University, Shanghai 201804, China Article History: Received 17 June 2009; Revised 28 April 2010; Accepted 30 April 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2010.04.068 Byline: Gyu Sang Choi (a), Chita R. Das (b) Keywords: Multi-Core; SuperScalar; Software architecture model; Multi-thread Abstract: Design of high-performance servers has become a research thrust to meet the increasing demand of network-based applications. One approach to design such architectures is to exploit the enormous computing power of Multi-Core Processors (MCPs) that are envisioned to become the state-of-the-art in processor architecture. In this paper, we propose a new software architecture model, called SuperScalar, suitable for MCP machines. The proposed SuperScalar model consists of multiple pipelined thread pools, where each pipelined thread pool consists of multiple threads, and each thread takes a different role. The main advantages of the proposed model are global information sharing by the threads and minimal memory requirement due to fewer threads. We have conducted in-depth performance analyses of the proposed scheme along with three prior software architecture schemes (Multi-Process (MP), Multi-Thread (MT) and Event-Driven (ED)) via an analytical model. The performance results indicate that the proposed SuperScalar model shows the best performance across all system and workload parameters compared to the MP, MT and ED models. Although the MT model shows competitive performance with less number of processing cores and smaller data cache size, the advantage of the SuperScalar model becomes obvious as the number of processing cores increases. Author Affiliation: (a) Department of Information and Communication Engineering, Yeungnam University, Sojae Building #202-1, 214-1 Dae-dong, Gyeongsan-si, Gyeongsangbuk-do 712-749, Republic of Korea (b) Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA 16802, United States Article History: Received 8 June 2009; Revised 29 April 2010; Accepted 29 April 2010 Article Note: (footnote) [star] This research was supported by the Yeungnam University research grants in 2010. Moreover, this research was supported in part by NSF grants EIA-0202007, CCR-0208734, CCF-0429631 and CNS-0509251.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2010.03.081 Byline: Cheng-Hsing Yang (a), Chi-Yao Weng (b), Shiuh-Jeng Wang (c), Hung-Min Sun (b) Keywords: Pixel-value differencing; LSB; Steganography; Detection analysis Abstract: Image steganographic schemes based on the least-significant-bit (LSB) replacement method own the character of high capacity and good quality, but they are detected easily by some programs. Pixel-value differencing (PVD) approaches are one kind of methods to pass some program detections, but PVD approaches usually provide lower capacities and larger distortion. Accordingly, the combined method of PVD and LSB replacement was proposed to raise the capacity and the quality of PVD approaches over the past literatures. In this paper, not only we contribute a new exploration in spatial domain to benefiting both the capacity and the fidelity on the basis of varied LSB+PVD approaches, but also the risk of the RS-steganalysis detection program is evaded. Furthermore, proof works are conducted to proclaim the correctness of the general LSB+PVD method. Following up, the varied LSB+PVD approach is therefore applied to our scheme. Author Affiliation: (a) Department of Computer Science, National Pingtung University of Education, Pingtung 900, Taiwan (b) Department of Computer Science, National Tsing-Hua University, Hsinchu 300, Taiwan (c) Department of Information Management, Central Police University, Taoyuan 333, Taiwan Article History: Received 23 June 2008; Revised 4 February 2010; Accepted 27 March 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.10.042 Byline: Jung-Sing Jwo (a), Yu Chin Cheng (b) Keywords: Software requirements models; Models as mediators; Ontology of models; Learning from models Abstract: A new synthesis of software requirements models called pseudo software is proposed with the aim to cut requirements-related errors. Pseudo software achieves this aim by serving as a mediating instrument to empower stakeholders to participate in requirements elicitation and validation through model construction and manipulation, and to provide guidance to the development team to correctly interpret the requirements in the downstream development activities. Pseudo software obtains its traits as a mediating instrument through the choice of requirements information bits and the use of multimodal representations with tool support to integrate the requirements. Using historical data of fifty projects in the enterprise computing domain, pseudo software is shown to effectively cut the requirements-related errors committed by both the customer and the development team. Author Affiliation: (a) Department of Computer Science and Information Engineering, Tunghai University, 181, Section 3, Taichung Port Road, Situn District, Taichung 407, Taiwan (b) Department of Computer Science and Information Engineering, National Taipei University of Technology, 1, Section 3, Chung-Hsiao East Road, Taipei 106, Taiwan Article History: Received 7 August 2008; Revised 27 October 2009; Accepted 29 October 2009 Article Note: (footnote) [star] A preliminary version of this paper was presented in the 14th Asia-Pacific Software Engineering Conference (APSEC 2007), Nagoya, Japan.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.09.037 Byline: W. Eric Wong (a), Vidroha Debroy (a), Byoungju Choi (b) Keywords: Fault localization; Program debugging; Code coverage; Heuristics; Suspiciousness of code; Successful tests; Failed tests Abstract: Locating faults in a program can be very time-consuming and arduous, and therefore, there is an increased demand for automated techniques that can assist in the fault localization process. In this paper a code coverage-based method with a family of heuristics is proposed in order to prioritize suspicious code according to its likelihood of containing program bugs. Highly suspicious code (i.e., code that is more likely to contain a bug) should be examined before code that is relatively less suspicious; and in this manner programmers can identify and repair faulty code more efficiently and effectively. We also address two important issues: first, how can each additional failed test case aid in locating program faults; and second, how can each additional successful test case help in locating program faults. We propose that with respect to a piece of code, the contribution of the first failed test case that executes it in computing its likelihood of containing a bug is larger than or equal to that of the second failed test case that executes it, which in turn is larger than or equal to that of the third failed test case that executes it, and so on. This principle is also applied to the contribution provided by successful test cases that execute the piece of code. A tool, IDebug, was implemented to automate the computation of the suspiciousness of the code and the subsequent prioritization of suspicious code for locating program faults. To validate our method case studies were performed on six sets of programs: Siemens suite, Unix suite, space, grep, gzip, and make. Data collected from the studies are supportive of the above claim and also suggest Heuristics III(a), (b) and (c) of our method can effectively reduce the effort spent on fault localization. Author Affiliation: (a) Department of Computer Science, University of Texas at Dallas, TX 75083, USA (b) Department of Computer Science and Engineering, Ewha womans University, Republic of Korea Article History: Received 3 March 2009; Revised 27 July 2009; Accepted 22 September 2009 Article Note: (footnote) [star] This research was supported by the MKE (Ministry of Knowledge Economy), Korea, under the ITRC (Information Technology Research Center) support program supervised by the NIPA (National IT Industry Promotion Agency) (NIPA-2009-(C1090-0902-0032)).

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.06.008 Byline: Jihyun Lee (a), Jeong-Hoon Park (a), Myung-Jae Park (a), Chin-Wan Chung (a), Jun-Ki Min (b) Keywords: Distributed query processing; Semantic mapping; Query optimization; Distributed ontologies; Semantic Web Abstract: In this paper, we propose an intelligent distributed query processing method considering the characteristics of a distributed ontology environment. We suggest more general models of the distributed ontology query and the semantic mapping among distributed ontologies compared with the previous works. Our approach rewrites a distributed ontology query into multiple distributed ontology queries using the semantic mapping, and we can obtain the integrated answer through the execution of these queries. Furthermore, we propose a distributed ontology query processing algorithm with several query optimization techniques: pruning rules to remove unnecessary queries, a cost model considering site load balancing and caching, and a heuristic strategy for scheduling plans to be executed at a local site. Finally, experimental results show that our optimization techniques are effective to reduce the response time. Author Affiliation: (a) Division of Computer Science, Department of Electronic Engineering and Computer Science, Korea Advanced Institute of Science and Technology (KAIST), Daejon 305-701, Republic of Korea (b) School of Internet-Media Engineering, Korea University of Technology and Education, Byeongcheon-Myeon, Cheonan, Chungnam 330-708, Republic of Korea Article History: Received 30 October 2008; Revised 30 March 2009; Accepted 7 June 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.07.050 Byline: Min-Shiang Hwang (a), Song-Kong Chong (b), Te-Yu Chen (c) Keywords: ID-based scheme; Client puzzles; Password authentication; Resources exhaustion attack; Smart card Abstract: In this paper, we provide a defense mechanism to Kim-Lee-Yoo's ID-based password authentication scheme, which is vulnerable to impersonation attacks and resource exhaustion attacks. Mutual authentication and communication privacy are regarded as essential requirements in today's client/server-based architecture; therefore, a lightweight but secure mutual authentication method is introduced in the proposed scheme. Once the mutual authentication is successful, the session key will be established without any further computation. The proposed defense mechanism not only accomplishes the mutual authentication and the session key establishment, but also inherits the security advantages of Kim-Lee-Yoo's scheme, e.g. it is secure against password guessing attacks and message replay attacks. Author Affiliation: (a) Department of Management Information Systems, National Chung Hsing University, 250 Kuo Kuang Road, Taichung 402, Taiwan, ROC (b) Department of Computer Science and Information Engineering, National Cheng-Kung University, 1 University Road, Tainan 701, Taiwan, ROC (c) Department of Computer Science and Engineering, National Chung Hsing University, 250 Kuo Kuang Road, Taichung 402, Taiwan, ROC Article History: Received 21 July 2007; Revised 5 July 2009; Accepted 31 July 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.04.043 Byline: Sang-Uk Jeon (a), Jang-Eui Hong (b), In-Gwon Song (a), Doo-Hwan Bae (a) Keywords: MPSoC; Embedded software; Platform independent model; Platform specific model; UML; Task allocation Abstract: In this paper, we describe a technique to design UML-based software models for MPSoC architecture, which focuses on the development of the platform specific model of embedded software. To develop the platform specific model, we define a process for the design of UML-based software model and suggest an algorithm with precise actions to map the model to MPSoC architecture. In order to support our design process, we implemented our approach in an integrated tool. Using the tool, we applied our design technique to a target system. We believe that our technique provides several benefits such as improving parallelism of tasks and fast-and-valid mapping of software models to hardware architecture. Author Affiliation: (a) Division of Computer Science, College of Information Science and Technology, KAIST, Republic of Korea (b) School of Electrical and Computer Engineering, Chungbuk National University, Cheongju, Republic of Korea Article History: Received 15 September 2007; Revised 20 April 2009; Accepted 22 April 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.04.001 Byline: Hung-Min Sun (a), Mu-En Wu (b), M. Jason Hinek (c), Cheng-Ta Yang (d), Vincent S. Tseng (d) Keywords: RSA; CRT; Encryption; Digital signatures; Lattice basis reduction; Cryptanalysis Abstract: In 1982, Quisquater and Couvreur proposed an RSA variant, called RSA-CRT, based on the Chinese Remainder Theorem to speed up RSA decryption. In 1990, Wiener suggested another RSA variant, called Rebalanced-RSA, which further speeds up RSA decryption by shifting decryption costs to encryption costs. However, this approach essentially maximizes the encryption time since the public exponent e is generally about the same order of magnitude as the RSA modulus. In this paper, we introduce two variants of Rebalanced-RSA in which the public exponent e is much smaller than the modulus, thus reducing the encryption costs, while still maintaining low decryption costs. For a 1024-bit RSA modulus, our first variant (Scheme A) offers encryption times that are at least 2.6 times faster than that in the original Rebalanced-RSA, while the second variant (Scheme B) offers encryption times at least 3 times faster. In both variants, the decrease in encryption costs is obtained at the expense of slightly increased decryption costs and increased key generation costs. Thus, the variants proposed here are best suited for applications which require low costs in encryption and decryption. Author Affiliation: (a) Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC (b) Institute of Information Science, Academia Sinica, Taipei, Taiwan, ROC (c) School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada (d) Department of Computer Science and Information Engineering, National Cheng Kung University, Taiwan, ROC Article History: Received 17 October 2008; Revised 1 March 2009; Accepted 4 April 2009 Article Note: (footnote) [star] This is an improved version of .

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.03.008 Byline: Ki Yong Lee (a), Hyojun Kim (b), Kyoung-Gu Woo (b), Yon Dohn Chung (c), Myoung Ho Kim (a) Keywords: Flash-based DBMS; MLC NAND flash memory; Transaction processing Abstract: Recently, Multi-Level Cell (MLC) NAND flash memory is becoming widely used as storage media for mobile devices such as mobile phones, MP3 players, PDAs and digital cameras. MLC NAND flash memory, however, has some restrictions that hard disk or Single-Level Cell (SLC) NAND flash memory do not have. Since most traditional database techniques assume hard disk, they may not provide the best attainable performance on MLC NAND flash memory. In this paper, we design and implement an MLC NAND flash-based DBMS for mobile devices, called AceDB Flashlight, which fully exploits the unique characteristics of MLC NAND flash memory. Our performance evaluations on an MLC NAND flash-based device show that the proposed DBMS significantly outperforms the existing ones. Author Affiliation: (a) Division of Computer Science, KAIST, 373-1 Guseong-Dong, Yuseong-Gu, Daejeon 305-701, Republic of Korea (b) Software Laboratories, Samsung Electronics, 416, Maetan-3Dong, Yeongtong-Gu, Suwon, Gyeonggi-Do 443-742, Republic of Korea (c) Department of Computer Science and Engineering, Korea University, Anam-Dong, Seongbuk-Gu, Seoul 136-701, Republic of Korea Article History: Received 27 August 2008; Revised 5 January 2009; Accepted 5 March 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.02.020 Byline: Sanghyun Yoo (a), Jin Hyun Son (b), Myoung Ho Kim (a) Keywords: Mobile ad hoc networks; Publish/subscribe system Abstract: Since nodes that compose mobile ad hoc networks (MANETs) does not have any prior knowledge about other nodes in many cases, the publish/subscribe communication paradigm that has the decoupling and asynchrony properties can be useful to share information between nodes. Existing publish/subscribe services for MANETs can be categorized into document flooding (DF), destination-based routing (DBR), and content-based routing (CBR). Although those approaches may work well when the size of network is small, all of them suffer from the performance decline as the size of the network increases. In this paper, we compare those approaches, and then propose a scalable publish/subscribe communication scheme in large MANETs by combining DF and CBR hierarchically. Our approach is to cluster all nodes in networks and to exploit CBR and DF for the intra- and inter-cluster communication, respectively. By using this approach, we can effectively utilize benefits of both approaches. Then, we present performance evaluation results which validate our idea with respect to system performance and scalability. Author Affiliation: (a) Division of Computer Science, KAIST, 335 Gwahangno, Yuseong-gu, Daejeon, Republic of Korea (b) Department of Computer Science and Engineering, Hanyang University, 1271 Sa3-Dong, Sangrok-gu, Ansan, Kyunggi-do 426-791, Republic of Korea Article History: Received 8 October 2008; Revised 29 December 2008; Accepted 3 February 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.01.012 Byline: Joo Hyuk Jeon (a), Ki Yong Lee (a), Jae Soo Yoo (b), Myoung Ho Kim (a) Keywords: In-network join; Event-detection; Sensor network Abstract: In sensor networks, the event-detection process can be considered as a join of two relations, i.e., a sensor table and a condition table, where a condition table is a set of tuples each of which contains condition information about a certain event. When join operations are used for event-detection, it is desirable, if possible, to perform 'in-network' joins in order to reduce the communication cost. In this paper, we propose an in-network join algorithm, called HIPaG. In HIPaG, a condition table is partitioned into several fragments. Those fragments are stored either in paths from the base station to sensor nodes, or in groups of nodes each of which are within the broadcast range among each other. By distributing a condition table in this way, a distributed join of a sensor table and a condition table can be effectively performed in the network. The experimental results show that our proposed HIPaG works much better than the existing method. Author Affiliation: (a) Division of Computer Science, KAIST, 373-1 Guseong-dong, Yuseong-gu, Daejeon, Republic of Korea (b) School of Electrical and Computer Engineering, Chungbuk National University, 361-763 Gaesin-dong, Heungduk-gu, Cheongju, Chungbuk, Republic of Korea Article History: Received 20 February 2008; Revised 8 December 2008; Accepted 9 January 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2008.11.846 Byline: Diane Kelly Keywords: Scientific software; Characteristics of scientific software development; Long-term software evolution; Empirical study; Model of change Abstract: One of the characteristics of scientific application software is its long lifetime of active maintenance. There has been little software engineering research into the development characteristics of scientific software and into the factors that support its successful long evolution. The research described in this paper introduces a novel model to examine the nature of change that influenced an example of industrial scientific software over its lifetime. The research uses the model to provide an objective analysis of factors that contributed to long-term evolution of the software system. Conclusions suggest that the architectural design of the software and the characteristics of the software development group played a major role in the successful evolution of the software. The novel model of change and the research method developed for this study are independent of the type of software under study. Author Affiliation: Royal Military College of Canada, Department of Mathematics and Computer Science, Kingston, Ontario, Canada Article History: Received 2 June 2008; Revised 21 November 2008; Accepted 23 November 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.12.562 Byline: Chulyun Kim (a), Jong-Hwa Lim (b), Raymond T. Ng (c), Kyuseok Shim (a) Keywords: Data mining; Knowledge discovery; Sequential pattern mining Abstract: Discovering sequential patterns is an important problem for many applications. Existing algorithms find qualitative sequential patterns in the sense that only items are included in the patterns. However, for many applications, such as business and scientific applications, quantitative attributes are often recorded in the data, which are ignored by existing algorithms. Quantity information included in the mined sequential patterns can provide useful insight to the users. In this paper, we consider the problem of mining sequential patterns with quantities. We demonstrate that naive extensions to existing algorithms for sequential patterns are inefficient, as they may enumerate the search space blindly. To alleviate the situation, we propose hash filtering and quantity sampling techniques that significantly improve the performance of the naive extensions. Experimental results confirm that compared with the naive extensions, these schemes not only improve the execution time substantially but also show better scalability for sequential patterns with quantities. Author Affiliation: (a) School of Electrical Engineering and Computer Science, Seoul National University, Kwanak, P.O. Box 34, Seoul, Republic of Korea (b) Department of Computer Science, KAIST, Taejeon, Republic of Korea (c) Department of Computer Science, University of British Columbia, Vancouver, Canada Article History: Received 23 March 2006; Revised 3 December 2006; Accepted 7 December 2006 Article Note: (footnote) [star] This work was supported by the Ministry of Information and Communication, Korea, under the College Information Technology Research Center Support Program, grant number IITA-2006-C1090-0603-0031.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2007.01.006 Byline: Natalia Juristo (a), Ana M. Moreno (a), Maria-Isabel Sanchez-Segura (b) Keywords: Software usability; Software design Abstract: This paper analyses what implications usability has for software development, paying special attention to the impact of this quality attribute on design. In this context, the aim is twofold. On the one hand, we intend to empirically corroborate that software design and usability are really related. This would mean that this, like other quality attributes, would need to be dealt with no later than at design time to develop usable software at a reasonable cost. On the other hand, we present a possible quantification, calculated from a number of real applications, of the effect of incorporating certain usability features at design time. Author Affiliation: (a) School of Computing, Universidad Politecnica de Madrid, Campus de Montegancedo s/n, 28660 Boadilla del Monte, Madrid, Spain (b) Computer Science Department, Universidad Carlos III de Madrid, Avda. De la Universidad, 30, 28911 Leganes, Madrid, Spain Article History: Received 20 July 2006; Revised 3 January 2007; Accepted 5 January 2007 Article Note: (footnote) [star] This research was funded by the Spanish Ministry of Education - Project TIN 230005-00176.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.03.038 Byline: Helio R. Costa (a)(b), Marcio de O. Barros (b)(c), Guilherme H. Travassos (b) Keywords: Software project management; Software risk management; Software Engineering Economics; Empirical studies Abstract: As in any other business, software development organizations try to maximize their profits and minimize their risks. The risks represent uncertain events and conditions that may prevent enterprises from attaining their goals, turning risk management into a major concern, not only for project managers but also for executive officers involved with strategic objectives. In this sense, economical concepts can greatly support Software Engineers in the effort to better quantify the uncertainties of either a single project or even a project portfolio. In this paper, we present a technique for evaluating risk levels in software projects through analogies with economic concepts. This technique allows a manager to estimate the probability distribution of earnings and losses incurred by an organization in relation to its software project portfolio. This approach has been calibrated by data collected in an empirical study, which has been planned and accomplished to provide information about the relative importance of risk factors in software projects. A usage example of such an approach is presented. Finally, we introduce a case tool specially built to support the application of the proposed techniques. Author Affiliation: (a) CCA-RJ, Brazilian Air Force, Ponta do Galeao s/n[degrees], Ilha do Governador, CEP: 21941-510 Rio de Janeiro, Brazil (b) COPPE/UFRJ, System Engineering and Computer Science Department, Caixa Postal: 68511, CEP: 21945-970 Rio de Janeiro, Brazil (c) UNIRIOTEC, Applied Computer Science Department, Av. Pasteur 458, Urca, CEP: 22290-240 Rio de Janeiro, Brazil Article History: Received 1 October 2005; Revised 9 March 2006; Accepted 26 March 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.03.039 Byline: Sanghyun Yoo (a), Jin Hyun Son (b), Myoung Ho Kim (a) Keywords: Publish/subscribe system; XPath; Homomorphism; Subscription routing algorithm Abstract: XML-based publish/subscribe systems have gained popularity as one of the newly emerging communication paradigms. As the number of clients has increased, the concept of the scalability has become the most important factor in the distributed information processing. In this paper, we propose an efficient subscription routing algorithm as a part of efforts to achieve scalability, with subscriptions especially expressed in XPath patterns. We first discuss that the homomorphism relationship among XPath patterns can be utilized for routing XPath patterns. Then, we develop a lattice data structure called the partially ordered set of XPath patterns which is abbreviated as POX and its corresponding algorithm for efficiently maintaining homomorphism relationships. Finally, we present performance evaluation results which validate our algorithm with respect to system performance and scalability. Author Affiliation: (a) Division of Computer Science, Korea Advanced Institute of Science and Technology, 373-1 Guseong-dong, Yuseong-gu, Daejeon, Republic of Korea (b) Department of Computer Science and Engineering, Hanyang University, 1271 Sa-1-dong, Sangrok-gu, Ansan, Kyonggi-do, Republic of Korea Article History: Received 31 July 2005; Revised 8 March 2006; Accepted 26 March 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.11.576 Byline: Chin-Chen Chang (a)(b), Tzu-Chuen Lu (b) Keywords: Reversible information hiding; SMVQ; Lossy compression Abstract: Information hiding has become an interesting topic that receives more and more attention. Recently, many hiding techniques were proposed to directly conceal secret information on an image. However, for convenience and efficiency, images are usually stored and compressed by lossy or lossless compression mechanisms in indices format. The hidden information might be erased or cancelled when the stego image is lossy compressed. Hence, this paper proposes an information hiding scheme based on side-match vector quantization (SMVQ), which conceals the secret information on the indices of the SMVQ compressed images. The proposed scheme not only can embed information in the indices of the compressed image with low image distortion, but also can recover the original indices to reconstruct the SMVQ compressed image. As the experimental results indicated, the proposed scheme indeed outperforms other schemes in terms of image quality, hiding capacity, and compression rate. Author Affiliation: (a) Department of Information Engineering and Computer Science, Feng Chia University, 100 Wenhwa Rd., Seatwen, Taichung 40724, Taiwan, ROC (b) Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi 621, Taiwan, ROC Article History: Received 13 May 2005; Revised 15 November 2005; Accepted 24 November 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.09.003 Byline: Yusuf Hasan (a), J. Morris Chang (b) Keywords: Dynamic memory allocation; Performance; Tuning; Optimization Abstract: Dynamic memory management can make up to 60% of total program execution time. Object oriented languages such as C++ can use 20 times more memory than procedural languages like C. Bad memory management causes severe waste of memory, several times that actually needed, in programs. It can also cause degradation in performance. Many widely used allocators waste memory and/or CPU time. Since computer memory is an expensive and limited resource its efficient utilization is necessary. There cannot exist a memory allocator that will deliver best performance and least memory consumption for all programs and therefore easily tunable allocators are required. General purpose allocators that come with operating systems give less than optimal performance or memory consumption. An allocator with a few tunable parameters can be tailored to a program's needs for optimal performance and memory consumption. Our tunable hybrid allocator design shows 11-54% better performance and nearly equal memory consumption when compared to the well known Doug Lea allocator in seven benchmark programs. Author Affiliation: (a) Department of Computer Science, Illinois Institute of Technology, Chicago, IL 60616, USA (b) Department of Electrical Engineering, Iowa State University, 3216 Coover Hall, Ames, IA 50011, USA Article History: Received 15 August 2004; Revised 5 September 2005; Accepted 10 September 2005 Article Note: (footnote) [star] A preliminary version of this paper titled "A Hybrid Allocator" appeared in the Proceedings of 2003 IEEE International Symposium on Performance Analysis of Systems and Software, Austin, TX, 6-8 March 2003, pp. 214-221.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.04.005 Byline: Seng W. Loke Keywords: Prolog; Integration; Logic programming; Web computing; Peer-to-peer computing; Declarative programming Abstract: Web and peer-to-peer systems have emerged as popular areas in distributed computing, and their integrated usage permits the benefits of both to be exploited. While much work in these areas have utilized the imperative programming paradigm, the need for declarative programming paradigms is increasingly being recognized, not only for the often cited advantages such as a higher level of abstraction and specialized language features, but also to tackle the querying and manipulation of knowledge and reasoning with semantics that will be the mainstay of the proposed next generation of the Web and peer-to-peer computing. This paper presents an approach towards integrative use of the Web and peer-to-peer systems within a declarative programming paradigm. We contend that logic programming can be useful in peer-to-peer computing, especially for querying and representing knowledge shared over peer networks, and for scripting applications that involve sophisticated search behaviour over peer networks. As an example of peer-to-peer querying expressed in a logic programming language, we propose a simple extension of Prolog, which we call LogicPeer, to enable goal evaluation over peers in a peer network. Using LogicPeer, we outline how a peer-to-peer version of a Yahoo-like system can be built and queried, and several other applications that involve decentralized knowledge sharing. We then show how LogicPeer can be used with LogicWeb, a Prolog extension to access Web pages, thereby integrating peer-to-peer querying and Web querying in a common declarative framework. Author Affiliation: School of Computer Science and Software Engineering, Monash University, 900 Dandenong Road, Caulfield East, Melbourne, Vic. 3145, Australia Article History: Received 20 August 2003; Revised 6 April 2005; Accepted 6 April 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.04.040 Byline: Juan J. Cuadrado-Gallego (a), Miguel-Angel Sicilia (a), Miguel Garre (a), Daniel Rodriguez (b) Keywords: Parametric software effort estimation; Clustering algorithms; Software cost drivers; EM algorithm Abstract: Parametric software effort estimation models consisting on a single mathematical relationship suffer from poor adjustment and predictive characteristics in cases in which the historical database considered contains data coming from projects of a heterogeneous nature. The segmentation of the input domain according to clusters obtained from the database of historical projects serves as a tool for more realistic models that use several local estimation relationships. Nonetheless, it may be hypothesized that using clustering algorithms without previous consideration of the influence of well-known project attributes misses the opportunity to obtain more realistic segments. In this paper, we describe the results of an empirical study using the ISBSG-8 database and the EM clustering algorithm that studies the influence of the consideration of two process-related attributes as drivers of the clustering process: the use of engineering methodologies and the use of CASE tools. The results provide evidence that such consideration conditions significantly the final model obtained, even though the resulting predictive quality is of a similar magnitude. Author Affiliation: (a) Computer Science Department, Polytechnic School, University of Alcala. Ctra. Barcelona km. 33.6, 28871 Alcala de Henares, Madrid, Spain (b) Computer Science Department, University of Reading, Reading RG6 6AY, UK Article History: Received 15 February 2005; Revised 23 April 2005; Accepted 23 April 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2004.10.012 Byline: Min-Jae Lee (a), Kyu-Young Whang (a), Wook-Shin Han (b), Il-Yeol Song (c) Keywords: Spatial join; Corner transformation; Databases Abstract: A transform-space index indexes spatial objects represented as points in the transform space. An advantage of a transform-space index is that optimization of spatial join algorithms using these indexes can be more formal. The authors earlier proposed the Transform-Based Spatial Join algorithm that joins two transform-space indexes. It renders global optimization easy with little overhead by utilizing the characteristics of the transform space. In particular, it allows us to globally determine the order of accessing disk pages, which makes a significant impact on the performance of joins. For this purpose, we use various space filling curves. In this paper, we propose a new space filling curve called the adaptive row major order (ARM order). The ARM order adaptively controls the order of accessing pages and significantly reduces the one-pass buffer size (the minimum buffer size required for guaranteeing one disk access per page) and the number of disk accesses for a given buffer size. Through analysis and experiments, we verify excellence of the ARM order when used with the Transform-Based Spatial Join. The Transform-Based Spatial Join with the ARM order always outperforms those with other conventional space filling curves in terms of both measures used: the one-pass buffer size and the number of disk accesses. Specifically, it reduces the one-pass buffer size by up to 25.9 times and the number of disk accesses by up to 2.11 times. We conclude that we achieve these results mainly due to global optimization of the order of accessing disk pages using an adaptive space filling curve. Author Affiliation: (a) Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science and Technology (KAIST), 373-1, Koo-Sung Dong, Yoo-Sung Ku, Daejeon 305-701, Republic of Korea (b) Department of Computer Engineering, Kyungpook National University, Sankyuk-Dong, Buk-Gu, Daegu 702-701, Republic of Korea (c) College of Information Science and Technology, Drexel University, Philadelphia, PA, USA Article History: Received 4 December 2003; Revised 18 October 2004; Accepted 18 October 2004

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2004.05.029 Byline: Shi-Wu Lo (a), Tei-Wei Kuo (a), Kam-Yiu Lam (b) Keywords: Real-time disk scheduling; RAID-0; Multi-disk scheduling Abstract: In this paper, we study the scheduling problem of real-time disk requests in multi-disk systems, such as RAID-0. We first propose a multi-disk scheduling algorithm, called Least-Remaining-Request-Size-First (LRSF), to improve soft real-time performance of I/O systems. LRSF may be integrated with different real-time/non-real-time single-disk scheduling algorithms, such as SATF and SSEDV, adopted by the disks in a multi-disk system. We then extend LRSF by considering the serving requests on-the-way (OTW) to the target request to minimize the starvation problem for requests that need to retrieve a large amount of data. The pre-fetching issue in RAID-0 is also studied to further improve the I/O performance. The performance of the proposed algorithm and schemes is investigated and compared with other disk scheduling algorithms through a series of experiments using both randomly generated workload and realistic workload. Author Affiliation: (a) Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC (b) Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong Article History: Received 21 March 2003; Revised 23 May 2004; Accepted 23 May 2004