%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.00", %%% date = "18 March 2009", %%% time = "21:36:53 MST", %%% filename = "taas.bib", %%% address = "University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "43644 2598 14392 132937", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "ACM Transactions on Autonomous and Adaptive %%% Systems (TAAS); bibliography; TAAS", %%% license = "public domain", %%% supported = "yes", %%% docstring = "This is a COMPLETE BibTeX bibliography for %%% ACM Transactions on Autonomous and Adaptive %%% Systems (TAAS) (CODEN ????, ISSN 1556-4665)), %%% covering all journal issues from 2006 -- %%% date. %%% %%% At version 1.00, the COMPLETE journal %%% coverage looked like this: %%% %%% 2006 ( 11) 2008 ( 21) %%% 2007 ( 17) 2009 ( 9) %%% %%% Article: 58 %%% %%% Total entries: 58 %%% %%% The journal Web page can be found at: %%% %%% http://www.acm.org/pubs/taas.html %%% %%% The journal table of contents page is at: %%% %%% http://www.acm.org/taas/ %%% http://portal.acm.org/browse_dl.cfm?idx=J1010 %%% %%% Qualified subscribers can retrieve the full %%% text of recent articles in PDF form. %%% %%% The initial draft was extracted from the ACM %%% Web pages. %%% %%% ACM copyrights explicitly permit abstracting %%% with credit, so article abstracts, keywords, %%% and subject classifications have been %%% included in this bibliography wherever %%% available. Article reviews have been %%% omitted, until their copyright status has %%% been clarified. %%% %%% bibsource keys in the bibliography entries %%% below indicate the entry originally came %%% from the computer science bibliography %%% archive, even though it has likely since %%% been corrected and updated. %%% %%% URL keys in the bibliography point to %%% World Wide Web locations of additional %%% information about the entry. %%% %%% BibTeX citation tags are uniformly chosen %%% as name:year:abbrev, where name is the %%% family name of the first author or editor, %%% year is a 4-digit number, and abbrev is a %%% 3-letter condensation of important title %%% words. Citation tags were automatically %%% generated by software developed for the %%% BibNet Project. %%% %%% In this bibliography, entries are sorted in %%% publication order, using ``bibsort -byvolume.'' %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility." %%% } %%% ==================================================================== @Preamble{"\input bibnames.sty" # "\def \TM {${}^{\sc TM}$}" } %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb = "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Journal abbreviations: @String{j-TAAS = "ACM Transactions on Autonomous and Adaptive Systems (TAAS)"} %%% ==================================================================== %%% Bibliography entries: @Article{Serugendo:2006:I, author = "Giovanna Di Marzo Serugendo", title = "Introduction", journal = j-TAAS, volume = "1", number = "1", pages = "1--3", month = sep, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1152934.1152935", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:22 MDT 2009", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Labella:2006:DLG, author = "Thomas H. Labella and Marco Dorigo and Jean-Louis Deneubourg", title = "Division of labor in a group of robots inspired by ants' foraging behavior", journal = j-TAAS, volume = "1", number = "1", pages = "4--25", month = sep, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1152934.1152936", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:22 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In this article, we analyze the behavior of a group of robots involved in an object retrieval task. The robots' control system is inspired by a model of ants' foraging. This model emphasizes the role of learning in the individual. Individuals adapt to the environment using only locally available information. We show that a simple parameter adaptation is an effective way to improve the efficiency of the group and that it brings forth division of labor between the members of the group. Moreover, robots that are best at retrieving have a higher probability of becoming active retrievers. This selection of the best members does not use any explicit representation of individual capabilities. We analyze this system and point out its strengths and its weaknesses.", acknowledgement = ack-nhfb, keywords = "adaptation; adaptive systems; ant algorithms; bio-inspired systems", } @Article{Babaoglu:2006:DPB, author = "Ozalp Babaoglu and Geoffrey Canright and Andreas Deutsch and Gianni A. Di Caro and Frederick Ducatelle and Luca M. Gambardella and Niloy Ganguly and M{\'a}rk Jelasity and Roberto Montemanni and Alberto Montresor and Tore Urnes", title = "Design patterns from biology for distributed computing", journal = j-TAAS, volume = "1", number = "1", pages = "26--66", month = sep, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1152934.1152937", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:22 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Recent developments in information technology have brought about important changes in distributed computing. New environments such as massively large-scale, wide-area computer networks and mobile ad hoc networks have emerged. Common characteristics of these environments include extreme dynamicity, unreliability, and large scale. Traditional approaches to designing distributed applications in these environments based on central control, small scale, or strong reliability assumptions are not suitable for exploiting their enormous potential. Based on the observation that living organisms can effectively organize large numbers of unreliable and dynamically-changing components (cells, molecules, individuals, etc.) into robust and adaptive structures, it has long been a research challenge to characterize the key ideas and mechanisms that make biological systems work and to apply them to distributed systems engineering. In this article we propose a conceptual framework that captures several basic biological processes in the form of a family of design patterns. Examples include plain diffusion, replication, chemotaxis, and stigmergy. We show through examples how to implement important functions for distributed computing based on these patterns. Using a common evaluation methodology, we show that our bio-inspired solutions have performance comparable to traditional, state-of-the-art solutions while they inherit desirable properties of biological systems including adaptivity and robustness.", acknowledgement = ack-nhfb, keywords = "ad-hoc networks; bio-inspiration; distributed design patterns; peer-to-peer; self-&ast", } @Article{Mena:2006:SRS, author = "Eduardo Mena and Arantza Illarramendi and Jose A. Royo and Alfredo Go{\~n}I", title = "A software retrieval service based on adaptive knowledge-driven agents for wireless environments", journal = j-TAAS, volume = "1", number = "1", pages = "67--90", month = sep, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1152934.1152938", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:22 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "The ability to retrieve software in an easy and efficient way confers competitive advantage on computer users in general and, even more especially, on users of wireless devices (like some laptops, PDAs, etc.). In this article, we present a software retrieval service that allows users to select and retrieve software in an easy and efficient way, anywhere and anytime. Two relevant components of this service are: 1) a software ontology (software catalog) which provides users with a semantic description of software elements, hiding the location and access method of various software repositories, and 2) a set of specialist agents that allow browsing of the software catalog (automatically customized for each user), and an efficient retrieval method for the selected software. These agents automatically adapt their behavior to different users and situations by considering the profile and preferences of the users and the network status. In summary, our software-obtaining process based on an ontology and autonomous and adaptive agents presents a qualitative advance with respect to existing solutions: our approach adapts to the features of users, relieving them from knowing the technical features of their devices and the location and access method of various remote software repositories.", acknowledgement = ack-nhfb, keywords = "adaptive multiagent systems; pervasive and mobile computing; Software retrieval", } @Article{Khan:2006:AFE, author = "Masood Mehmood Khan and Michael Ingleby and Robert D. Ward", title = "Automated Facial Expression Classification and affect interpretation using infrared measurement of facial skin temperature variations", journal = j-TAAS, volume = "1", number = "1", pages = "91--113", month = sep, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1152934.1152939", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:22 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Machines would require the ability to perceive and adapt to affects for achieving artificial sociability. Most autonomous systems use Automated Facial Expression Classification (AFEC) and Automated Affect Interpretation (AAI) to achieve sociability. Varying lighting conditions, occlusion, and control over physiognomy can influence the real life performance of vision-based AFEC systems. Physiological signals provide complementary information for AFEC and AAI. We employed transient facial thermal features for AFEC and AAI. Infrared thermal images with participants' normal expression and intentional expressions of happiness, sadness, disgust, and fear were captured. Facial points that undergo significant thermal changes with a change in expression termed as Facial Thermal Feature Points (FTFPs) were identified. Discriminant analysis was invoked on principal components derived from the Thermal Intensity Values (TIVs) recorded at the FTFPs. The cross-validation and person-independent classification respectively resulted in 66.28\% and 56.0\% success rates. Classification significance tests suggest that (1) like other physiological cues, facial skin temperature also provides useful information about affective states and their facial expression; (2) patterns of facial skin temperature variation can complement other cues for AFEC and AAI; and (3) infrared thermal imaging may help achieve artificial sociability in robots and autonomous systems.", acknowledgement = ack-nhfb, keywords = "Automated affect recognition; facial expression classification; infrared thermal imaging; socially intelligent machines", } @Article{TAAS-Staff:2006:R, author = "{ACM Transactions on Autonomous and Adaptive Systems staff}", title = "Reviewers", journal = j-TAAS, volume = "1", number = "1", pages = "114--114", month = sep, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1152934.1152940", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:22 MDT 2009", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Tuci:2006:CTS, author = "Elio Tuci and Roderich Gro{\ss} and Vito Trianni and Francesco Mondada and Michael Bonani and Marco Dorigo", title = "Cooperation through self-assembly in multi-robot systems", journal = j-TAAS, volume = "1", number = "2", pages = "115--150", month = dec, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1186778.1186779", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:40 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "This article illustrates the methods and results of two sets of experiments in which a group of mobile robots, called {\em s-bots}, are required to physically connect to each other, that is, to self-assemble, to cope with environmental conditions that prevent them from carrying out their task individually. The first set of experiments is a pioneering study on the utility of self-assembling robots to address relatively complex scenarios, such as cooperative object transport. The results of our work suggest that the s-bots possess hardware characteristics which facilitate the design of control mechanisms for autonomous self-assembly. The control architecture we developed proved particularly successful in guiding the robots engaged in the cooperative transport task. However, the results also showed that some features of the robots' controllers had a disruptive effect on their performances. The second set of experiments is an attempt to enhance the adaptiveness of our multi-robot system. In particular, we aim to synthesise an integrated (i.e., not-modular) decision-making mechanism which allows the s-bot to autonomously decide whether or not environmental contingencies require self-assembly. The results show that it is possible to synthesize, by using evolutionary computation techniques, artificial neural networks that integrate both the mechanisms for sensory-motor coordination and for decision making required by the robots in the context of self-assembly.", acknowledgement = ack-nhfb, keywords = "artificial neural networks; evolutionary algorithms; evolutionary robotics; self-assembly; swarm intelligence; Swarm robotics", } @Article{Soundararajan:2006:RPB, author = "Gokul Soundararajan and Cristiana Amza", title = "Reactive provisioning of backend databases in shared dynamic content server clusters", journal = j-TAAS, volume = "1", number = "2", pages = "151--188", month = dec, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1186778.1186780", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:40 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "This paper introduces a self-configuring architecture for on-demand resource allocation to applications in a shared database cluster. We use a unified approach to load and fault management based on data replication and reactive replica provisioning. While data replication provides scaling and high availability, reactive provisioning dynamically allocates additional replicas to applications in response to peak loads or failure conditions, thus providing per application performance. We design an efficient method for data migration when joining a new replica to a running application that allows for the quick addition of replicas with minimal disruption of transaction processing. Furthermore, by augmenting the adaptation feedback loop with awareness of the delay introduced by the data migration process in our replicated system, we avoid oscillations in resource allocation. We investigate our transparent database provisioning mechanisms in the context of multitier dynamic content Web servers. We dynamically expand/contract the respective allocations within the database tier for two different applications, the TPC-W e-commerce benchmark and the RUBIS online auction benchmark. We demonstrate that our techniques provide quality of service under different load and failure scenarios.", acknowledgement = ack-nhfb, keywords = "Autonomic systems; databases; query processing; transactions", } @Article{Gechter:2006:RAB, author = "Franck Gechter and Vincent Chevrier and Fran{\c{c}}ois Charpillet", title = "A reactive agent-based problem-solving model: Application to localization and tracking", journal = j-TAAS, volume = "1", number = "2", pages = "189--222", month = dec, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1186778.1186781", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:40 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "For two decades, multi-agent systems have been an attractive approach for problem solving and have been applied to a wide range of applications. Despite the lack of generic methodology, the reactive approach is interesting considering the properties it provides. This article presents a problem-solving model based on a swarm approach where agents interact using physics-inspired mechanisms. The initial problem and its constraints are represented through agents' environment, the dynamics of which is part of the problem-solving process. This model is then applied to localization and target tracking. Experiments assess our approach and compare it to widely-used classical algorithms.", acknowledgement = ack-nhfb, keywords = "localization; mobile robots; reactive multi-agent systems; tracking", } @Article{Dobson:2006:SAC, author = "Simon Dobson and Spyros Denazis and Antonio Fern{\'a}ndez and Dominique Ga{\"\i}ti and Erol Gelenbe and Fabio Massacci and Paddy Nixon and Fabrice Saffre and Nikita Schmidt and Franco Zambonelli", title = "A survey of autonomic communications", journal = j-TAAS, volume = "1", number = "2", pages = "223--259", month = dec, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1186778.1186782", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:40 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Autonomic communications seek to improve the ability of network and services to cope with unpredicted change, including changes in topology, load, task, the physical and logical characteristics of the networks that can be accessed, and so forth. Broad-ranging autonomic solutions require designers to account for a range of end-to-end issues affecting programming models, network and contextual modeling and reasoning, decentralised algorithms, trust acquisition and maintenance---issues whose solutions may draw on approaches and results from a surprisingly broad range of disciplines. We survey the current state of autonomic communications research and identify significant emerging trends and techniques.", acknowledgement = ack-nhfb, keywords = "Autonomic communication", } @Article{TAAS-223920005, author = "Pages: 260 - 261", title = "Reviewers", journal = j-TAAS, volume = "1", number = "2", pages = "260--261", month = dec, year = "2006", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1186778.1186783", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:33:40 MDT 2009", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Biskupski:2007:PMS, author = "Bartosz Biskupski and Jim Dowling and Jan Sacha", title = "Properties and mechanisms of self-organizing {MANET} and {P2P} systems", journal = j-TAAS, volume = "2", number = "1", pages = "1:1--1:??", month = mar, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1216895.1216896", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:02 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Despite the recent appearance of self-organizing distributed systems for Mobile Ad Hoc Networks (MANETs) and Peer-to-Peer (P2P) networks, specific theoretical aspects of both their properties and the mechanisms used to establish those properties have been largely overlooked. This has left many researchers confused as to what constitutes a self-organizing distributed system and without a vocabulary with which to discuss aspects of these systems. This article introduces an agent-based model of self-organizing MANET and P2P systems and shows how it is realised in three existing network systems. The model is based on concepts such as partial views, evaluation functions, system utility, feedback and decay. We review the three network systems, AntHocNet, SAMPLE, and Freenet, and show how they can achieve high scalability, robustness and adaptability to unpredictable changes in their environment, by using self-organizing mechanisms similar to those found in nature. They are designed to improve their operation in a dynamic, heterogeneous environment, enabling them to often demonstrate superior performance to state of the art distributed systems. This article is also addressed at researchers interested in gaining a general understanding of different mechanisms and properties of self-organization in distributed systems.", acknowledgement = ack-nhfb, articleno = "1", keywords = "Adaptive systems; complex systems; MANET; peer-to-peer; self-organization", } @Article{Kolan:2007:STD, author = "Prakash Kolan and Ram Dantu", title = "Socio-technical defense against voice spamming", journal = j-TAAS, volume = "2", number = "1", pages = "2:1--2:??", month = mar, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1216895.1216897", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:02 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Voice over IP (VoIP) is a key enabling technology for migration of circuit-switched PSTN (Public Switched Telephone Network) architectures to packet-based networks. One problem of the present VoIP networks is filtering spam calls referred to as SPIT (Spam over Internet Telephony). Unlike spam in e-mail systems, VoIP spam calls have to be identified in real time. Many of the techniques devised for e-mail spam detection rely upon content analysis, and in the case of VoIP, it is too late to analyze the content (voice) as the user would have already attended the call. Therefore, the real challenge is to block a spam call before the telephone rings. In addition, we believe it is imperative that spam filters integrate human behavioral aspects to gauge the legitimacy of voice calls. We know that, when it comes to receiving or rejecting a voice call, people use the social meaning of trust, reputation, friendship of the calling party and their own mood. In this article, we describe a multi-stage, adaptive spam filter based on presence (location, mood, time), trust, and reputation to detect spam in voice calls. In particular, we describe a closed-loop feedback control between different stages to decide whether an incoming call is spam. We further propose formalism for voice-specific trust and reputation analysis. We base this formal model on a human intuitive behavior for detecting spam based on the called party's direct and indirect relationships with the calling party. No VoIP corpus is available for testing the detection mechanism. Therefore, for verifying the detection accuracy, we used a laboratory setup of several soft-phones, real IP phones and a commercial-grade proxy server that receives and processes incoming calls. We experimentally validated the proposed filtering mechanisms by simulating spam calls and measured the filter's accuracy by applying the trust and reputation formalism. We observed that, while the filter blocks a second spam call from a spammer calling from the same end IP host and domain, the filter needs only a maximum of three calls---even in the case when spammer moves to a new host and domain. Finally, we present a detailed sensitivity analysis for examining the influence of parameters such as spam volume and network size on the filter's accuracy.", acknowledgement = ack-nhfb, articleno = "2", keywords = "behavior; reputation; SIP (Session Initiation Protocol); SPIT (Spam over IP Telephony); tolerance; Trust", } @Article{Litoiu:2007:PAM, author = "Marin Litoiu", title = "A performance analysis method for autonomic computing systems", journal = j-TAAS, volume = "2", number = "1", pages = "3:1--3:??", month = mar, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1216895.1216898", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:02 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In an {\em autonomic computing\/} system, an autonomic manager makes tuning, load balancing, or provisioning decisions based on a predictive model of the system. This article investigates performance analysis techniques used by the autonomic manager. It looks at the complexity of the workloads and presents algorithms for computing the bounds of performance metrics for distributed systems under {\em asymptotic\/} and {\em nonasymptotic\/} conditions, that is, with saturated and nonsaturated resources. The techniques used are hybrid in nature, making use of performance evaluation and linear and nonlinear programming models. The workloads are characterized by the {\em workload intensity}, which represents the total number of users in the system, and by the {\em workload mixes}, which depict the number of users in each class of service. The results presented in this article can be applied to distributed transactional systems. Such systems serve a large number of users with many classes of services and can thus be considered as representative of a large class of autonomic computing systems.", acknowledgement = ack-nhfb, articleno = "3", keywords = "autonomic computing; performance models; Self-management", } @Article{Mamei:2007:PPB, author = "Marco Mamei and Franco Zambonelli", title = "Pervasive pheromone-based interaction with {RFID} tags", journal = j-TAAS, volume = "2", number = "2", pages = "4:1--4:??", month = jun, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1242060.1242061", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:13 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Despite the growing interest in pheromone-based interaction to enforce adaptive and context-aware coordination, the number of deployed systems exploiting digital pheromones to coordinate the activities of situated autonomous agents is still very limited. In this article, we present a simple low-cost and general-purpose implementation of a pheromone-based interaction mechanism for pervasive environments. This is realized by making use of RFID tags to store digital pheromones and by having humans or robots spread/sense pheromones by properly writing/reading RFID tags populating the surrounding physical environment. We exemplify and evaluate the effectiveness of our approach via an application for object-tracking. This application allows robots and humans to find forgotten-somewhere objects by following pheromones trails associated with them. In addition, we sketch further potential applications of our approach in pervasive computing scenarios, discuss related work in the area, and identify future research directions.", acknowledgement = ack-nhfb, articleno = "4", keywords = "pervasive computing; RFID tags; stigmergy", } @Article{Johnson:2007:MHD, author = "Jeffrey H. Johnson and Pejman Iravani", title = "The multilevel hypernetwork dynamics of complex systems of robot soccer agents", journal = j-TAAS, volume = "2", number = "2", pages = "5:1--5:??", month = jun, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1242060.1242062", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:13 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "A mathematical formalism is sketched for representing relational structure between agents. {\em n\/} -ary relations, {\em n\/} > 2, require hypernetworks, which generalize binary relation networks. {\em n\/} -ary relations on sets create structure at higher levels of representation to the elements in multilevel systems. The {\em state\/} of a system is represented by its multilevel relational structure. The {\em dynamics\/} of a system are represented by state changes through time. These can be continuous with no change in the hypernetwork topology, but often they are not. Controlling such systems involves taking actions intended to result in desirable state changes. The concept of multilevel hypernetwork can be applied to multiagent systems in general.", acknowledgement = ack-nhfb, articleno = "5", keywords = "agent; complex systems; hypernetwork; multiagent systems; multilevel representations; multilevel systems; Q-analysis; robotics; robot soccer; simulated multiagent football", } @Article{Chen:2007:ASN, author = "Jinjun Chen and Yun Yang", title = "Adaptive selection of necessary and sufficient checkpoints for dynamic verification of temporal constraints in grid workflow systems", journal = j-TAAS, volume = "2", number = "2", pages = "6:1--6:??", month = jun, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1242060.1242063", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:13 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In grid workflow systems, a checkpoint selection strategy is responsible for selecting checkpoints for conducting temporal verification at the runtime execution stage. Existing representative checkpoint selection strategies often select some unnecessary checkpoints and omit some necessary ones because they cannot adapt to the dynamics and uncertainty of runtime activity completion duration. In this article, based on the dynamics and uncertainty of runtime activity completion duration, we develop a novel checkpoint selection strategy that can adaptively select not only necessary, but also sufficient checkpoints. Specifically, we introduce a new concept of minimum time redundancy as a key reference parameter for checkpoint selection. An important feature of minimum time redundancy is that it can adapt to the dynamics and uncertainty of runtime activity completion duration. We develop a method on how to achieve minimum time redundancy dynamically along grid workflow execution and investigate its relationships with temporal consistency. Based on the method and the relationships, we present our strategy and rigorously prove its necessity and sufficiency. The simulation evaluation further demonstrates experimentally such necessity and sufficiency and its significant improvement on checkpoint selection over other representative strategies.", acknowledgement = ack-nhfb, articleno = "6", keywords = "adaptive checkpoint selection; Grid workflows; temporal constraints; temporal verification", } @Article{Tsai:2007:ISI, author = "Jeffrey J. P. Tsai and Mukesh Singhal", title = "Introduction: Special issue of the {IEEE SUTC'06}", journal = j-TAAS, volume = "2", number = "3", pages = "7:1--7:??", month = sep, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1278460.1278461", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:20 MDT 2009", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "7", } @Article{Herbert:2007:ACM, author = "Douglas Herbert and Vinaitheerthan Sundaram and Yung-Hsiang Lu and Saurabh Bagchi and Zhiyuan Li", title = "Adaptive correctness monitoring for wireless sensor networks using hierarchical distributed run-time invariant checking", journal = j-TAAS, volume = "2", number = "3", pages = "8:1--8:??", month = sep, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1278460.1278462", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "This article presents a hierarchical approach for detecting faults in wireless sensor networks (WSNs) after they have been deployed. The developers of WSNs can specify ``invariants'' that must be satisfied by the WSNs. We present a framework, Hierarchical SEnsor Network Debugging (H-SEND), for lightweight checking of invariants. H-SEND is able to detect a large class of faults in data-gathering WSNs, and leverages the existing message flow in the network by buffering and piggybacking messages. H-SEND checks as closely to the source of a fault as possible, pinpointing the fault quickly and efficiently in terms of additional network traffic. Therefore, H-SEND is suited to bandwidth or communication energy constrained networks. A specification expression is provided for specifying invariants so that a protocol developer can write behavioral level invariants. We hypothesize that data from sensor nodes does not change dramatically, but rather changes gradually over time. We extend our framework for the invariants that includes values determined at run-time in order to detect data trends. The value range can be based on information local to a single node or the surrounding nodes' values. Using our system, developers can write invariants to detect data trends without prior knowledge of correct values. Automatic value detection can be used to detect anomalies that cannot be detected in existing WSNs. To demonstrate the benefits of run-time range detection and fault checking, we construct a prototype WSN using CO$_2$ and temperature sensors coupled to Mica2 motes. We show that our method can detect sudden changes of the environments with little overhead in communication, computation, and storage.", acknowledgement = ack-nhfb, articleno = "8", keywords = "correctness monitoring; data integrity; fault tolerance and diagnostics; in-network processing and aggregation; Invariants; network protocols; programming models and languages; run-time; tools", } @Article{Shyu:2007:NID, author = "Mei-Ling Shyu and Thiago Quirino and Zongxing Xie and Shu-Ching Chen and Liwu Chang", title = "Network intrusion detection through Adaptive Sub-Eigenspace Modeling in multiagent systems", journal = j-TAAS, volume = "2", number = "3", pages = "9:1--9:??", month = sep, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1278460.1278463", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Recently, network security has become an extremely vital issue that beckons the development of accurate and efficient solutions capable of effectively defending our network systems and the valuable information journeying through them. In this article, a distributed multiagent intrusion detection system (IDS) architecture is proposed, which attempts to provide an accurate and lightweight solution to network intrusion detection by tackling issues associated with the design of a distributed multiagent system, such as poor system scalability and the requirements of excessive processing power and memory storage. The proposed IDS architecture consists of (i) the Host layer with lightweight host agents that perform anomaly detection in network connections to their respective hosts, and (ii) the Classification layer whose main functions are to perform misuse detection for the host agents, detect distributed attacks, and disseminate network security status information to the whole network. The intrusion detection task is achieved through the employment of the lightweight Adaptive Sub-Eigenspace Modeling (ASEM)-based anomaly and misuse detection schemes. Promising experimental results indicate that ASEM-based schemes outperform the KNN and LOF algorithms, with high detection rates and low false alarm rates in the anomaly detection task, and outperform several well-known supervised classification methods such as C4.5 Decision Tree, SVM, NN, KNN, Logistic, and Decision Table (DT) in the misuse detection task. To assess the performance in a real-world scenario, the Relative Assumption Model, feature extraction techniques, and common network attack generation tools are employed to generate normal and anomalous traffic in a private LAN testbed. Furthermore, the scalability performance of the proposed IDS architecture is investigated through the simulation of the proposed agent communication scheme, and satisfactory linear relationships for both degradation of system response time and agent communication generated network traffic overhead are achieved.", acknowledgement = ack-nhfb, articleno = "9", keywords = "adaptive sub-eigenspace modeling (ASEM); agent-based distributed system; Agent communications; intrusion detection; network security", } @Article{Ren:2007:RRS, author = "Shangping Ren and Yue Yu and Nianen Chen and Jeffrey J.-P. Tsai and Kevin Kwiat", title = "The role of roles in supporting reconfigurability and fault localizations for open distributed and embedded systems", journal = j-TAAS, volume = "2", number = "3", pages = "10:1--10:??", month = sep, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1278460.1278464", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "One of the main characteristics of open distributed embedded systems is that the involved entities are often very dynamic --- different individual entities may join or leave the systems frequently. Therefore, systems built of these dynamic entities must be runtime reconfigurable. In addition, large classes of open embedded systems often have high availability and dependability requirements. However, the openness makes these requirements more difficult to achieve and the system more vulnerable to attacks.\par This article presents a coordination model, the Actor, Role and Coordinator (ARC) model, that aims to support reconfigurability and fault localization for open distributed embedded software systems. In particular, the actor model is used to model concurrent embedded entities, while the system's reconfigurability and dependability requirements are encapsulated within coordination objects: roles and coordinators, and are achieved through coordination among the actors. Roles, as a key thrust in the ARC model not only represent an abstraction for a set of behaviors shared by a group of actors so that reconfiguration within the roles becomes transparent to entities outside the roles, but also assume coordination responsibilities among the member actors. The article also argues from both analytical and empirical perspectives that with the support of the role, faults can be localized within actors, and actor level reconfiguration becomes transparent to the system.", acknowledgement = ack-nhfb, articleno = "10", keywords = "actors; coordination; coordinators; open distributed embedded systems; roles", } @Article{Watanabe:2007:RFP, author = "Kenichi Watanabe and Yoshio Nakajima and Tomoya Enokido and Makoto Takizawa", title = "Ranking factors in peer-to-peer overlay networks", journal = j-TAAS, volume = "2", number = "3", pages = "11:1--11:??", month = sep, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1278460.1278465", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "A large number of peer processes are distributed in a peer-to-peer (P2P) overlay network. It is difficult, maybe impossible for a peer to perceive the membership and location of every resource object due to the scalability and openness of a P2P network. In this article, we discuss a fully distributed P2P system where there is no centralized controller. Each peer has to obtain service information from its acquaintance peers and also send its service information to the acquaintance peers. An acquaintance peer of a peer {\em p\/} is a peer about whose service the peer {\em p\/} knows and with which the peer {\em p\/} can directly communicate in an overlay network. Some acquaintance peer might hold obsolete service information and might be faulty. Each peer has to find a more trustworthy one among acquaintance peers. There are many discussions on how to detect peers that hold a target object. However, a peer cannot manipulate an object without being granted access rights (permissions). In addition to detecting what peers hold a target object, we have to find peers granted access rights to manipulate the target object. The trustworthiness of each acquaintance is defined in terms of the satisfiability and ranking factor in this article. The satisfiability of an acquaintance peer shows how much each peer can trust the acquaintance peer through direct communication to not only detect target objects but also obtain their access rights. On the other hand, the ranking factor of an acquaintance peer indicates how much the acquaintance peer is trusted only by trustworthy acquaintance peers which is different from the traditional reputation concept. We evaluate how the trustworthiness of an acquaintance peer is changed through interactions among peers in a detection algorithm.", acknowledgement = ack-nhfb, articleno = "11", keywords = "acquaintances; P2P overlay networks; ranking factor; satisfiability; trustworthiness", } @Article{Petta:2007:ISI, author = "Paolo Petta and Andrea Omicini and Terry Payne and Peter McBurney", title = "Introduction to the special issue: The {AgentLink III} technical forums", journal = j-TAAS, volume = "2", number = "4", pages = "12:1--12:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1293731.1293732", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:35 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "This article introduces the special issue of {\em ACM Transactions on Autonomous and Adaptive Systems\/} devoted to research papers arising from the three Technical Forum Group meetings held in 2004 and 2005 that were organized and sponsored by the European FP6 Coordination Action AgentLink III.", acknowledgement = ack-nhfb, articleno = "12", keywords = "AgentLink III; agent-oriented software engineering; autonomous agents; European research; multi-agent systems; technical forums", } @Article{Locatelli:2007:ACU, author = "Marco P. Locatelli and Giuseppe Vizzari", title = "Awareness in collaborative ubiquitous environments: The Multilayered Multi-Agent Situated System approach", journal = j-TAAS, volume = "2", number = "4", pages = "13:1--13:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1293731.1293733", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:35 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Collaborative Ubiquitous Environments (CUEs) are environments that support collaboration among persons in a context of ubiquitous computing. This article shows how results of the research in the Multi-Agent System (MAS) area, and in particular on MAS environments, can be used to model, design and engineer CUEs, with specific reference to the management of context-awareness information. After a description of the reference scenario, the Multilayered Multi-Agent Situated System model will be introduced and applied to represent and to manage several types of awareness information (both physical and logical contextual information). Finally, three different approaches to the design and engineering of CUEs will then be introduced and evaluated.", acknowledgement = ack-nhfb, articleno = "13", keywords = "context awareness; MAS environments", } @Article{Paurobally:2007:FWS, author = "Shamimabi Paurobally and Valentina Tamma and Michael Wooldrdige", title = "A Framework for Web service negotiation", journal = j-TAAS, volume = "2", number = "4", pages = "14:1--14:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1293731.1293734", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:35 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In a survey on the theory and practice of agent system deployment, conducted by the AgentLink workgroup on networked agents, it was found that there are an increasing number of initiatives for the migration of agents research towards new Internet technologies such as the semantic web, Grid, and Web services. In fact, Grid computing and multi-agent systems research have similar objectives. They both aim to achieve ``large-scale open distributed systems, capable of being able to effectively and dynamically deploy and redeploy computational (and other) resources as required, to solve computationally complex problems'' [Foster and Kesselman 2003]. On the one hand, service-oriented Grid architectures need to support dynamic cooperation, negotiation, and adaptive interactions between Web services controlling Grid resources for efficient resource and task allocation and execution. On the other hand, the Grid can facilitate agent communication, life-cycle management, and access to resources for agents. Although the relevance of Grid for agent research and vice versa has been identified in several forums, actual collaborative applications are still in their infancy. In this article, we discuss our recent work on deploying multi-agent negotiation techniques to facilitate dynamic negotiation for Grid resources as a step closer to an adaptive and autonomous Grid. In particular, we describe a Web service development of the Contract Net Protocol for negotiation between insurance companies and repair companies. We evaluate our approach to show the added value of negotiable interactions between Web services as opposed to inflexible single-shot interactions that are currently the state of the art.", acknowledgement = ack-nhfb, articleno = "14", keywords = "Grid; insurance; negotiation; Web services", } @Article{Poslad:2007:SPM, author = "Stefan Poslad", title = "Specifying protocols for multi-agent systems interaction", journal = j-TAAS, volume = "2", number = "4", pages = "15:1--15:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1293731.1293735", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:35 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Multi-Agent-Systems or MAS represent a powerful distributed computing model, enabling agents to cooperate and complete with each other and to exchange both semantic content and a semantic context to more automatically and accurately interpret the content. Many types of individual agent and MAS models have been proposed since the mid-1980s, but the majority of these have led to single developer homogeneous MAS systems. For over a decade, the FIPA standards activity has worked to produce public MAS specifications, acting as a key enabler to support interoperability, open service interaction, and to support heterogeneous development. The main characteristics of the FIPA model for MAS and an analysis of design, design choices and features of the model is presented. In addition, a comparison of the FIPA model for system interoperability versus those of other standards bodies is presented, along with a discussion of the current status of FIPA and future directions.", acknowledgement = ack-nhfb, articleno = "15", keywords = "autonomy; deployment; Multi-Agent systems; semantics; social interaction; specifications", } @Article{Penserini:2007:HVD, author = "Loris Penserini and Anna Perini and Angelo Susi and John Mylopoulos", title = "High variability design for software agents: Extending Tropos", journal = j-TAAS, volume = "2", number = "4", pages = "16:1--16:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1293731.1293736", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:35 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Many classes of distributed applications, including e-business, e-government, and ambient intelligence, consist of networking infrastructures, where the nodes (peers) --- be they software components, human actors or organizational units --- cooperate with each other to achieve shared goals. The multi-agent system metaphor fits very well such settings because it is founded on intentional and social concepts and mechanisms. Not surprisingly, many agent-oriented software development methods have been proposed, including GAIA, PASSI, and {\em Tropos}. This paper extends the {\em Tropos\/} methodology, enhancing its ability to support high variability design through the explicit modelling of alternatives, it adopts an extended notion of agent capability and proposes a refined {\em Tropos\/} design process. The paper also presents an implemented software development environment for {\em Tropos}, founded on the Model-Driven Architecture (MDA) framework and standards. The extended {\em Tropos\/} development process is illustrated through a case study involving an e-commerce application.", acknowledgement = ack-nhfb, articleno = "16", keywords = "Agent capability design; agent-oriented software engineering; early requirements; goal-oriented requirements engineering", } @Article{TAAS-224970006, author = "Article No. 17", title = "Reviewers 2007", journal = j-TAAS, volume = "2", number = "4", pages = "17:1--17:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1293731.1293737", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:35 MDT 2009", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "17", } @Article{Urgaonkar:2008:ADP, author = "Bhuvan Urgaonkar and Prashant Shenoy and Abhishek Chandra and Pawan Goyal and Timothy Wood", title = "Agile dynamic provisioning of multi-tier Internet applications", journal = j-TAAS, volume = "3", number = "1", pages = "1:1--1:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1342171.1342172", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:52 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Dynamic capacity provisioning is a useful technique for handling the multi-time-scale variations seen in Internet workloads. In this article, we propose a novel dynamic provisioning technique for multi-tier Internet applications that employs (1) a flexible queuing model to determine how much of the resources to allocate to each tier of the application, and (2) a combination of predictive and reactive methods that determine when to provision these resources, both at large and small time scales. We propose a novel data center architecture based on virtual machine monitors to reduce provisioning overheads. Our experiments on a forty-machine Xen/Linux-based hosting platform demonstrate the responsiveness of our technique in handling dynamic workloads. In one scenario where a flash crowd caused the workload of a three-tier application to double, our technique was able to double the application capacity within five minutes, thus maintaining response-time targets. Our technique also reduced the overhead of switching servers across applications from several minutes to less than a second, while meeting the performance targets of residual sessions.", acknowledgement = ack-nhfb, articleno = "1", keywords = "dynamic provisioning; Internet application", } @Article{Hilaire:2008:AAA, author = "Vincent Hilaire and Abder Koukam and Sebastian Rodriguez", title = "An adaptative agent architecture for holonic multi-agent systems", journal = j-TAAS, volume = "3", number = "1", pages = "2:1--2:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1342171.1342173", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:52 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Self-organized multi-agent systems (MAS) are still difficult to engineer, because, to deal with real world problems, a self-organized MAS should exhibit complex adaptive organizations. In this respect the holonic paradigm provides a solution for modelling complex organizational structures. Holons are defined as self-similar entities that are neither parts nor wholes. The organizational structure produced by holons is called a holarchy. A holonic MAS (HMAS) considers agents as holons that are grouped according to holarchies. The goal of this article is to introduce an architecture that allows holons to adapt to their environment. The metaphor is based upon the immune system and considers stimulations/requests as antigens and selected antibodies as reactions/answers. Each antibody is activated by specific antigens and stimulated and/or inhibited by other antibodies. The immune system rewards (respectively penalizes) selected antibodies, which constitutes a good (respectively wrong) answer to a request. This mechanism allows an agent to choose from a set of possible behaviors, the one that seems the best fit for a specific context. In this context, each holon, atomic or composed, encapsulates an immune system in order to select a behavior. For composed holons, each sub-holon is represented by the selected antibody of its immune system. The super-holon's immune system therefore contains one antibody per sub-holon. This recursive architecture corresponds with the recursive nature of the holarchy. This architecture is presented with an example of simulated robot soccer. From experiments under different conditions we show that this architecture has interesting properties.", acknowledgement = ack-nhfb, articleno = "2", keywords = "Agents; holonic systems; immune systems", } @Article{Shen:2008:ABD, author = "Chien-Chung Shen and Ke Li and Chaiporn Jaikaeo and Vinay Sridhara", title = "Ant-based distributed constrained steiner tree algorithm for jointly conserving energy and bounding delay in ad hoc multicast routing", journal = j-TAAS, volume = "3", number = "1", pages = "3:1--3:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1342171.1342174", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:52 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "The minimum-energy multicast tree problem aims to construct a multicast tree rooted at the source node and spanning all the destination nodes such that the sum of transmission power at non-leaf nodes is minimized. However, aggressive power assignment at non-leaf nodes, although conserving more energy, results in multicast trees that suffer from higher hop count and jeopardizes delay-sensitive applications, signifying a clear tradeoff between energy efficiency and delay. This article formulates these issues as a {\em constrained Steiner tree\/} problem, and describes a distributed constrained Steiner tree algorithm, which jointly conserves energy and bounds delay for multicast routing in ad hoc networks. In particular, the proposed algorithm concurrently constructs a constrained Steiner tree, performs transmission power assignment at non-leaf nodes, and strives to minimize the sum of transmission power of non-leaf nodes, subject to the given maximum hop count constraint. Simulation results validate the effectiveness and reveal the characteristics of the proposed algorithm.", acknowledgement = ack-nhfb, articleno = "3", keywords = "Ad hoc networks; constrained Steiner tree; multicast; swarm intelligence", } @Article{Gelenbe:2008:AQA, author = "Erol Gelenbe and Georgia Sakellari and Maurizio D'arienzo", title = "Admission of {QoS} aware users in a smart network", journal = j-TAAS, volume = "3", number = "1", pages = "4:1--4:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1342171.1342175", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:34:52 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Smart networks have grown out of the need for stable, reliable, and predictable networks that will guarantee packet delivery under Quality of Service (QoS) constraints. In this article we present a measurement-based admission control algorithm that helps control traffic congestion and guarantee QoS throughout the lifetime of a connection. When a new user requests to enter the network, probe packets are sent from the source to the destination to estimate the impact that the new connection will have on the QoS of both the new and the existing users. The algorithm uses a novel algebra of QoS metrics, inspired by Warshall's algorithm, to look for a path with acceptable QoS values to accommodate the new flow. We describe the underlying mathematical principles and present experimental results obtained by evaluating the method in a large laboratory test-bed operating the Cognitive Packet Network (CPN) protocol.", acknowledgement = ack-nhfb, articleno = "4", keywords = "cognitive packet network; measurement-based admission control; quality of service; self-aware", } @Article{Forestiero:2008:GSO, author = "Agostino Forestiero and Carlo Mastroianni and Giandomenico Spezzano", title = "So-Grid: {A} self-organizing Grid featuring bio-inspired algorithms", journal = j-TAAS, volume = "3", number = "2", pages = "5:1--5:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1352789.1352790", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:04 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "This article presents So-Grid, a set of bio-inspired algorithms tailored to the decentralized construction of a {\em Grid\/} information system that features adaptive and self-organization characteristics. Such algorithms exploit the properties of {\em swarm\/} systems, in which a number of entities/agents perform simple operations at the local level, but together engender an advanced form of {\em swarm intelligence\/} at the global level. In particular, So-Grid provides two main functionalities: logical reorganization of resources, inspired by the behavior of some species of ants and termites that move and collect items within their environment, and resource discovery, inspired by the mechanisms through which ants searching for food sources are able to follow the pheromone traces left by other ants. These functionalities are correlated, since an intelligent dissemination can facilitate discovery. In the Grid environment, a number of ant-like agents autonomously travel the Grid through P2P interconnections and use biased probability functions to: (i) replicate resource descriptors in order to favor resource discovery; (ii) collect resource descriptors with similar characteristics in nearby Grid hosts; (iii) foster the dissemination of descriptors corresponding to {\em fresh\/} (recently updated) resources and to resources having high quality of service (QoS) characteristics. Simulation analysis shows that the So-Grid replication algorithm is capable of reducing the entropy of the system and efficiently disseminating content. Moreover, as descriptors are progressively reorganized and replicated, the So-Grid discovery algorithm allows users to reach Grid hosts that store information about a larger number of useful resources in a shorter amount of time. The proposed approach features characteristics, including self-organization, scalability and adaptivity, which make it useful for a dynamic and partially unreliable distributed system.", acknowledgement = ack-nhfb, articleno = "5", keywords = "Grid; multiagent systems; P2P; resource discovery; self-organization; swarm intelligence", } @Article{Gounaris:2008:CTA, author = "Anastasios Gounaris and Christos Yfoulis and Rizos Sakellariou and Marios D. Dikaiakos", title = "A control theoretical approach to self-optimizing block transfer in Web service grids", journal = j-TAAS, volume = "3", number = "2", pages = "6:1--6:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1352789.1352791", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:04 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Nowadays, Web Services (WS) play an important role in the dissemination and distributed processing of large amounts of data that become available on the Web. In many cases, it is essential to retrieve and process such data in blocks, in order to benefit from pipelined parallelism and reduced communication costs. This article deals with the problem of minimizing at runtime, in a self-managing way, the total response time of a call to a database exposed to a volatile environment, like the Grid, as a WS. Typically, in this scenario, response time exhibits a concave, nonlinear behavior depending on the client-controlled size of the individual requests comprising a fixed size task. In addition, no accurate profiling or internal state information is available, and the optimum point is volatile. This situation is encountered in several systems, such as WS Management Systems (WSMS) for DBMS-like data management over wide area service-based networks, and the widely spread OGSA-DAI WS for accessing and integrating traditional DBMS. The main challenges in this problem apart from the unavailability of a model, include the presence of noise, which incurs local minima, the volatility of the environment, which results in moving optimum operating point, and the requirements for fast convergence to the optimal size of the request from the side of the client rather than of the server, and for low overshooting. Two solutions are presented in this work, which fall into the broader areas of runtime optimization and switching extremum control. They incorporate heuristics to avoid local optimal points, and address all the aforementioned challenges. The effectiveness of the solutions is verified via both empirical evaluation in real cases and simulations, which show that significant performance benefits can be provided rendering obsolete the need for detailed profiling of the WS.", acknowledgement = ack-nhfb, articleno = "6", keywords = "Autonomic computing; control theory; data grids; extremum control; OGSA-DAI; Web Services", } @Article{Garruzzo:2008:ACB, author = "Salvatore Garruzzo and Domenico Rosaci", title = "Agent clustering based on semantic negotiation", journal = j-TAAS, volume = "3", number = "2", pages = "7:1--7:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1352789.1352792", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:04 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Forming groups of agents is an important task in many agent-based applications, for example when determining a coalition of buyers in an e-commerce community or organizing different Web services in a Web services' composition. A key issue in this context is that of generating groups of agents such that the communication among agents of the same group is not subjected to comprehension problems. To this purpose, several approaches have been proposed in the past in order to form groups of agents based on some similarity measures among agents. Such similarity measures are mainly based on lexical and/or structural similarities among agent ontologies. However, the necessity of taking into account a semantic component of the similarity value arises, for example by considering the context in which a term is used in an agent ontology. Therefore we propose a clustering technique based on the HISENE semantic negotiation protocol, using a similarity value that has lexical, structural and semantic components. Moreover, we introduce a suitable multiagent architecture that allows computing agent similarities by means of an efficient distributed approach.", acknowledgement = ack-nhfb, articleno = "7", keywords = "Ontologies; open multiagent systems; semantic negotiation", } @Article{Baumes:2008:VVR, author = "Jeffrey Baumes and Hung-Ching (Justin) Chen and Matthew Francisco and Mark Goldberg and Malik Magdon-Ismail and William Wallace", title = "{ViSAGE}: {A} {\em Vi\/} rtual Laboratory for {\em S\/}imulation and {\em A\/}nalysis of Social {\em G\/}roup {\em E\/}volution", journal = j-TAAS, volume = "3", number = "3", pages = "8:1--8:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1380422.1380423", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:13 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present a modeling laboratory, Virtual Laboratory for the Simulation and Analysis of Social Group Evolution (ViSAGE), that views the organization of human communities and the experience of individuals in a community as contingent upon on the dynamic properties, or {\em micro-laws}, of social groups. The laboratory facilitates the theorization and validation of these properties through an iterative research processes that involves (1) forward simulation experiments, which are used to formalize dynamic group properties, (2) reverse engineering from real data on how the parameters are distributed among individual actors in the community, and (3) grounded research, such as participant observation, that follows specific activities of real actors in a community and determines if, or how well, the micro-laws describe the way choices are made in real world, local settings. In this article we report on the design of ViSAGE. We first give some background to the model. Next we detail each component. We then describe a set of simulation experiments that we used to further design and clarify ViSAGE as a tool for studying emergent properties/phenomena in social networks.", acknowledgement = ack-nhfb, articleno = "8", keywords = "agent-based modeling and simulation; social capital; virtual social science laboratory", } @Article{Koshutanski:2008:IAC, author = "Hristo Koshutanski and Fabio Massacci", title = "Interactive access control for autonomic systems: From theory to implementation", journal = j-TAAS, volume = "3", number = "3", pages = "9:1--9:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1380422.1380424", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:13 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Autonomic communication and computing is a new paradigm for dynamic service integration over a network. An autonomic network crosses organizational and management boundaries and is provided by entities that see each other just as partners. For many services no autonomic partner may guess a priori what will be sent by clients nor clients know a priori what credentials are required to access a service.\par To address this problem we propose a new {\em interactive access control\/}: servers should interact with clients, asking for missing credentials necessary to grant access, whereas clients may supply or decline the requested credentials. Servers evaluate their policies and interact with clients until a decision of grant or deny is taken.\par This proposal is grounded in a formal model on policy-based access control. It identifies the formal reasoning services of deduction, abduction and consistency. Based on them, the work proposes a comprehensive access control framework for autonomic systems. An implementation of the interactive model is given followed by system performance evaluation.", acknowledgement = ack-nhfb, articleno = "9", keywords = "abduction; autonomic systems; disclosure control; Interactive access control; logic programming; nonmonotonic policy", } @Article{Yu:2008:AAT, author = "Zhenwei Yu and Jeffrey J. P. Tsai and Thomas Weigert", title = "An adaptive automatically tuning intrusion detection system", journal = j-TAAS, volume = "3", number = "3", pages = "10:1--10:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1380422.1380425", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:13 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "An intrusion detection system (IDS) is a security layer to detect ongoing intrusive activities in computer systems and networks. Current IDS have two main problems: The first problem is that typically so many alarms are generated as to overwhelm the system operator, many of these being false alarms. The second problem is that continuous tuning of the intrusion detection model is required in order to maintain sufficient performance due to the dynamically changing nature of the monitored system. This manual tuning process relies on the system operators to work out the updated tuning solution and to integrate it into the detection model.\par In this article, we present an automatically tuning intrusion detection system, which controls the number of alarms output to the system operator and tunes the detection model on the fly according to feedback provided by the system operator when false predictions are identified. This system adapts its behavior (i) by throttling the volume of alarms output to the operator in response to the ability of the operator to respond to these alarms, and (ii) by deciding how aggressively the detection model should be tuned based on the accuracy of earlier predictions. We evaluated our system using the KDDCup'99 intrusion detection dataset. Our results show that an adaptive, automatically tuning intrusion detection system will be both practical and efficient.", acknowledgement = ack-nhfb, articleno = "10", keywords = "Fuzzy control; intrusion detection", } @Article{Ko:2008:NCN, author = "Steven Y. Ko and Indranil Gupta and Yookyung Jo", title = "A new class of nature-inspired algorithms for self-adaptive peer-to-peer computing", journal = j-TAAS, volume = "3", number = "3", pages = "11:1--11:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1380422.1380426", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:13 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present, and evaluate benefits of, a design methodology for translating natural phenomena represented as mathematical models, into novel, self-adaptive, peer-to-peer (p2p) distributed computing algorithms ({\em protocols\/}). Concretely, our first contribution is a set of techniques to translate discrete {\em sequence equations\/} (also known as difference equations) into new p2p protocols called {\em sequence protocols}. Sequence protocols are self-adaptive, scalable, and fault-tolerant, with applicability in p2p settings like Grids. A sequence protocol is a set of probabilistic local and message-passing actions for each process. These actions are translated from terms in a set of source sequence equations. Individual processes do not simulate the source sequence equations completely. Instead, each process executes probabilistic local and message passing actions, so that the emergent round-to-round behavior of the sequence protocol in a p2p system can be probabilistically predicted by the source sequence equations. The article's second contribution is the design and evaluation of a set of sequence protocols for detection of two global triggers in a distributed system: threshold detection and interval detection. This article's third contribution is a new self-adaptive Grid computing protocol called HoneyAdapt. HoneyAdapt is derived from sequence equations modeling adaptive bee foraging behavior in nature. HoneyAdapt is intended for Grid applications that allow Grid clients, at run-time, a choice of algorithms for executing chunks of the application's dataset. HoneyAdapt tells each Grid client how to adaptively select at run-time, for each chunk it receives, a good algorithm for computing the chunk --- this selection is based on continuous feedback from other clients. Finally, we design a variant of HoneyAdapt, called HoneySort, for application to Grid parallelized sorting settings using the master-worker paradigm. Our evaluation of these contributions consists of mathematical analysis, large-scale trace-based simulation results, and experimental results from a HoneySort deployment.", acknowledgement = ack-nhfb, articleno = "11", keywords = "adaptivity; autonomic computing and communication; bio-inspired techniques; Complex adaptive systems; convergence; design methodology; difference equations; distributed protocols; grid computing; probabilistic protocols; sequence equations; sequence protocols", } @Article{Datta:2008:ISI, author = "Ajoy K. Datta", title = "Introduction to special issue on stabilization, safety, and security of distributed systems", journal = j-TAAS, volume = "3", number = "4", pages = "12:1--12:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452002", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "12", } @Article{Angluin:2008:SSP, author = "Dana Angluin and James Aspnes and Michael J. Fischer and Hong Jiang", title = "Self-stabilizing population protocols", journal = j-TAAS, volume = "3", number = "4", pages = "13:1--13:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452003", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "This article studies self-stabilization in networks of anonymous, asynchronously interacting nodes where the size of the network is unknown. Constant-space protocols are given for Dijkstra-style round-robin token circulation, leader election in rings, two-hop coloring in degree-bounded graphs, and establishing consistent global orientation in an undirected ring. A protocol to construct a spanning tree in regular graphs using {\em O\/} (log {\em D\/}) memory is also given, where {\em D\/} is the diameter of the graph. A general method for eliminating nondeterministic transitions from the self-stabilizing implementation of a large family of behaviors is used to simplify the constructions, and general conditions under which protocol composition preserves behavior are used in proving their correctness.", acknowledgement = ack-nhfb, articleno = "13", keywords = "Anonymous; fairness; finite-state; population protocols; self-stabilization; sensor networks", } @Article{Cao:2008:MEN, author = "Hui Cao and Emre Ertin and Anish Arora", title = "{MiniMax} equilibrium of networked differential games", journal = j-TAAS, volume = "3", number = "4", pages = "14:1--14:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452004", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Surveillance systems based on wireless sensor network technology have been shown to successfully detect, classify and track evaders over a large area. State information collected via the sensor network also enables these systems to actuate mobile agents so as to achieve surveillance goals, such as target capture and asset protection. But satisfying these goals is complicated by the fact that the track information in a sensor network is routed to mobile agents through multihop wireless communication links and is thus subject to message delays and losses. Stabilization must also be considered in designing pursuer strategies so as to deal with state corruption as well as suboptimal evader strategies.\par In this article, we formulate optimal pursuit control strategies in the presence of network effects, assuming that target track information has been established locally in the sensor network. We adapt ideas from the theory of differential games to networked games --- including ones involving nonperiodic track updates, message losses and message delays --- to derive optimal strategies, bounds on the information requirements, and scaling properties of these bounds. We show the inherent stabilization features of our pursuit strategies, both in terms of implementation as well as the strategies themselves.", acknowledgement = ack-nhfb, articleno = "14", keywords = "delay; differential games; equilibrium; sensor networks", } @Article{Cohen:2008:ESS, author = "Johanne Cohen and Anurag Dasgupta and Sukumar Ghosh and S{\'e}bastien Tixeuil", title = "An exercise in selfish stabilization", journal = j-TAAS, volume = "3", number = "4", pages = "15:1--15:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452005", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Stabilizing distributed systems expect all the component processes to run predefined programs that are externally mandated. In Internet scale systems, this is unrealistic, since each process may have selfish interests and motives related to maximizing its own payoff. This article formulates the problem of selfish stabilization to show how competition blends with cooperation in a stabilizing environment.", acknowledgement = ack-nhfb, articleno = "15", keywords = "convergences; equilibrium; selfishness; Stabilization", } @Article{Dieudonne:2008:CFW, author = "Yoann Dieudonn{\'e} and Ouiddad Labbani-Igbida and Franck Petit", title = "Circle formation of weak mobile robots", journal = j-TAAS, volume = "3", number = "4", pages = "16:1--16:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452006", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider distributed systems made of {\em weak mobile\/} robots, that is, mobile devices, equipped with sensors, that are {\em anonymous}, {\em autonomous}, {\em disoriented}, and {\em oblivious}. The {\em Circle Formation Problem\/} (CFP) consists of the design of a protocol insuring that, starting from an initial arbitrary configuration where no two robots are at the same position, all the robots eventually form a {\em regular n-gon\/} --- the robots take place on the circumference of a circle {\em C\/} with equal spacing between any two adjacent robots on {\em C}.\par CFP is known to be unsolvable by arranging the robots evenly along the circumference of a circle {\em C\/} without leaving {\em C\/} --- that is, starting from a configuration where the robots are on the boundary of {\em C}. We circumvent this impossibility result by designing a scheme based on {\em concentric circles}. This is the first scheme that deterministically solves CFP. We present our method with two different implementations working in the semi-synchronous system (SSM) for any number {\em n\/} \geq 5 of robots.", acknowledgement = ack-nhfb, articleno = "16", keywords = "Distributed computing; formation of geometric patterns; mobile robot networks; self-deployment", } @Article{Dolev:2008:SSD, author = "Shlomi Dolev and Reuven Yagel", title = "Self-stabilizing device drivers", journal = j-TAAS, volume = "3", number = "4", pages = "17:1--17:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452007", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "This work presents approaches for designing the input-output device management components of self-stabilizing operating systems. As an example, we demonstrate the nonstability of the ata standard protocol for storage devices. We state the requirements that an operating system and I/O devices should satisfy in order to become self-stabilizing. Then we suggest two solutions to satisfy these requirements. The first uses leases to guarantee progress from the I/O device side. The second assumes stabilization of the I/O device, and uses snapshots to perform consistency checks. A device driver for a PC hard-disk, using the first solution, was implemented. By supplying an infrastructure for practical self-stabilizing systems, robust and dependable systems can be achieved.", acknowledgement = ack-nhfb, articleno = "17", } @Article{Elmallah:2008:LK, author = "Ehab S. Elmallah and Mohamed G. Gouda and Sandeep S. Kulkarni", title = "Logarithmic keying", journal = j-TAAS, volume = "3", number = "4", pages = "18:1--18:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452008", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Consider a communication network where each process needs to securely exchange messages with its neighboring processes. In this network, each sent message is encrypted using one or more symmetric keys that are shared only between two processes: the process that sends the message and the neighboring process that receives the message. A straightforward scheme for assigning symmetric keys to the different processes in such a network is to assign each process {\em O\/} ({\em d\/}) keys, where {\em d\/} is the maximum number of neighbors of any process in the network. In this article, we present a more efficient scheme for assigning symmetric keys to the different processes in a communication network. This scheme, which is referred to as logarithmic keying, assigns {\em O\/} (log {\em d\/}) symmetric keys to each process in the network. We show that logarithmic keying can be used in rich classes of communication networks that include star networks, acyclic networks, limited-cycle networks, planar networks, and dense bipartite networks. In addition, we present a construction that utilizes efficient keying schemes for general bipartite networks to construct efficient keying schemes for general networks.", acknowledgement = ack-nhfb, articleno = "18", keywords = "keying scheme; secure communications; symmetric keys", } @Article{Dastidar:2008:SPP, author = "Kajari Ghosh Dastidar and Ted Herman and Colette Johnen", title = "Safe peer-to-peer self-downloading", journal = j-TAAS, volume = "3", number = "4", pages = "19:1--19:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452009", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "A goal of peer-to-peer applications is to share files between users themselves rather than downloading files from file servers. Self-downloading protocols have the property that, eventually, every user downloads only from other users. Self-downloading is problematic if users disconnect from the system upon completing file downloading, because they only share with other users while connected. Yet, if users continue to arrive at a sufficient rate, self-downloading protocols are possible. One vulnerability of file sharing between users is the possibility that files or segments could be counterfeit or corrupt. Protocols that are {\em d\/} -safe tolerate some number of instances of faulty segments in a file being downloaded, because each segment is downloaded {\em d\/} times before being shared. This article shows that {\em d\/} -safe self-downloading is possible for a sufficiently large arrival rate of users to the system. Upper and lower connectivity and sharing bounds are given for {\em d\/} = 2, and simulation results show effects of relaxing assumptions about arrival rates and bandwidth.", acknowledgement = ack-nhfb, articleno = "19", keywords = "Peer-to-peer distributed systems", } @Article{Guerraoui:2008:GCI, author = "R. Guerraoui and N. Lynch", title = "A general characterization of indulgence", journal = j-TAAS, volume = "3", number = "4", pages = "20:1--20:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452010", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "An indulgent algorithm is a distributed algorithm that, besides tolerating process failures, also tolerates unreliable information about the interleaving of the processes. This article presents a general characterization of indulgence in an abstract computing model that encompasses various communication and resilience schemes. We use our characterization to establish several results about the inherent power and limitations of indulgent algorithms.", acknowledgement = ack-nhfb, articleno = "20", keywords = "agreement; process failures; scheduling failures", } @Article{TAAS-226040010, author = "Article No. 21", title = "Reviewers 2008", journal = j-TAAS, volume = "3", number = "4", pages = "21:1--21:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1452001.1452011", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:25 MDT 2009", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "21", } @Article{Datta:2009:ISI, author = "Ajoy K. Datta", title = "Introduction to special issue on stabilization, safety, and security of distributed systems", journal = j-TAAS, volume = "4", number = "1", pages = "1:1--1:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462188", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "1", } @Article{Ammari:2009:FTM, author = "Habib M. Ammari and Sajal K. Das", title = "Fault tolerance measures for large-scale wireless sensor networks", journal = j-TAAS, volume = "4", number = "1", pages = "2:1--2:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462189", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "{\em Connectivity}, primarily a graph-theoretic concept, helps define the {\em fault tolerance\/} of wireless sensor networks (WSNs) in the sense that it enables the sensors to communicate with each other so their sensed data can reach the sink. On the other hand, {\em sensing coverage}, an intrinsic architectural feature of WSNs plays an important role in meeting application-specific requirements, for example, to reliably extract relevant data about a sensed field. Sensing coverage and network connectivity are not quite orthogonal concepts. In fact, it has been proven that connectivity strongly depends on coverage and hence considerable attention has been paid to establish tighter connection between them although only loose lower bound on network connectivity of WSNs is known. In this article, we investigate connectivity based on the degree of sensing coverage by studying {\em k-covered\/} WSNs, where every location in the field is simultaneously covered (or sensed) by at least {\em k\/} sensors (property known as {\em k-coverage}, where {\em k\/} is the {\em degree of coverage\/}). We observe that to derive network connectivity of {\em k\/} -covered WSNs, it is necessary to compute the sensor spatial density required to guarantee {\em k\/} -coverage. More precisely, we propose to use a model, called the {\em Reuleaux Triangle}, to characterize {\em k\/} -coverage with the help of Helly's Theorem and the analysis of the intersection of sensing disks of {\em k\/} sensors. Using a deterministic approach, we show that the sensor spatial density to guarantee {\em k\/} -coverage of a convex field is proportional to {\em k\/} and inversely proportional to the sensing range of the sensors. We also prove that network connectivity of {\em k\/} -covered WSNs is higher than their sensing coverage {\em k}. Furthermore, we propose a new measure of fault tolerance for {\em k\/} -covered WSNs, called {\em conditional fault tolerance}, based on the concepts of {\em conditional connectivity\/} and {\em forbidden faulty sensor set\/} that includes all the neighbors of a given sensor. We prove that {\em k\/} -covered WSNs can sustain a large number of sensor failures provided that the faulty sensor set does not include a forbidden faulty sensor set.", acknowledgement = ack-nhfb, articleno = "2", keywords = "connectivity; coverage; fault tolerance; k -covered wireless sensor networks", } @Article{Bapat:2009:CRS, author = "S. Bapat and W. Leal and T. Kwon and P. Wei and A. Arora", title = "Chowkidar: Reliable and scalable health monitoring for wireless sensor network testbeds", journal = j-TAAS, volume = "4", number = "1", pages = "3:1--3:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462190", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Wireless sensor network (WSN) testbeds are useful because they provide a way to test applications in an environment that makes it easy to deploy experiments, configure them statically or dynamically, and gather performance information. However, WSNs are typically composed of low-cost devices and tend to be unreliable, with failures a common phenomenon. Accurate knowledge of network health status, including nodes and links of each type, is critical for correctly configuring applications on WSN testbeds and for interpreting the data collected from them.\par In this article we present a stabilizing protocol, Chowkidar, that provides accurate and efficient network health monitoring in WSNs. Our approach adapts the well-known problem of message-passing rooted spanning tree construction and its use in propagation of information with feedback (PIF) for the case of a WSN. The Chowkidar protocol is initiated upon demand; that is, it does not involve ongoing maintenance, and it terminates with accurate results, including detection of failure and restart during the monitoring process. Chowkidar is distinguished from others in two important ways. Given the resource constraints of WSNs, it is message-efficient in that it uses only a few messages per node. Also, it tolerates ongoing node and link failure and node restart, in contrast to requiring that faults stop during convergence.\par We have implemented the Chowkidar protocol as part of enabling a network health status service that is tightly integrated with a remotely accessible wireless sensor network testbed, Kansei, at The Ohio State University. We present experimental results from this testbed that validate the correctness and performance of Chowkidar. We also report on initial experiences and lessons learnt from the integration of Chowkidar with Kansei, including feedback from both testbed users and administrators who have found Chowkidar to be a useful tool for improving the accuracy and efficiency of testbed experimentation and maintenance, and the need for well-defined policies to address issues such as minimizing interference with concurrently running experiments. Finally, we discuss extensions that enhance the functionality and usability of Chowkidar.", acknowledgement = ack-nhfb, articleno = "3", keywords = "health monitoring; PIF; protocol architecture; stabilization; tree protocols; Wireless sensor networks", } @Article{Biely:2009:OMD, author = "Martin Biely and Josef Widder", title = "Optimal message-driven implementations of omega with mute processes", journal = j-TAAS, volume = "4", number = "1", pages = "4:1--4:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462191", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We investigate the complexity of algorithms in message-driven models. In such models, events in the computation can only be caused by message receptions, but not by the passage of time. Hutle and Widder [2005a] have shown that there is no deterministic message-driven self-stabilizing implementation of the eventually strong failure detector and thus \Omega in systems with uncertainty in message delays and channels of unknown capacity using only bounded space. Under stronger assumptions it was shown that even the eventually perfect failure detector can be implemented in message-driven systems consisting of at least {\em f\/} + 2 processes ({\em f\/} being the upper bound on the number of processes that crash during an execution).\par In this article we show that {\em f\/} + 2 is in fact a lower bound in message-driven systems, even if nonstabilizing algorithms are considered. This contrasts time-driven models where {\em f\/} + 1 is sufficient for failure detector implementations.\par Moreover, we investigate algorithms where not all processes send message, that is, are active, but some (in a predetermined set) remain passive. Here, we show that the {\em f\/} + 2 processes required for message-driven systems must be active, while in time-driven systems it suffices that {\em f\/} processes are active.\par We also provide message-driven implementations of \Omega . Our algorithms are efficient in the sense that not all processes have to send messages forever, which is an improvement to previous message-driven failure detector implementations.", acknowledgement = ack-nhfb, articleno = "4", keywords = "Fault tolerance; lower bound; message-driven distributed algorithm; unreliable failure detectors", } @Article{Bonakdarpour:2009:CRR, author = "Borzoo Bonakdarpour and Ali Ebnenasir and Sandeep S. Kulkarni", title = "Complexity results in revising {UNITY} programs", journal = j-TAAS, volume = "4", number = "1", pages = "5:1--5:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462192", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We concentrate on automatic revision of untimed and real-time programs with respect to UNITY properties. The main focus of this article is to identify instances where addition of UNITY properties can be achieved efficiently (in polynomial time) and where the problem of adding UNITY properties is difficult (NP-complete). Regarding efficient revision, we present a sound and complete algorithm that adds a single {\em leads-to\/} property (respectively, {\em bounded-time leads-to\/} property) and a conjunction of {\em unless, stable}, and {\em invariant\/} properties (respectively, {\em bounded-time unless\/} and {\em stable\/}) to an existing untimed (respectively, real-time) UNITY program in polynomial-time in the state space (respectively, region graph) of the given program. Regarding hardness results, we show that (1) while one {\em leads-to\/} (respectively, {\em ensures\/}) property can be added in polynomial-time, the problem of adding two such properties (or any combination of {\em leads-to\/} and {\em ensures\/}) is NP-complete, (2) if maximum non-determinism is desired then the problem of adding even a single {\em leads-to\/} property is NP-complete, and (3) the problem of providing maximum non-determinism while adding a single {\em bounded-time leads-to\/} property to a real-time program is NP-complete (in the size of the program's region graph) even if the original program satisfies the corresponding {\em unbounded leads-to\/} property.", acknowledgement = ack-nhfb, articleno = "5", keywords = "formal methods; UNITY", } @Article{Cournier:2009:LES, author = "Alain Cournier and Stephane Devismes and Vincent Villain", title = "Light enabling snap-stabilization of fundamental protocols", journal = j-TAAS, volume = "4", number = "1", pages = "6:1--6:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462193", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In this article, we show that some fundamental self- and snap-stabilizing wave protocols (e.g., token circulation, {\em PIF}, etc.) implicitly assume a very light property that we call {\em BreakingIn}. We prove that {\em BreakingIn\/} is strictly induced by self- and snap-stabilization. Combined with a transformer, {\em BreakingIn\/} allows to easily turn the non-fault-tolerant versions of those protocols into snap-stabilizing versions. Unlike the previous solutions, the transformed protocols are very efficient and work at least with the same daemon as the initial versions extended to satisfy {\em BreakingIn}. Finally, we show how to use an additional property of the transformer to design snap-stabilizing extensions of those fundamental protocols like Mutual Exclusion.", acknowledgement = ack-nhfb, articleno = "6", keywords = "Self- and snap-stabilization; transformer; wave protocols", } @Article{Danturi:2009:SSP, author = "Praveen Danturi and Mikhail Nesterenko and S{\'e}bastien Tixeuil", title = "Self-stabilizing philosophers with generic conflicts", journal = j-TAAS, volume = "4", number = "1", pages = "7:1--7:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462194", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We generalize the classic dining philosophers problem to separate the conflict and communication neighbors of each process. Communication neighbors may directly exchange information while conflict neighbors compete for the access to the exclusive critical section of code. This generalization is motivated by a number of practical problems in distributed systems including problems in wireless sensor networks. We present a self-stabilizing deterministic algorithm --- {\em GDP\/} that solves this generalized problem. Our algorithm is terminating. We formally prove {\em GDP\/} correct and evaluate its performance. We extend the algorithm to handle a similarly generalized drinking philosophers and the committee coordination problem. We describe how {\em GDP\/} can be implemented in wireless sensor networks and demonstrate that this implementation does not jeopardize its correctness or termination properties.", acknowledgement = ack-nhfb, articleno = "7", keywords = "dining philosophers; self-stabilization", } @Article{Masuzawa:2009:BTK, author = "Toshimitsu Masuzawa and S{\'e}bastien Tixeuil", title = "On bootstrapping topology knowledge in anonymous networks", journal = j-TAAS, volume = "4", number = "1", pages = "8:1--8:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462195", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In this article, we quantify the amount of ``practical'' information (i.e., views obtained from the neighbors, colors attributed to the nodes and links) to obtain ``theoretical'' information (i.e., the local topology of the network up to distance {\em k\/}) in anonymous networks. In more detail, we show that a coloring at distance 2 {\em k\/} + 1 is necessary and sufficient to obtain the local topology at distance {\em k\/} that includes outgoing links. This bound drops to 2 {\em k\/} when outgoing links are not needed. A second contribution of this article deals with color bootstrapping (from which local topology can be obtained using the aforementioned mechanisms). On the negative side, we show that ({\em i\/}) with a distributed daemon, it is impossible to achieve deterministic color bootstrap, even if the whole network topology can be instantaneously obtained, and ({\em ii\/}) with a central daemon, it is impossible to achieve distance {\em m\/} when instantaneous topology knowledge is limited to {\em m\/} - 1. On the positive side, we show that ({\em i\/}) under the {\em k\/} -central daemon, deterministic self-stabilizing bootstrap of colors up to distance {\em k\/} is possible provided that {\em k\/} -local topology can be instantaneously obtained, and ({\em ii\/}) under the distributed daemon, probabilistic self-stabilizing bootstrap is possible for any range.", acknowledgement = ack-nhfb, articleno = "8", keywords = "anonymous networks; daemon; stabilization; topology", } @Article{Souissi:2009:UEC, author = "Samia Souissi and Xavier D{\'e}fago and Masafumi Yamashita", title = "Using eventually consistent compasses to gather memory-less mobile robots with limited visibility", journal = j-TAAS, volume = "4", number = "1", pages = "9:1--9:??", month = jan, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1462187.1462196", ISSN = "1556-4665", bibdate = "Fri Apr 24 17:35:49 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Reaching agreement among a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some location not determined in advance, and without the help of some global coordinate system. While very simple to express, this problem has the advantage of retaining the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In previous works, it has been proved that the gathering problem is solvable in asynchronous model with oblivious (i.e., memory-less) robots and limited visibility, as long as the robots share the knowledge of some direction, as provided by a compass. However, the problem has no solution in the semi-synchronous model when robots do not share a compass, or when they cannot detect multiplicity.\par In this article, we define a model in which compasses may be unreliable, and study the solvability of gathering oblivious mobile robots with limited visibility in the semi-synchronous model. In particular, we give an algorithm that solves the problem in finite time in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually. In addition, we show that our algorithm solves the gathering problem for at most three robots in the asynchronous model. Our algorithm is intrinsically self-stabilizing.", acknowledgement = ack-nhfb, articleno = "9", keywords = "autonomous mobile robots; cooperation and control; point formation; self-organizing robots; self-stabilization; unreliable compasses", }