SICS, Box 1263, S-164 29 Kista, SWEDEN
This is an abstracts listing of Technical and Research reports from SICS.
Magnus Sahlgren, Ola Knutsson
This is a collection of papers presented at the Nodalida 2009 workshop on extracting and using constructions in NLP.
Oscar Täckström
Subjective language is used to express attitudes and opinions towards things, ideas and people. While content and topic centred natural language processing is now part of everyday life, analysis of subjective aspects of natural language have until recently been largely neglected by the research community. The explosive growth of personal blogs, consumer opinion sites and social network applications in the last years, have however created increased interest in subjective language analysis. This paper provides an overview of recent research conducted in the area.
Rebecca Steinert, Daniel Gillblad
We present a distributed adaptive fault-handling algorithm applied in networked systems. The probabilistic approach that we use makes the proposed method capable of adaptively detect and localize network faults by the use of simple end-to-end test transactions. Our method operates in a fully distributed manner, such that each network element detects faults using locally extracted information as input. This allows for a fast autonomous adaption to local network conditions in real-time, with significantly reduced need for manual configuration of algorithm parameters. Initial results from a small synthetically generated network indicate that satisfactory algorithm performance can be achieved, with respect to the number of detected and localized faults, detection time and false alarm rate.
Fredrik Olsson
Active learning is a supervised machine learning technique in which the learner is in control of the data used for learning. That control is utilized by the learner to ask an oracle, typically a human with extensive knowledge of the domain at hand, about the classes of the instances for which the model learned so far makes unreliable predictions. The active learning process takes as input a set of labeled examples, as well as a larger set of unlabeled examples, and produces a classifier and a relatively small set of newly labeled data. The overall goal is to create as good a classifier as possible, without having to mark-up and supply the learner with more data than necessary. The learning process aims at keeping the human annotation effort to a minimum, only asking for advice where the training utility of the result of such a query is high. Active learning has been successfully applied to a number of natural language processing tasks, such as, information extraction, named entity recognition, text categorization, part-of-speech tagging, parsing, and word sense disambiguation. This report is a literature survey of active learning from the perspective of natural language processing.
Stina Nylander, Bo Karlson
A microcommunity for preschool is a community for parents, teachers and other people involved in a preschool child group. The community is a tool for distributing and exchanging information and complements the traditional face to face communication and paper notes in that it makes information available from other places than the home and the preschool facilities. We present a first design iteration for preschool microcommunities with parents and teachers. Teachers have worked with a prototype tool to create microcommunities that has been made available to parents. We present a set of design principles for preschool microcommunities and a new design of the tool.
Malin Forsgren, Martin Aronsson, Per Kreuger
Idag konfliktregleras tågtrafiken i Sverige på sekundnivå redan i tidtabelläggningsfasen då operatörernas ansökningar har kommit in till Banverket, trots hög osäkerhet i planeringsunderlaget. Den här rapporten beskriver en tidtabelläggningsprocess där den detaljerade planeringen skjuts upp tills mer tillförlitliga fakta finns att tillgå. För den tidiga fasen föreslås i stället en mer översiktlig -- grov -- planering, vilken huvudsakligen mynnar ut i ett antal ankomster och avgångar som Banverket åtar sig att leverera punktligt till operatörerna. Poängen är att Banverket på så vis kan skjuta på besluten angående det som ska hända mellan åtagandepunkterna, och vi presenterar en konkret metod för hur detaljeringen som följer på den grova planeringen kan gå till. Metoden producerar en plan med en detaljeringsnivå som i stort överensstämmer med den i Banverkets tidtabelläggningssystem TrainPlan.
Nicolas Beldiceanu, Mats Carlsson, Julien Martin
It is well known that real-life applications rarely admit a constraint model expressed purely in terms of a few global constraints. Usually, the global constraints capture a relaxed form of the problem, but needs additional side-constraints to capture the full problem. Handling such side-constraints inside the global constraints, as opposed to in conjunction with it, improves propagation. Historically, this has been done by extending the global constraints with a host of specific options, each connected to a specific filtering method. Being able to express and filter side-constraints in a more uniform and systematic way would seem a more elegant and manageable solution. This report presents such a mechanism for the global non-overlapping constraint "geost", which handles the location in space of k-dimensional objects. Side-constraints are expressed as rules written in a language based on arithmetic and first-order logic, which should hold among the objects. We explain in detail the way the rules are compiled into a form that is accessed by the constraint's sweep-based filtering algorithm. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are transformed to generators of k-dimensional forbidden sets. Thirdly, the generators are transformed to procedures answering queries about candidate coordinate points for a given object. Such queries are at the heart of the filtering algorithm. The business rules allow to express a great variety of packing and placement constraints, while admitting effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures. The constraint was used to directly encode the packing knowledge of a major car manufacturer, and was evaluated on several benchmarks.
Magnus Ågren, Nicolas Beldiceanu, Mats Carlsson, Mohamed Sbihi, Charlotte Truchet, Stéphane Zampelli
This report introduces six ways for handling a chain of lexicographic ordering constraint between the origins of identical orthotopes (e.g., rectangles, boxes, hyper-rectangles) subject to the fact that they should not pairwise overlap. While the first two ways deal with the integration of a chain of lexicographic ordering constraint within a generic geometric constraint kernel, the four latter ways deal with the conjunction of a chain of lexicographic ordering constraint and a non-overlapping or a cumulative constraint. Experiments on academic two and three dimensional placement problems as well as on industrial problems show the benefit of such a strong integration of symmetry breaking constraints and non-overlapping ones.
Stina Nylander
We have interviewed four parents and a teacher at a Swedish preschool to investigate the practices for spreading information in preschool. Our findings suggest that frequent presence in the premises of the preschool is important to get information, and that parents rely heavily on routines to make it work. When either of these points fail, breakdowns occur. Discrepancies in parents’ and teachers’ IT use also complicates the information exchange.
Simon Schütz , Henrik Abrahamsson, Bengt Ahlgren , Marcus Brunner
The Internet Protocol (IP) has been proven very flexible, being able to accommodate all kinds of link technologies and supporting a broad range of applications. The basic principles of the original Internet architecture include end-to-end addressing, global routeability and a single namespace of IP addresses that unintentionally serves both as locators and host identifiers. The commercial success and widespread use of the Internet have lead to new requirements, which include internetworking over business boundaries, mobility and multi-homing in an untrusted environment. Our approach to satisfy these new requirements is to introduce a new internetworking layer, the node identity layer. Such a layer runs on top of the different versions of IP, but could also run directly on top of other kinds of network technologies, such as MPLS and 2G/3G PDP contexts. This approach enables connectivity across different communication technologies, supports mobility, multi-homing, and security from ground up. This paper describes the Node Identity Architecture in detail and discusses the experiences from implementing and running a prototype.
Fredrik Holmgren, Sverker Janson
We report on a first study of interactive visual analysis of networked systems. Working with ABB Corporate Research and Ericsson Research, we have created workflows which demonstrate the potential of visualization in the domains of industrial automation and telecommunications. By a workflow in this context, we mean a sequence of visualizations and the actions for generating them. Visualizations can be any images that represent properties of the data sets analyzed, and actions typically either change the selection of data visualized or change the visualization by choice of technique or change of parameters.
Maria Sjölinder, Åsa Rudström
This work is part of the On-demand IPTV project, conducted by Acreo and SICS with financing from Vinnova and active support from an industrial consortium. The main goal of the project is to study the demands on cost-effective, scalable video-on-demand networks that can deliver video with high-quality with minor quality degradations in the transmission. An important issue in understanding this situation is to explore future user behaviour (and the resulting traffic patterns) when user can choose a mix of broadcast TV and a large number of on-demand channels and services. This paper reports on the first steps to develop an understanding of IPTV user behaviour by investigating the current situation using archetypical, fictional character descriptions often referred to as personas. This is an intermediate version; the final version will be the result of Task 4.1: User requirements analysis, part of WP 4: User needs and behaviour.
Ludwig Seitz, Erik Rissanen
The XACML standard defines an XML based language for defining access control policies and a related processing model. Recent work aims to add delegation to XACML in order to express the right to administrate XACML policies within XACML itself. The delegation profile draft explains how to validate the right to issue a policy, but there are no provisions for removing a policy. This paper proposes a revocation model for delegated XACML. A novel feature of this model is that whether a revocation is valid or not, depends not only on who issued the revocation, but also on the context in which an attempt to use the revoked policy is done.
Per Kreuger
We report results on a maintenance scheduling problem. The problem consists of allocating maintenance task instances to and scheduling the performances of a suitable number of maintenance packages. The number of maintenance packages is not fixed, nor is, in general, the dates or durations of their performances. A constraint programming (CP) model and solver for the problem is presented together with preliminary computational results.
Karl-Filip Faxén
In this report we sketch a polymorphic type and effect inference system for ensuring deterministic execution of parallel programs containing shared mutable state. It differs from that of Gifford and Lucassen in being based on Hindley Milner polymorphism and in formalizing the operational semantics of parallel and sequential computation.
Karl-Filip Faxén
In this paper we deal with the problem of making context dependent interprocedural optimizations (where the legality of optimizing a function depends on properties of the callers of the function) effective and compatible with (a form of) separate compilation. We improve effectiveness by cloning, generating several versions of a single function optimized for different call sites. We attack the separate compilation problem, that code can not be generated until all calls of a function are known, by splitting the compilation process into two phases. The first phase analyses the modules one at a time in bottom-up dependency order ('main' is processed last) and produces code in an intermediate language where the constructs targeted by the optimization are annotated to control the application of the optimization. In cases where the legality of an optimization depends on properties of the callers of the function, these annotations can take the form of annotation variables which become extra formal parameters. The second phase traverses the modules in top-down dependency order, removing all of these extra parameters by specialization. We illustrate our approach with an integrated programming analysis and transformation system featuring a context sensitive type based analysis, cloning with sharing of identical clones and a modular implementation allowing for the compilation of large programs. The system implements cheap eagerness and redundant eval elimination for a lazy functional language.
Ludwig Seitz, Erik Rissanen
The NETCONF remote network configuration protocol currently lacks an access control model. The need for such a model has been recognised within the NETCONF working group. The eXtended Access Control Markup Language (XACML) is an XML-based access control standard, with widespread acceptance from the industry and good open-source support. This document proposes a profile that defines how to use XACML to provide fine-grain access control for NETCONF commands.
Fredrik Österlind, Adam Dunkels
Recent work in sensor network energy optimization has shown that batch-and-send networks can significantly reduce network energy consumption. Batch-and-send networks rely on effective batch data transport protocols, but the throughput of state-of-the-art protocols is low. We present conditional immediate transmission, a novel packet forwarding mechanism, with which we achieve a 109 kbit/s raw data throughput over a 6-hop multi-channel 250 kbit/s 802.15.4 network; 97% of the theoretical upper bound. We show that packet copying is the bottleneck in high-throughput packet forwarding and that by moving packet copying off the critical path, we nearly double the end-to-end throughput. Our results can be seen as an upper bound on the achievable throughput over a single-route, multi-channel, multi-hop 802.15.4 network. While it might be possible to slightly improve our performance, we are sufficiently close to the theoretical upper bound for such work to be of limited value. Rather, our results suggests that other mechanisms, such as multi-route forwarding, may be fruitful way to further improve multi-hop throughput.
Mats Carlsson, Nicolas Beldiceanu, Julien Martin
This report presents a global constraint that enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are compiled to generators of k-dimensional forbidden sets. Such generators are a generalization of the indexicals of cc(FD). Finally, the forbidden sets generated by such indexicals are aggregated by a sweep-based algorithm and used for filtering. The business rules allow to express a great variety of packing and placement constraints, while admitting efficient and effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures. The constraint was used to directly encode the packing knowledge of a major car manufacturer and tested on a set of real packing problems under these rules, as well as on a packing-unpacking problem.
Markus Bohlin, Malin Forsgren
Rapporten beskriver ett antal provkörningar av TIMM-demonstratorn utförda för att undersöka hur antalet besök i verkstaden varierar givet en förväntad underhållsvinst från CBM. TIMM-demonstratorn är en programvara framtagen för att under drift planera in underhållsbesök för ett antal simulerade fordon i spårtrafik, där underhållsbehovet styrs av dynamiskt varierande mätvärden på fordonen.
Jan Ekman, Anders Holst
This report concerns the "ISC-tool", a tool for classification of patterns and detection of anomalous patterns, where a pattern is a set of values. The tool has a graphical user interface "the anomalo-meter" that shows the degree of anomaly of a pattern and how it is classified. The report describes the user interaction with the tool and the underlying statistical methods used, which basically are Bayesian inference for finding expected or "predictive" distributions for clusters of patterns and using these distributions for classifying and assessing a degree of anomaly to a new pattern. The report also briefly discusses what in general are appropriate methods for clustering and anomaly detection. The project has been supported by SSF via the Butler2 programme.
Zhitao He
Sensornet Protocol (SP) is a link abstraction layer between the network layer and the link layer for sensor networks. SP was proposed as the core of a future-oriented sensor node architecture that allows flexible and optimized combination between multiple coexisting protocols. This thesis implements the SP sensornet protocol on the Contiki operating system in order to: evaluate the effectiveness of the original SP services; explore further requirements and implementation trade-offs uncovered by the original proposal. We analyze the original SP design and the TinyOS implementation of SP to design the Contiki port. We implement the data sending and receiving part of SP using Contiki processes, and the neighbor management part as a group of global routines. The evaluation consists of a single-hop traffic throughput test and a multihop convergecast test. Both tests are conducted using both simulation and experimentation. We conclude from the evaluation results that SP's link-level abstraction effectively improves modularity in protocol construction without sacrificing performance, and our SP implementation on Contiki lays a good foundation for future protocol innovations in wireless sensor networks.
Nicolas Tsiftes
Software used in sensor networks to perform tasks such as sensing, network routing, and operating system services can be subject to changes or replacements during the long lifetimes of many sensor networks. The task of reprogramming the network nodes consumes a significant amount of energy and increases the network congestion because the software is sent over radio in an epidemic manner to all the nodes. In this thesis, I show that the use of data compression of dynamically linkable modules makes the reprogramming more energy-efficient and reduces the time needed for the software to propagate. The cost for using data compression is that the decompression algorithm must execute for a relatively long time, and that the software takes five to ten kilobytes to store on the sensor nodes.
Ali Ghodsi, Seif Haridi
We present Forestcast which is a flexible and centralized solution to building a forest of trees, which are used to stream live media. A number of heuristic strategies are described to handle joins. Leaves are handled through rejoins. To enable fail-overs, we describe a scheme where the server gives each peer a backup parent such that it is guaranteed that the failure of any peer can be handled. We also describe how the scheme can be efficiently coupled with multiple stripes to allow for better bandwidth utilization. Finally, it is shown how the centralized solution can be decentralized. The provided scheme has three main advantages. i) It is difficult for peers to hack ForestCast as all decisions are taken by the central server. A peer just follows the server's orders about where it should download its stream. It is also possible to use a PKI scheme, where a peer can verify whether it should give its stream to another peer. ii) As the server has complete information about the state of all trees, it can optimize the number and shape of trees based on any metric, e.g. total latency, bandwidth utilization, robustness against failures etc. iii) The client software, running on the peers, contains little intelligence. Hence, it will be simple and can therefore be adapted for various OS and environments. Furthermore, most updates will be to the server infrastructure. A decentralized solution would need software updates to be applied to all peers.
Kristofer Franzén, Daniel Oppenheimer
The FetchProt Corpus has been built within the FetchProt project in order to work as training and test data for the FetchProt system.
Cosmin Arad, Ozair Kafray, Ali Ghodsi, Seif Haridi
We propose GODS, an ecosystem for the evaluation and study of world-wide distributed and dynamic systems under a realistic emulated network environment. GODS allows the evaluation of a system's actual implementation in reproducible experiments, collecting global knowledge about the system state. Furthermore, GODS addresses the problems of debugging distributed algorithms, performance tuning, measuring bandwidth consumption, regression testing, and benchmarking similar systems, thus offering a complete evaluation environment for distributed applications. Our framework uses ModelNet for the network emulation and enhances that by (1) adding dynamism by varying link properties, partitioning the network and emulating churn, (2) offering global knowledge about the observed system by gathering statistics and events and (3) enabling the user to easily deploy, manage and monitor complex, large-scale distributed systems.
Niclas Finne, Joakim Eriksson, Adam Dunkels, Thiemo Voigt
Various experiments have shown that the performance of wireless sensor networks is very hard to predict. It is also acknowledged that deploying sensor networks in real settings is a difficult and tedious task. To contribute to the understanding of wireless sensor network behavior we report on our experience from two recently deployed sensor networks: one in-door surveillance network in a factory complex and a combined out-door and in-door surveillance network. Both networks use advanced sensor network technology such as ad hoc routing and multi hop networking. Our results highlight the need for self-configuration in wireless sensor networks, especially in cases where fast deployment and dynamic environments are important aspects.
Nicolas Beldiceanu, Emmanuel Poder, Rida Sadek, Mats Carlsson, Charlotte Truchet
This report introduces a geometrical constraint kernel for handling the location in space and time of polymorphic k-dimensional objects subject to various geometrical and time constraints. The constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. These constraints are handled globally by the kernel. We first illustrate how to model several placement problems with the constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.
Magnus Boman, Fredrik Espinoza, Kristofer Franzén , Preben Hansen, Markus Bylund, Martin Svensson
Vi har granskat förutsättningarna och möjligheterna att implementera Human Grid: en så kallad mellanprogramvara för att integrera samarbetsfrämjande IT-lösningar som redan idag finns i datorer och telefoner, med hänsyn tagen till formella och informella sociala nätverk.
Magnus Sahlgren, Ola Knutsson
This is the proceedings of the Workshop on Semantic Content Acquisition and Representation, held in conjunction with NODALIDA 2007, on May 24 2007 in Tartu, Estonia.
Ali Ghodsi, Seif Haridi
This paper provides algorithms to maintain a ring-structure for structured peer-to-peer systems. The algorithms guarantee consistent lookup results in the presence of joins and leaves, regardless of at which node the lookup is initiated. Every join and leave event appears as if it happened atomically, thus guaranteeing that lookup results will be the same as if no joins or leaves took place. The ring maintenance algorithms guarantee that no routing failures occur as nodes are joining and leaving. We also show that lookup consistency is impossible to provide given failure detector, and show how the algorithms can be extended to handle failures. The correctness of all the provided algorithms is proven. Previous approaches to this problem either assume a fault-free environment, or have no proof of correctness.
Fredrik Österlind, Erik Pramsten, Daniel Roberthson, Joakim Eriksson, Niclas Finne, Thiemo Voigt
Building automation systems (BAS) are used to control and improve indoor building climate at reduced costs. By integrating BAS with wireless sensor networks, the need for cabling can be removed, and both installation and operational costs significantly reduced. Furthermore, temporary BAS installations are made possible. By implementing and evaluating the open BAS standard BACnet on the ESB nodes we show that using existing standard BAS protocols is possible on resource-constrained sensor nodes.
Martin Aronsson, Markus Bohlin, Per Kreuger
This paper introduces two MILP models for the cumulative scheduling constraint and associated pre-processing filters. We compare standard solver performance for these models on three sets of problems and for two of them, where tasks have unitary resource consumption, we also compare them with two models based on a geometric placement constraint. In the experiments, the solver performance of one of the cumulative models, is clearly the best and is also shown to scale very well for a large scale industrial transportation scheduling problem.
Lars Albertsson
Testing is the predominant software quality assurance method today, but it has a major flaw --- it cannot reliably catch race conditions, intermittent errors caused by factors that cannot be controlled during testing, such as unpredictable timing behaviour in concurrent software. We present entropy injection, a extension of traditional test methods, which enable developers to create tests for arbitrary types of race conditions in any software application, reusing the application's existing test cases. An entropy injector runs the software under test in an instruction set simulator, where all factors that normally are unpredictable can be explicitly controlled. The injector provokes race condition defects by artificially changing the timing behaviour of the simulated processors, hardware devices, clocks, and input models. Provoked defects can be debugged by developers in a non-intrusive, programmable debugger, which allows race condition defects to be reproduced and provides access to all software state in a distributed system. Developers can use its services to create application-specific injection strategies and directed regression test cases that monitor application state and test specific interleavings of events. Our proof-of-concept entropy injector implementation Njord is built on Nornir, a debugger environment based on the complete system simulator Simics. Njord provokes test case failures by suspending simulated processors, thereby injecting delays in the processes in a concurrent application. We demonstrate Njord on a small test routine, and show how a developer can write a race condition regression test that triggers errors with very high probability, or provoke errors with good probability without using application knowledge.
Supriya Krishnamurthy, Sameh El-Ansary, Erik Aurell, Seif Haridi
In this paper, we present an analytical tool for understanding the performance of structured overlay networks under churn based on the master-equation approach of physics. We motivate and derive an equation for the average number of hops taken by lookups during churn, for the Chord network. We analyse this equation in detail to understand the behaviour with and without churn. We then use this understanding to predict how lookups will scale for varying peer population as well as varying the sizes of the routing tables. We also consider a change in the maintenance algorithm of the overlay, from periodic stabilisation to a reactive one which corrects fingers only when a change is detected. We generalise our earlier analysis to understand how the reactive strategy compares with the periodic one.
Stina Nylander
Multi-device services need to be adapted to various devices to accommodate users. When deciding how to adapt a multi-device service, several parameters such as device capabilities, usage context, purpose of use, and usability need to be considered. Here, these parameters are discussed and based on the discussion basic design guidelines for multi-device services are presented.
Stina Nylander
We have conducted interviews with 22 users of three multi-device services, email and two web communities, to explore practices, benefits, and problems with using services both from desktop computers and mobile devices. Participants reported different usage patterns on different devices, offering support for adapting services to the capabilities of devices. The most common usage problems reported concerned text input and navigation on mobile devices, and data organization over multiple devices.
Daniel Gillblad, Anders Holst, Rebecca Steinert
In many diagnosis situations it is desirable to perform a classification in an iterative and interactive manner. All relevant information may not be available initially and must be acquired manually or at a cost. The matter is often complicated by very limited amounts of knowledge and examples when a new system to be diagnosed is initially brought into use. Here, we will describe how to create an incremental classification system based on a statistical model that is trained from empirical data, and show how the limited available background information can still be used initially for a functioning diagnosis system.
Magnus Boman, Jarmo Laaksolahti, Fredrik Espinoza, Rickard Cöster
Report produced in the project Enabling and Promoting Trust in Micro Service Environments (EPTMSE) with a web site at www.trust-eze.org. The report gives an overview of the concept of trust in domains such as psychology, sociology, philosophy, and computer science, and then describes the current domain of Micro Service Environments - open and unregulated electronic service environments - where users can create, use, and share electronic services, and where the need for decentralized trust mechanisms is high. Some design and implementation choices and solutions for trust mechanisms are suggested.
Adam Dunkels
With sensor networks starting to get mainstream acceptance, programmability is of increasing importance. Customers and field engineers will need to reprogram existing deployments and software developers will need to test and debug software in network testbeds. Script languages, which are a popular mechanism for reprogramming in general-purpose computing, have not been considered for wireless sensor networks because of the perceived overhead of interpreting a script language on tiny sensor nodes. In this paper we show that a structured script language is both feasible and efficient for programming tiny sensor nodes. We present a structured script language, SCript, and develop an interpreter for the language. To reduce program distribution energy the SCript interpreter stores a tokenized representation of the scripts which is distributed through the wireless network. The ROM and RAM footprint of the interpreter is similar to that of existing virtual machines for sensor networks. We show that the interpretation overhead of our language is on par with that of existing virtual machines. Thus script languages, previously considered as too expensive for tiny sensor nodes, are a viable alternative to virtual machines.
Lars Albertsson
We present holistic debugging, a novel method for observing execution of complex and distributed software. It builds on an instruction set simulator, which provides reproducible experiments and non-intrusive probing of state in a distributed system. Instruction set simulators, however, provide low-level information, so a holistic debugger contains a translation framework that maps this information to higher abstraction level observation tools, such as source code debuggers. We have created Nornir, a proof-of-concept holistic debugger, built on the simulator Simics. For each observed process in the simulated system, Nornir creates an abstraction translation stack, with virtual machine translators that map machine-level storage contents (e.g. physical memory, registers) provided by Simics, to application-level data (e.g. virtual memory contents) by parsing the data structures of operating systems and virtual machines. Nornir includes a modified version of the GNU debugger (GDB), which supports non-intrusive symbolic debugging of distributed applications. Nornir's main interface is a debugger shepherd, a programmable interface that controls multiple debuggers, and allows users to coherently inspect the entire state of heterogeneous, distributed applications. It provides a robust observation platform for construction of new observation tools.
Sebastian Brand, Roland H.C. Yap
Constraint propagation algorithms implement logical inference. For efficiency, it is essential to control whether and in what order basic inference steps are taken. We provide a high-level framework that clearly differentiates between information needed for controlling propagation versus that needed for the logical semantics of complex constraints composed from primitive ones. We argue for the appropriateness of our controlled propagation framework by showing that it captures the underlying principles of manually designed propagation algorithms, such as literal watching for unit clause propagation and the lexicographic ordering constraint. We provide an implementation and benchmark results that demonstrate the practicality and efficiency of our framework.
Kenil C. K. Cheng, Roland H. C. Yap
Binary decision diagrams (BDDs) can compactly represent ad-hoc n-ary Boolean constraints. However, there is no generalized arc consistency (GAC) algorithm which exploit BDDs. For example, the global case constraint by SICStus Prolog for ad-hoc constraints is designed for non-Boolean domains. In this paper, we introduce a new GAC algorithm, bddc, for BDD constraints. Our empirical results demonstrate the advantages of a new BDD-based global constraint -- bddc is more efficient both in terms of memory and time than the case constraint when dealing with ad-hoc Boolean constraints. This becomes important as the size of the ad-hoc constraints becomes large.
Steven Halim, Roland H.C. Yap, Hoong Chuin Lau
Metaheuristic search algorithms due to their heuristic nature usually need tuning of parameters, components and/or strategies to achieve acceptable performance on a particular problem. While there has been much work on tools and techniques to address this Tuning Problem, there has been relatively little work which takes advantage of putting humans in the metaheuristic analysis/evaluation loop. This paper proposes the use of a search trajectory visualization tool, Viz, which is meant to make it easier for humans (e.g. the algorithm designer/programmer) to understand, evaluate and design metaheuristics for search. In particular, our visualization exploits the human's capabilities for finding patterns in search trajectory by using a combination of spatial visualizations. We use the Travelling Salesman Problem to illustrate how Viz can be used to visualize the behavior of two local search algorithms with different heuristics.
Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Thierry Petit
This report presents a generic filtering scheme, based on the graph description of global constraints. This description is defined by a network of binary constraints and a list of elementary graph properties: each solution of the global constraint corresponds to a subgraph of the initial network, retaining only the satisfied binary constraints, and which fulfills all the graph properties. The graph-based filtering identifies the arcs of the network that belong or not to the solution subgraphs. The objective is to build, besides a catalog of global constraints, also a list of systematic filtering rules based on a limited set of graph properties. We illustrate this principle on some common graph properties and provide computational experiments of the effective filtering on the "group" constraint.
Birgir Stefansson , Antonios Thodis, Ali Ghodsi, Seif Haridi
Traditional backup methods are error prone, cumbersome and expensive. Distributed backup applications have emerged as promising tools able to avoid these disadvantages, by exploiting unused disk space of remote computers. In this paper we propose MyriadStore, a distributed peer-to-peer backup system. MyriadStore makes use of a trading scheme that ensures that a user has as much available storage space in the system as the one he/she contributes to it. A mechanism for making challenges between the system's nodes ensures that this restriction is fulfilled. Furthermore, MyriadStore minimizes bandwidth requirements and migration costs by treating separately the storage of the system's meta-data and the storage of the backed up data. This approach also offers great flexibility on the placement of the backed up data, a property that facilitates the deployment of the trading scheme.
Markus Bohlin, Per Kreuger, Martin Aronsson, Malin Forsgren
Rapporten beskriver möjliga ansatser för att lösa det abstraherade tidtabellproblemet som bl.a. diskuteras i rapporten "Leveranstågplan: Specifikation och åtagande" (DDTP Arbetsdokument SICS-DDTP-002). Till grund för de olika ansatserna ligger en modell med avgångstider och hålltider (dvs. väntetider och i viss mån traverseringstider) som tillåts variera inom vissa tidsintervall. Huvudidén är att arbeta med förenklade kapacitetsvillkor på bana och bangård, för att på ett effektivt sätt kunna beräkna tidtabeller på en nivå som tillåter anpassning av tidtabellen till det gällande transportbehovet och den rådande trafiksituationen.
Martin Aronsson
Denna rapport sammanfattar arbetet i projektet TUFF, TågplaneUtveckling För Framtiden, finansierat av Banverkets FoU-program. Projektet har pågått under åren 2004 och 2005, och syftet med projektet har varit att studera beräkningsmodeller och beräkningsaspekter för tågplanekonstruktion. Rapporten presenterar en beräkningsmodell för tågplanekonstruktion som skalar väl upp till storleken på konstruktionsområden som används idag och är således lämplig att basera ett stödsystem åt tidtabellkonstruktörer på. Rapporten beskriver den operationsalanytiska modellen samt sammanfattar de tester som utförts. Utöver detta presenteras en del förslag och ansatser till nyckeltal att mäta tågplaners egenskaper.
Bilge Cetin
In IEEE802.11,it is the general case that the further away the stations from the access point (AP), the slower the data rate is to transmit to the AP. With the existing IEEE 802.11 MAC, in the long run all stations end up with the same amount of throughput, no matter if they transmit slow or fast. When one host captures the channel for a long time because its bit rate is low, it penalizes other hosts that use the higher rate. As a solution, a novel MAC layer relay protocol, Opportunistic Relay Protocol (ORP) is proposed, to improve the performance of IEEE 802.11. The ORP suggests two hops technique to enable slow transmitting stations to speed up their transmission rates. The simplest explanation is: A single 2 Mbps transmission path is replaced with two 11 Mbps transmissions where an intermediate node is used as a relayer. This way relay protocol offers 5.5 Mbps (ignoring overhead) effective bitrate instead of 2 Mbps. In this thesis, ORP was formalized and analyzed through theoretical work and implemented within a simulation environment to evaluate the performance improvement that ORP offers. It is showed that with ORP, the overall throughput of the BSS improves up to %25. Moreover, ORP inserts negligible amount of overhead to the system while maintaining backward compatibility with IEEE 802.11.
Fredrik Österlind
This report introduces a new sensor network simulator for the Contiki OS - the COOJA Simulator. The Contiki OS is a portable operating system designed specifically for resource limited devices such as sensor nodes. It is built around an event-driven kernel but supports pre-emptive multithreading at a per-process basis. It also supports a full TCP/IP stack via uIP and the programming abstraction Protothreads. The main design goal of the COOJA Simulator is extendibility, for which Interfaces and Plugins are used. An Interface represents a sensor node property or device, such as a position, a button or a radio transmitter. A Plugin is used to interact with a simulation, for example to control the simulation speed or to watch all network traffic between the simulated nodes. Both new Plugins and Interfaces can easily be created and added to the simulation environment. A number of other parts of the simulator, for example a radio medium responsible for forwarding radio network data, can also be implemented and added to the simulator. And by supporting several different simulation environments at the same time in one simulation, different underlying hardware platforms can be simulated in heterogeneous networks. Java Native Interface is used to connect the new simulator with Contiki, allowing simulated applications to run in a real Contiki system. By using this approach, any simulated application can then be run on a real sensor node unaltered.
Anders Holst, Jan Ekman, Stefan Larsen
I Reginatågen genereras signaler om såväl s.k. "events" (meddelanden om både rutinhändelser och mer eller mindre allvarliga fel i olika enheter) som "condition" (driftsräknare för olika enheter). Det är önskvärt att övervaka båda dessa typer av signaler för att upptäcka avvikelser som kraftigt förändrad frekvens eller driftsintensitet. Sådana avvikelser skulle kunna signalera olika servicebehov, och det skulle alltså vara till användning om servicepersonal fick reda på dem i god tid innan de lett till allvarligare fel. Vi kommer här att gå igenom en grundläggande och generellt användbar statistisk modell för detta scenario. Metoden utvärderas på autentiska data från Reginatågen.
Jan Ekman, Anders Holst, Martin Aronsson, Markus Bohlin, Malin Forsgren, Stefan Larsen
TIME står för Train Information Management Environment. TIME är ett tänkt övergripande informationssystem för Järnväg. Viktiga aspekter hos TIME är utformningen av en plattform för kommunikation mellan aktörerna i järnvägstransportbranschen och information mellan fordon och system med en fast plats. TIME gäller alla delar i ett informationssystem, hur data produceras och processas, infrastruktur för information och principer för datalagring och informationsutbyte samt funktioner och tjänster baserade på denna information. TIME avser t.ex. att medverka till att samverkan mellan järnvägstransportbranschens aktörer fungerar bra, dessa aktörers egen verksamhet blir effektiv och att kunder till järnvägen och andra som beror av järnvägen erhåller rätt information.
Per Kreuger, Martin Aronsson, Markus Bohlin
Denna rapport beskriver och motiverar leveranstågplanens roll och utformning i relation till den dynamiska tågplanen. Med utgångspunkt i formen för de krav som specificerats i den framtida tåglägesansökan föreslår vi en form för leveranstågplanen vars syfte är att både kunders och trafikutövares krav på förutsägbarhet och samtidigt ger utrymme för effektiv operativ styrning och kortare ledtider vid förändrad efterfrågan. I sin första version är detta dokument främst tänkt som ideskiss för diskussion och kritisk analys bland kapacitetsfördelningsprocessen intressenter.
Max Loubser
The Delay Tolerant Networking Architecture (DTN) has been proposed for use in challenged networks that suffer from intermittent connectivity or high delay. The DTN architecture and the bundle protocol presents a standard method to interconnect heterogeneous challenged networks using asynchronous message switching. It provides a framework for dynamic routing, contact scheduling, naming, reliability and transmission status reports. Wireless Sensor Networks (WSNs) are often viewed as challenged networks as nodes operate at low power, often with weak or intermittent radio communication. WSNs are an important application area for DTN. In this work I present ContikiDTN, a TCP/IP based prototype implementation of the DTN architecture and bundle protocol. ContikiDTN aims to evaluate the suitability of the DTN bundle protocol as a solution for messaging inside a TCP/IP WSN and as a way of connecting the WSN to the Internet. I discuss the design and implementation of ContikiDTN using the Contiki operating system. I highlight the issues in implementing the bundle protocol with TCP and Contiki. I show that the event-driven Contiki kernel is very suitable for an asynchronous message forwarding application. I use ContikiDTN to communicate with a full PC platform implementation of DTN and show that it can be used as a gateway to the Internet. I present a simulation and experimental results showing the performance of multi-hop TCP based DTN as compared to only TCP. I show that the core propositions of the DTN architecture hold in a WSN and that it is feasible to implement DTN on resource constrained devices using TCP/IP and Contiki.
Ali Ghodsi, Sameh El-Ansary, Supriya Krishnamurthy, Seif Haridi
We present a self-stabilizing network size estimation gossip algorithm which determines the number of nodes in a structured peer-to-peer system. The algorithm can handle joins, leaves, and failures and is applicable to most structured peer-to-peer systems providing a distributed hash table abstraction. Furthermore, the algorithm is self-stabilizing with respect to the local estimates of any node, which might be arbitrary at any given time. Once state corruption ceases, the algorithm eventually adjusts all estimates to the correct value even in presence of joins and leaves. The algorithm only assumes that the system is weakly fair, and does hence not require the nodes to make the same number of exchanges, to be correct.
Jussi Karlgren, Shlomo Argamon, James G Shanahan
Papers from the workshop held in conjunction with the 28th Annual International ACM Conference on Research and Development in Information Retrieval, August 13-19, 2005, Salvador, Bahia, Brazil
Stina Nylander, Thomas Nyström, Botond Pakucs
We have applied interaction acts, an abstract user-service interaction specification, to speech user interfaces to investigate how well it lends itself to a new type of user interface. We used interaction acts to generate VoiceXML-based speech user interface, and identified two main issues connected to the differences between graphical user interfaces and speech user interfaces. The first issue concerns the structure of the user interface. Generating speech user interfaces and GUIs from the same underlying structure easily results in a too hierarchical and difficult to use speech user interface. The second issue is user input. Interpreting spoken user input is fundamentally different from user input in GUIs. We have shown that it is possible to generate speech user interfaces based on. A small user study supports the results.
Per Kreuger, Martin Aronsson, Jan Ekman, Thomas Franzén
The deregulation of the Swedish rail transport market and introduction of several operators competing for train paths has fundamentally affected the demands on the capacity allocation process. As a consequence this process is facing radical change in the near future. The demands and their consequences for the future are analysed in this paper. The analysis proceeds from a set of identified requirements typically posed by rail transport customers and service operators. A simple mathematical framework in which these requirements can be formalised is defined and methods for conflict detection and resolution are discussed.
Ian Marsh
This report describes the protocol design of TCP with Forward Error Correction (TCP-FEC). The performance of TCP can be significantly improved by generating and sending redundant segments in addition to the normal TCP data segments. Data losses in the network can be recovered from the redundant or the original data packets. Additionally by adding correcting codes to the TCP transmissions, both isolated and bursty losses can be handled. The advantage for the application is that the long retransmission times can be avoided if the repair can be done locally. The advantage for the network is two-fold, excessive retransmissions do not further congest the network and wireless losses can be repaired at the receiver. This technical report details TCP-FEC from a design, migration and protocol perspective in the highly heterogeneous wireless environments envisaged by the sixth framework Ambient Networks project\footnote{This work was supported by the EU Ambient Networks Project IST-2002-507134-AN}.
Daniel Gilblad, Per Kreuger, Björn Levin, Åsa Rudström
Industrial process data is often stored in a wide variety of formats and in several different repositories. Efficient methodologies and tools for data preparation and merging are critical for efficient analysis of such data. Experience shows that data analysis projects involving industrial data often spend the major part of their effort on these tasks, leaving little room for model development and generating applications. This paper identifies and classifies the needs and individual steps in data preparation of industrial data. A methodology for data preparation specifically suited for the domain is proposed and a practically useful set of primitive operations to support the methodology is defined. Finally, a proof of concept data preparation system implementing the proposed operations and a scripting facility to support the iterations in the methodology is presented along with a discussion of necessary and desirable properties of such a tool.
Adam Dunkels, et al.
Proceedings of the First REALWSN 2005 Workshop on Real-World Wireless Sensor Networks, Stockholm, Sweden, 20-21 June 2005
Nicolas Beldiceanu, Mats Carlsson, Jean-Xavier Rampon
This report presents a catalog of global constraints where each constraint is explicitly described in terms of graph properties and/or automata. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.
Nicolas Beldiceanu, Mats Carlsson, Jean-Xavier Rampon, Charlotte Truchet
This report presents a database of about 200 graph invariants for deriving systematically necessary conditions from the graph properties based representation of global constraints. This scheme is based on invariants on the graph characteristics used in the description of a global constraint. A SICStus Prolog implementation based on arithmetic and logical constraints as well as on indexicals is available.
Anna Larsson, Carina Nerén
Women are less dedicated to computer gaming than men. Previous studies show that one reason might be that current games exhibit hypersexualised female avatars: avatars that have exaggerated sexual signals to which female players object. In this thesis the purpose is to find out how female (and male) consumers of computer games really feel about hypersexualized female avatars in computer games and how these feelings differ between the genders. We also explore how the avatars? appearance being assigned certain attitudes impact the preference of avatar. The thesis is divided into two areas of study; in the first, the preliminary study, we investigate which attitudes are associated with certain stereotypes; in the second and main study we use the results from the first study when examining how people relate to hypersexual avatars and the reasons for this. The results from the main study of this thesis show that there are no great differences of how the hypersexual avatars are perceived by males and females, a majority in both gender groups do not reflect on the abnormality of the avatars exaggerated body shape; avatars with this appearance are actually preferred as personal representations in a game. It is the avatars clothes that are more in the centre of attention in the study, the avatars that does not show as much skin as the others are the ones preferred by both males and females. Stereotypical attitudes associated with the avatars seem to influence how the avatars are perceived, the avatars that make people think of a negative stereotype are shunned in selections for personal representation in a game, with a positive stereotype the reactions are the opposite.
Adam Dunkels, Oliver Schmidt
Protothreads are a extremely lightweight, stackless threads designed for use in severely memory constrained systems such as embedded systems. Software for memory constrained embedded systems sometimes are based on an event-driven model rather than on multi-threading. While event-driven systems allow for reduced memory usage, they require programs to be developed as explicit state machines. Since implementing programs as explicit state machines is hard, developing, maintaining, and debugging programs for event-driven systems is difficult. Protothreads simplify implementation of high-level functionality on top of event-driven systems, without significantly increasing the memory requirements. Protothreads can be implemented in in the C programming language using 10 lines of code and 2 bytes of RAM per protothread.
Mattias Söderqvist
Two of the most commonly used intra-domain Internet routing protocols are Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). In both these protocols the traffic is routed along shortest paths to the destination without considering other traffic demands or load in the network. The weight of the links, and thereby the shortest paths, can be set by the network operator. This creates the possibility for the network operator to redirect traffic from congested links to less utilised links and achieve a more efficient use of the network. We study three different heuristics for the problem of finding a set of OSPF/IS-IS weights that optimises the performance of the network. We evaluate the heuristics in topologies with power-law properties and compare the obtained results with those from a standard weight setting recommended by Cisco (a major router vendor) as well as with those from an optimal multi-commodity flow routing. Our main conclusion is that one of the heuristics performs better than the rest of the heuristics and achieves results reasonable close to optimum.
Daniel Gillblad, Anders Holst, Björn Levin, Magnus Gudmundsson
We explore the possibility of replacing a first principles process simulator with a learning system. This is motivated in the presented test case setting by a need to speed up a simulator that is to be used in conjunction with an optimisation algorithm to find near optimal process parameters. Here we will discuss the potential problems and difficulties in this application, how to solve them and present the results from a paper mill test case.
Daniel Hasselrot
In the last few years many new structured overlay network protocols for peer-to-peer systems have appeared. Following that, the need to test and develop the protocols in a controlled environment arose and many different simulators were written, often only supporting a single protocol and designed with a specific simulation task in mind. We introduce a general component based framework in Java for writing peer-to-peer simulators, complete with methods for exporting and visualizing the simulation data. The simulation framework is built using the Java in Simulation Time (JiST) framework, a parallel discrete-event simulation package for Java, allowing close to pseudo code implementation of the protocols using simulated remote procedure calls, while still providing flexibility enough for down to packet level simulation of the protocols.
Fredrik Holmgren
Studying how peers come and go in a model of a peer-to-peer overlay network and how it effects the distributed routing information can be a complex task. It usually gets to be a complex task even for a relative small network. Means for visualizing graphically the events and changes in an overlay network would be helpful for understanding, developing, verifying and demonstrating such networks. This report is the result of a short study towards designing and implementing such a visualization tool for the Chord protocol.
Markus Bylund, Marie Sjölinder, Anna-Frida Eriksson
The work described herein focus on the impact of different context factors in short-term planning situations. We have investigated which services have been used to solve different tasks. The method used in the study was based on scenario descriptions. The participants reported how they would have acted in different situations and they also rated the importance of different context factors in different situations. Analyses were made that revealed relationships between context factors and services used by the participants of the study. A qualitative analysis was also conducted, with the aim to capture context factors not covered in the study design.
Markus Bylund, Marie Sjölinder, Anna Danestig
The physical, social, and computational context of people affect their choice of activity, thus also their need for and use of mobile services. It is quite easy to find likely examples of situations where this would be true. For example, a person who is standing on a subway station on the way home from work, waiting for a train that does not appear to be on time, is more likely to feel a need for a subway time table or traffic information than someone who is driving a car. To what degree does context matter is however not easy to answer precisely. Which context parameters matter for which activities, and in which combinations? This report describes a study with the aim to draw a map of user activities and context parameters, as well as combinations of context parameters. The study is based on a qualitative method with only 10 study participants, and thus, no precise answers can be given to any question regarding which context parameters matter more than others when trying to predict what user activity is needed the most for every given situation. However, the intention is that the report will assist in determining which context parameters and user activities are the most interesting to take a closer look at.
Daniel Gillblad, Anders Holst, Per Kreuger, Björn Levin
This report describes the gmdl modeling and analysis environment. gmdl was designed to provide powerful data analysis, modeling, and visualization with simple, clear semantics and easy to use, well defined syntactic conventions. It provides an extensive set of necessary for general data preparation, analysis, and modeling tasks.
Erik Klintskog
This technical report describes the integration of the Distribution Subsystem (DSS) to the programming system Mozart. The result, OzDSS, is described in detail. Essential when coupling a programming system to the DSS is how the internal model of threads and language entities are mapped to the abstract entities of the DSS. The model of threads and language entities of Mozart is described at a detailed level to explain the design choices made when developing the code that couples the DSS to Mozart. To show the challenges associated with different thread implementations, the C++DSS system is introduced. C++DSS is a C++ library which uses the DSS to implement different types of distributed language entities in the form of C++ classes. Mozart emulates threads, thus there is no risk of multiple threads accessing the DSS simultaneously. C++DSS, on the other hand, makes use of POSIX threads, thus simultaneous access to the DSS from multiple POSIX threads can happen. The fundamental differences in how threads are treated in a system that emulates threads (Mozart) to a system that make use of native-threads~(C++DSS) is discussed. The paper is concluded by a performance comparison between the OzDSS system and other distributed programming systems. We see that the OzDSS system outperforms ``industry grade'' Java-RMI and Java-CORBA implementations.
Erik Klintskog
This technical report describes the implementation of the DSS middleware with focus on the design of the abstract entity interface and the coordination layer. Key concepts are highlighted and described, on the level of C++ classes.
Zacharias ElBanna, Erik Klintskog, Per Brand
This report presents how the Distribution Subsystem is made secure. A set of different security threats to a shared data programming system are identifed. The report presents the extensions nessesary to the DSS in order to cope with the identified security threats by maintaining reference security. A reference to a shared data structure cannot be forged or guessed; only by proper delegation can a thread acquire access to data originating at remote processes. Referential security is a requirement for secure distributed applications. By programmatically restricting access to distributed data to trusted nodes, a distributed application can be made secure. However, for this to be true, referential security must be supported on the level of the implementation.
Juan Alonso, Adam Dunkels, Thiemo Voigt
Energy is one of the most important resources in wireless sensor networks. We use an idealized mathematical model to study the energy consumption under all possible routings. Our results are very general and, within the assumptions listed in Section 2, apply to arbitrary topologies, routings and radio energy models. We find bounds on the minimal and maximal energy routings will consume, and use them to bound the lifetime of the network. The bounds are sharp, and we show that they are achievable in many situations of interest. We give some examples, and apply the theory to the problem of covering a given square region with the most efficient member of a family of increasingly more dense square-lattice sensor networks. Finally, we use simulations to test these results in a more realistic scenario, where packet loss can occur.
Sameh El-Ansary, Supriya Krishnamurthy, Erik Aurell, Seif Haridi
In this paper, we present a complete analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a master-equation-based approach, which is used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. We demonstrate that this methodology is infact also well suited to describing structured overlay networks by an application to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately account for the functional form of: the distribution of inter-node distances, the probability of network disconnection, the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict both the performance and consistency of lookups under churn. Additionally, we also discuss how churn may actually be of different 'types' and the implications this will have for structured overlays in general. All theoretical predictions match simulation results to a high extent. The analysis includes details that are applicable to a generic structured overlay deploying a ring as well as Chord-specific details that can act as guidelines for analyzing other systems.
Ali Ghodsi, Luc Onana Alima, Seif Haridi
Existing structured peer-to-peer systems heavily rely on replication as a means to provide fault-tolerance. Many systems use the so-called successor- list scheme for replication. We argue that this scheme has grave limitations. First, these systems are vulnerable to, what we call, Mendacity attacks, where a malicious peer can lie about other peers to gain full control over all replicas of an item. Second, the successor-list scheme prevents the peers from doing concurrent-requests to replicas of an item. We present, and provide full algorithmic specification for, a generic replication scheme called symmetric replication. The scheme is applicable to all existing structured peer-to-peer systems. In contrast to the successor-list scheme, our scheme makes replicas independent of each other, preventing Mendacity attacks while enabling concurrent requests. Concurrent requests can be used for increasing the security by using voting or consensus algorithms to ensure the correctness of replicas. Moreover, concurrent requests can be used for load-balancing of requests, and to add locality awareness. Finally, to maintain the replication factor, the successor-list scheme uses a complex algorithm that involves all peers replicating a departing peer. In contrast, our symmetric replication scheme only involves two peers to restore the replication factor and thus avoids such complex algorithms.
Raghu Arunachalam, Joakim Eriksson, Niclas Finne, Sverker Janson, Norman Sadeh
This report is the specification for the Trading Agent Competition Supply Chain Management Game - TAC SCM-04, to be held between July 20-22, 2004, in New York in conjunction with AAMAS-04. Based on the experience of the 2003 Trading Agent Competition a few enhancements have been added to the original game: (1)The price function has been modified to better reflect demand; (2) storage costs have been introduced; and (3) customer demand has been segmented into multiple markets.
Luc Onana Alima, Ali Ghodsi, Seif Haridi
Structured peer-to-peer overlay networks have recently emerged as good candidate infrastructure for building novel large-scale and robust Internet applications in which participating peers share computing resources as equals. In the past three year, various structured peer-to-peer overlay networks have been proposed, and probably more are to come. We present a framework for understanding, analyzing and designing structured peer-to-peer overlay networks. The main objective of the paper is to provide practical guidelines for the design of structured overlay networks by identifying a fundamental element in the construction of overlay networks: the embedding of k-ary trees. Then, a number of effective techniques for maintaining these overlay networks are discussed. The proposed framework has been effective in the development of the DKS system.
Nicolas Beldiceanu, Mats Carlsson, Thierry Petit
This report deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in $n$, where $n$ is the number of variables of the corresponding global constraint. By reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.
Anders Holst, Per Kreuger
Denna rapport beskriver resultatet av en dataanalys gjord på produktionsdata från Outokumpu:s valsverk i Avesta. Syftet har varit att fastställa samband mellan övriga produktionsparametrar och uppkomsten av sk. "slivers" en typ av ytlig sprick- eller veck-bildning i det färdiga stålet. Ett annat syfte har varit att studera metodologiska frågor i ett arbete av detta slag.
Adam Dunkels, Juan Alonso, Thiemo Voigt, Hartmut Ritter
Previous research on transport layer protocols for wireless sensor networks (WSNs) has focused on designing protocols specifically targeted for sensor networks. Most sensor networks applications, however, are only useful when connected to an external network. The deployment of TCP/IP in WSNs would enable direct connection between the WSN and external TCP/IP networks. However, TCP performs badly in wireless environments both in terms of throughput and energy efficiency. To overcome these problems in WSNs we have designed Distributed TCP Caching. This mechanism greatly enhances TCP performance by caching TCP segments on the nodes in the sensor network and locally retransmitting lost segments. Our simulations demonstrate that with these enhancements TCP performs well enough to be useful in wireless sensor networks.
Adam Dunkels, Björn Grönvall, Thiemo Voigt, Juan Alonso
Wireless sensor networks are composed of large numbers of tiny networked devices that communicate untethered. In this paper we present the design of Contiki, a lightweight and portable operating system for such tiny devices. In this work, we try to find the right operating system abstractions that enable dynamic and efficient operation of a system with severe limitations. Contiki is built around a lightweight event scheduler and provides suitable abstractions for dynamic loading of programs, device drivers, and run-time linking of libraries. The system is highly portable and the kernel can be ported without changing a single line of code (except device drivers). We show how higher level abstractions such as multi-threading can be implemented as libraries on top of the lightweight event kernel.
Gerd Andersson, Adrian Bullock, Jarmo Laaksolahti, Stina Nylander, Fredrik Olsson, Marie Sjölinder, Annika Waern, Magnus Boman
A categorization of telecommunications services is presented, as a deliverable in a project commissioned by TeliaSonera.
Emmanuel Frécon
A few years ago, Virtual Reality technologies and Virtual Environments were seen by some as a panacea and the computer interface of the future. VR received a lot of attention in the media and devices such as head mounted displays or data gloves have become widely recognised. Of particular interest was the ability to realise a vision that had been described in a number of science fiction novels: providing a parallel world in which it would be possible to be present, interact and feel as if in the real world. This vision is realised by Collaborative Virtual Environments (CVEs). CVEs are three-dimensional computer-generated environments where users are represented by avatars and can navigate and interact in real-time independently of their physical location. While the technology has not lived up to early expectations, real niched applications and the success of networked games have shown its viability and promises. This report summarises a number of the technologies that are commonly used to interface with virtual environments. Additionally, it presents some of the major CVE systems to date and isolates a number of trends when it comes to network architectures, protocols and techniques and to software choices.
Fredrik Olsson
Machine learning methods have been successfully applied to a number of language technology tasks. The purpose of this report is to investigate the efforts made in applying machine learning methods for handling the phenomena of anaphoric reference and coreference in text.
Erik Aurell, Sameh El-Ansary
Is it possible to treat large scale distributed systems as physical systems? The importance of that question stems from the fact that the behavior of many P2P systems is very complex to analyze analytically, and simulation of scales of interest can be prohibitive. In Physics, however, one is accustomed to reasoning about large systems. The limit of very large systems may actually simplify the analysis. As a first step, we here analyze the effect of the density of populated nodes in an identifier space in a P2P system. We show that while the average path length is approximately given by a function of the number of populated nodes, there is a systematic correction which depends on the density. In other words, the dependence is both on the number of address nodes and the number of populated nodes, but only through their ratio. Interestingly, the correction is negative for finite densities, showing that an amount of randomness somewhat shortens average path length. END of example.
Tobias Hasselrot
Fair Bandwidth Allocation (FBA) in Internet gateways is the problem of how to allocate network capacity between users that share an Internet connection. This Thesis starts with explaining different views of fairness and fair resource allocation and how they are related to existing solutions of FBA. The main part of this Thesis describes the implementation of an agent-based electronic market system for FBA. The advantage of the market approach is that users that do not use their Internet connection are being compensated when letting others use their capacity. A testbed is created where the implemented system is tested by using simulated users that sends real network traffic. The tests show that the market is able to shape the users' network traffic according to their bought capacity and that users that seldom use their Internet connection get higher throughput with the system active compared to ordinary FBA solutions. This behavior is expected and wanted as it reduces the unfair subsidization of very active users.
Henrik Abrahamsson, Bengt Ahlgren
Several studies of Internet traffic have shown that it is a small percentage of the flows that dominate the traffic. This is often referred to as the mice and elephants phenomenon. It has been proposed that this might be one of very few invariants of Internet traffic and that this property could somehow be used for traffic engineering purposes. The idea being that one in a scalable way could control a major part of the traffic by only keeping track of a small number of flows. But for this the large flows must also be stable in the meaning that they should be among the largest flows during long periods of time. In this work we analyse packet traces of Internet traffic and study the temporal characteristics of large aggregated traffic flows defined by destination address prefixes.
Åsa Rudström, Kristina Höök
A study was performed to investigate a domain for a mobile and social service, where a web of social trails is overlaid over a physical space. Using a method inspired by work of the city planner Kevin Lynch, 20 subjects were interviewed about their experiences, activities, movements and habits related to a specific shopping mall. Design implications for the service were drawn from subjects’ sketches of the area, lists of places important to them, and their daily routes through the mall as drawn on a standardized map. Three user groups were identified based on the amount of activities and time spent in the mall: dwellers, shoppers and exploiters. User sketches indicated that traditional maps are not an optimal means for visualising the mall in the service. Finally, the way subjects grouped, labelled and defined places and objects in the mall provided valuable input to the design of the service interface.
Åsa Rudström
An ethnographically inspired study was performed in the Kista Galleria shopping mall. The objective was to provide input to the design of a mobile social service running on mobile telephones. User behaviour was observed indicating opportunities for a service to manifest itself on a user's mobile phone without being too obtrusive: phone walking, glancing, and logging on and off. The study also provided insight as to places in the mall where people tend to gather and stop for some time span: waiting rooms. Such places are appropriate for the placement of server stations and public server displays.
Ola Westin
There are many issues that limit the performance of wireless mobile multi-hop ad hoc networks (MANETs). One of them is that TCP is not well adapted to networks where routes can change or disappear often. In this paper the behaviour of a standard TCP implementation is studied in situations typical for MANETs and compared to the behaviour of a partial implementation of a ATCP, a TCP modification that is intended to increase performance in MANETs. Simulations with simple scenarios show that TCP easily creates a full network load which causes send failures and decreased throughput performance. In some cases the partial ATCP implementation increases throughput but more often it causes an increased amount of duplicate retransmissions. In these scenarios it is unlikely that even a complete ATCP implementation would increase throughput performance. A few modifications to ATCP and TCP are analysed. Especially a limit of the congestion window size shows a large throughput increase. The results are inconclusive, the simulations are too simple to show if the results are applicable in more complex scenarios. It is not clear if ATCP actually is useful in a MANET.
Adam Dunkels, Juan Alonso, Thiemo Voigt
The TCP/IP protocol suite, which has proven itself highly successful in wired networks, is often claimed to be unsuited for wireless micro-sensor networks. In this work, we question this conventional wisdom and present a number of mechanisms that are intended to enable the use of TCP/IP for wireless sensor networks: spatial IP address assignment, shared context header compression, application overlay routing, and distributed TCP caching (DTC). Sensor networks based on TCP/IP have the advantage of being able to directly communicate with an infrastructure consisting either of a wired IP network or of IP-based wireless technology such as GPRS. We have implemented parts of our mechanisms both in a simulator environment and on actual sensor nodes, and preliminary results are promising.
Juan Alonso, Adam Dunkels, Thiemo Voigt
Energy is one of the most important resources in wireless sensor networks. We use an idealized mathematical model to study the impact of routing on energy consumption. Our results are very general and, within the assumptions listed in Section 2, apply to arbitrary topologies, routings and radio energy models. We find bounds on the minimal and maximal energy routings will consume, and use them to bound the lifetime of the network. The bounds are sharp, and can be achieved in many situations of interest. We illustrate the theory with some examples.
Report number was reserved November 2003. No report was produced.
Adam Dunkels, Thiemo Voigt, Juan Alonso, Hartmut Ritter, Jochen Schiller
Wireless sensor networks are based on the collaborative efforts of many small wireless sensor nodes, which collectively are able to form networks through which sensor information can be gathered. Such networks usually cannot operate in complete isolation, but must be connected to an external network to which monitoring and controlling entities are connected. As TCP/IP, the Internet protocol suite, has become the de-facto standard for large-scale networking, it is interesting to be able to connect sensornets to TCP/IP networks. In this paper, we discuss three different ways to connect sensor networks with TCP/IP networks: proxy architectures, DTN overlays, and TCP/IP for sensor networks. We conclude that the methods are in some senses orthogonal and that combinations are possible, but that TCP/IP for sensor networks currently has a number of issues that require further research before TCP/IP can be a viable protocol family for sensor networking.
Stina Nylander
This paper is composed of two parts. The first one gives a review of the design iterations for the Ubiquitous Interactor prototype. The second part makes a primary evaluation the concepts and the implementation, describes a small pilot study and gives some pointers on how the future evaluation will be conducted.
Stina Nylander, Markus Bylund, Magnus Boman
If services providing real-time information are accessible from mobile devices, functionality is often restricted and no adaptation of the user interface to the mobile device is attempted. Mobile access to real-time information requires designs for multi-device access and automated facilities for adaptation of user interfaces. We present TapBroker, a push update service that provides mobile and stationary access to information on autonomous agents trading stocks. TapBroker is developed for the Ubiquitous Interactor system and is accessible from Java Swing user interfaces and Web user interfaces on desktop computers, and from a Java Awt user interface on mobile phones. New user interfaces can easily be added without changes in the service logic.
Stina Nylander, Markus Bylund, Annika Waern
The Ubiquitous Interactor (UBI) addresses the problems of design and development that arise around services that need to be accessed from many different devices. In UBI, services present themselves with different user interfaces on different devices. This is done by separation of user-service interaction and presentation. The interaction is kept the same for all devices, and different presentation information is provided for different devices. This way, tailored user interfaces for many different devices can be created without multiplying development and maintenance work. In this paper we describe the design of UBI, the system implementation, and two services implemented for the system: a calendar service and a stockbroker service.
Stina Nylander
This report provides an overview of different approaches to device independent development of applications and a background to why it is important for mobile computing. It also describes the different sources of inspiration for the work with the Ubiquitous Interactor.
Lars-Åke Fredlund
The paper describes an experiment in which a framework for model checking Java byte code, combined with the application of runtime monitoring techniques through code rewriting, was used to guarantee correctness properties of a Java Card applet.
Jakub Orzechowski Westholm, Adam Ameur
The aim of the GENKOMB project was to find and analyse transcription factor binding sites in the human genome, by correlating expression data for a set of genes with the nucleotide sequences in their upstream regions. This document is a technical description of tools that have been developed and results that have been obtained in the GENKOMB project. Apart from detecting transcription factor binding sites, this project has resulted in programs for matching weight matrices to DNA sequences and multiple alignment of short nucleotide sequences.
Martin Aronsson, Jan Ekman, Per Kreuger
This project is concerned with how to improve the capacity allocation process. In particular the project aims at proposing an enhanced format for train path applications, study the technical limitations for timetabling support tools and in the longer term to implement support systems for the train path allocation process. This report describes the various factors that affect the application process, and report the opinions from several actors in the field. Since the deregulation of the Swedish railway, and with new EU directives, the foundations for the capacity allocation process is changing rapidly. There is a strong need for clear and predictable principles that are fair and operator neutral and implements the prioritisation given to different types of traffic and for improved methodologies and decision support tools in the capacity allocation process. This is crucial to support both the possibility for the traffic operators to state demands and the timetable designers in judging conflicting train paths. A conclusion is that almost all the requirements on the timetable presented in this report can in fact be stated as properties and relations of events in the timetable.
Malin Forsgren
Banverket, the Swedish National Rail Administration, is interested in the development of a standard regarding how to assess capacity on railway networks. Jan Ekman and Per Kreuger at SICS AB propose that capacity on a section of a railway network for a specific traffic pattern can be assessed by computing its cycle time. This report covers an account of my implementation of Ekman and Kreuger's cycle time algorithm. It also describes my suggestion of an algorithm that transforms an intuitive representation of a traffic pattern to a graph that can be used as input to the cycle time algorithm. My major contribution to the project is to facilitate the computation of the cycle time of a traffic pattern by having designed a bridge between the description of a traffic pattern and the format suitable for Ekman and Kreuger's algorithm. The execution of these two tasks are important for an eventual continuation of the main project. My results constitute an important piece in a work that has the potential of making a real difference in the way in which capacity related issues in this field are handled.
Jan Ekman, Per Kreuger
Detta är slutrapporten till projektet "Beslutsstöd för utredning av kapacitetsfrågor vid signalprojektering," utfört av SICS AB under perioden januari 2002 - mars 2003 och finansierat av Banverkets FoU-program. Rapporten beskriver en metod att beräkna kapacitet, där kapacitet avser antalet tåg som per tidsenhet går att framföra genom ett spårområde. Metoden beräknar minsta tiden för en upprepning hos en periodiskt upprepad trafik. I rapporten införs begreppen fri väg och trafikering för att resonera om kapacitet. Dessa begrepp är centrala för metoden och delar upp beräkningen i två delar. Den ena delen utgörs av framtagandet av värden som hör samman med de införda begreppen, från data om bland annat fordon och infrastruktur. Beräkningen av kapacitet från dessa värden utgör den andra delen. Rapporten ger en detaljerad beskrivning av hur man går till väga för att använda metoden, bevis av det grafteoretiska påstående som metoden baseras på och uppskattning av metodens beräkningskomplexitet. Rapporten innehåller också en diskussion kring vad utredning av kapacitet innebär, resonemang kring målet med ett visst kapacitetskrav och förslag på hur kapacitet kravställs. Vid signalprojektering kan metoden användas både till snabba ungefärliga och till noggranna uppskattningar av kapacitet. Lämpliga sätt att använda metoden är att jämföra olika sätt att placera signaler, jämföra ett antal trafiklösningar på en bangård och att jämföra olika val av mötesstationer på en enkelspårssträcka.
Waldemar Kocjan , Per Kreuger
The symmetric cardinality constraint is described in terms of variables X = {x_1,...,x_k} which take values in the subset of values V={v_1,...,v_n}. It constraints the number of times a value can be assigned to a variable in X to be in an interval [l_{x_i},c_{x_i}] and at the same time it restricts the number of values in V which any variable can take to an interval [l_{v_j},c_{v_j}]. In this paper we introduce the symmetric cardinality constraint and define set constraint satisfaction problem as a framework for dealing with this type of constraints. Moreover, we present effective filtering methods for the symmetric cardinality constraint.
N.V. Antonov
A system of stochastic differential equations for the velocity and density of a classical self-gravitating matter is investigated by means of the field theoretic renormalization group. The existence of two types of large-scale scaling behavior, associated to physically admissible fixed points of the renormalization-group equations, is established. Their regions of stability are identified and the corresponding scaling dimensions are calculated in the one-loop approximation (first order of the epsilon expansion). The velocity and density fields have independent scaling dimensions. Our analysis supports the importance of the rotational (non-potential) components of the velocity field in the formation of those scaling laws.
Ian Marsh, Fengyi Li
Time, day, location and instantaneous network conditions largely dictate the quality of Voice over IP calls. In this paper we present the results of over 18000 VoIP measurements, taken from nine sites connected in a full-mesh configuration. We measure the quality of the routes on a hourly basis by transmitting a pre-recorded call between a pair of sites. We repeat the procedure for all nine sites during the one hour interval. Based on the obtained jitter, delay and loss values as defined in RFC 1889 (RTP) we conclude that the VoIP quality is acceptable for all but one of the nine sites we tested. We also conclude that VoIP quality has improved marginally since we last conducted a similar study in 1998.
Martin Aronsson, Jan Ekman, Per Kreuger
Denna rapport beskriver status hos den forskning som är relevant för tåglägestilldelning samt analyserar och kommenterar några av de reglerande dokument såsom lagar och förordningar samt instruktioner och information som Banverket och Tågtrafikledningen tagit fram. för att styra tåglägestilldelningsprocessen. Rapporten ger också en översikt av forskningsfronten vad gäller systemstöd för tåglägestilldelningen och ger en kortfattad en beskrivning av några av de tekniker som kan vara användbara i ett stödsystem för tåglägestilldelning samt lyfter fram deras respektive för och nackdelar.
Markus Bylund
We present the results of an empirical evaluation of the performance of some network connections available for mobile terminals. General Packet Radio Service (GPRS) is compared with Bluetooth and a USB wired connection from a Sony Ericsson P800 smart phone.
Douglas Wikström
A subgroup G_q, of prime order q, for which the discrete logarithm problem is assumed hard is mostly a subgroup of a larger group, e.g. Z_p^* for some prime p=k*q+1. Arithmetic for G_q is not implemented directly. Instead, arithmetic for the larger group, e.g. Z_p^*, is implemented, which gives arithmetic also for G_q. Furthermore, in most protocols based on arithmetic in G_q the participants do not verify their input properly. They only verify that inputs are in Z_p^*, even when they should verify that the inputs are in G_q. This practice sometimes allows the adversary to hand inputs from Z_p^*\G_q to honest participants without detection. Surprisingly, this seems to be a novel observation. In this paper we discuss the general problem further, introduce a novel class of attacks based on the above observations, and outline an efficient generic recipe for how to counter the attacks efficiently. To illustrate both the attacks and the countermeasures we provide examples of protocols that are vulnerable to the novel attacks, and show how they may be modified to counter the attacks. In particular we present attacks on the robustness for the majority of the El Gamal based mix-nets in the literature, and an attack on the privacy for the generic mix-net based on the proof of knowledge of correct shuffle of Furukawa and Sako.
Douglas Wikström
Golle, Zhong, Boneh, Jakobsson, and Juels recently presented a very efficient mix-net, that they claim to be both robust, and secure. We present four practical attacks for their mix-net, and break both its privacy and robustness. Each attack exploits and illustrates a separate weakness of the protocol. The first attack breaks the privacy of any given sender without corrupting any mix-server. The second attack requires that the first mix-server is corrupted. Both attacks are adaptations of the ``relation attack'' introduced by Pfitzmann. The third attack is similar to the attack of Desmedt and Kurusawa and breaks the privacy of all senders, and robustness. It requires that all senders are honest, and that the last mix-server is corrupted. The fourth attack is novel and breaks the privacy of any given sender. It requires that the first and last mix-servers are corrupted. This attack breaks also ``Flash Mix'' by Jakobsson, including the fixed version given by Mitomo and Kurosawa.
Petter Pettersson
Five network services that meet the needs of new Internet applications are formulated as derivatives on the spot price of the capacity in network connections. The derivatives are priced using the Black-Scholes model. The services suggested are: a multcast service for one-to-many connections, a video on-demand service, a service that gives the user perceived higher quality for many applications, a service that allows the requested capacity to vary with time and a service that does not specify the exact time of delivery of capacity.
Nicolas Beldiceanu, Mats Carlsson, Sven Thiel
This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Yk of the pairs X,Yk (1<=k<=n) occurring in these conjunctions. The main benefit of this new technique comes from the fact that, for adjusting the bounds of a variable X according to n conjunctions, we do not perform n sweeps in an independent way but rather synchronize them. We then specializes this technique to the non-overlapping rectangles constraint where we consider the case where several rectangles of height one have the same X coordinate for their origin as well as the same length. For this specific constraint we come up with an incremental bipartite matching algorithm which is triggered while we sweep over the time axis. We illustrate the usefulness of this new pruning method on a timetabling problem, where each task can’t be interrupted and requires the simultaneous availability of n distinct persons. Each person has its own periods of unavailability and can only perform one task at a time.
Erik Klintskog, Zacharias ElBanna, Per Brand
This document presents the philosophy and design of our language independent middleware, the Distribution Subsystem(DSS). A notion of abstract entity types enables the DSS to offer distribution support for virtually any high level programming language. A novel framework for entity consistency protocols is presented. The framework greatly simplifies the development of new protocols, indicated by the numerous protocols provided by the DSS implementation. A roadmap of how to couple a programming system to the DSS is also given
Waldemar Kocjan
Most of the research literature concerning scheduling concentrates on the static problems, i.e. problems where all input data is known and does not vary over the time. However, the real world scheduling problems are very seldom static. Events like machine failures or work overloads are, in some situations, impossible to predict. Dynamic scheduling is a research field which take into consideration uncertainty and dynamic changes in the scheduling problem. This paper gives an overview of the state of the art in the field of dynamic scheduling.
Per Persson, Petra Fagerberg
Much of context-aware application research has dealt with the technical aspects of context capturing and how to interpret the context of a user. Little effort, however, has been spent on the experience and usage of these systems. This paper describes a real-use study of a location-aware community system - GeoNotes. Over the one-month trial, 78 users published 283 information items connected to indoor and outdoor places. Users found present people, synchronous situations and activities more interesting to ‘tag’ than physical objects. Chat turned out to be the major activity in the system. In finding new notes at a place, users found the number of comments pivotal. GeoNotes was conceptualized in terms of newsgroup and IM applications. Implications for design are discussed.
Olof Hagsand, Ian Marsh, Kjell Hanson
The end to end delay is a critical factor in the perceived quality of service for Voice over IP applications. The described solution is a complete system-level platform and complements QoS work in the network and application areas. We describe a VoIP system that couples the low level features of audio hardware with a jitter buffer playout algorithm. Using the sound card directly eliminates intermediate buffering as well as providing fine control over timers needed by a soft real-time application such as VoIP. A statistical based approach for inserting packets into audio buffers is used in conjunction with a scheme for inhibiting unnecessary fluctuations in the system. We give comparisons for the performance of the playout algorithm against idealised playout conditions. We also present mouth to ear delay measurements for selected VoIP applications and show that several hundreds of milliseconds can be saved by using the techniques described in this paper. A prototype for both UNIX and Windows platforms (NT and 9X) has been implemented, demonstrating that our system adapts to network conditions whilst maintaining low delays.
Martin Aronsson, Jan Ekman
TUFF-PO rör personalplaneringsarbetet, specifikt planering för bemanning av tåg med lokförare, i tidiga faser då tidtabellen ännu inte är fastställd men då ett antal villkor och begränsningar på tågen och deras rörelser är kända. TUFF-PO genererar förslag och data som möjliggör effektiv personalplanering i senare skeden, genom att skapa begränsningar på tidtabelläggningen, begränsningar som tar bort dåliga och ineffektiva lösningar ur personalplaneringsperspektivet och bevarar de goda och effektiva lösningarna. Fokus för detta arbete är på tid och krav på tid, inte direkt på kostnader. Ansatsen i TUFF-PO är inte att försöka konstruera personalomlopp och inte heller personalslingor utan att titta på arbetsperioder för att utifrån dessa försöka finna gemensamma egenskaper som tycks gynna bra personalomlopp i senare planeringsskeden. Dessa egenskaper lägger grunden för de begränsningar som bildar krav på tidtabelläggningen. Preliminära resultat pekar på att det är möjligt att skapa kvalitativt bättre personalplaner. Vi tar upp och belyser både generella frågeställningar och den prototypimplementering som är gjord för att validera resultaten.
Douglas Wikström
First we present two attacks for the mix-net proposed by Golle et al., and also propose modifications that counter our attacks. The first attack breaks the privacy of the protocol completely. Our attacks are adaptations of the "relation attack", discussed by Jakobsson, Pfitzmann, and Wikström, but we introduce a novel way of exploiting intermediate values of different mix-sessions. Then we propose two optimizations of the protocol that reduce the number of exponentiations computed by each mix-server from 4(k+1)N to 4N, where k is the number of mix-servers, and N is the (large) number of senders (we improve the analysis of the original protocol from (5+10k)N to 4(k+1)N). Thus the modified protocol outperforms the original by a factor k+1, with complexity essentially independent of k.
Lars Rasmusson and Erik Aurell
In a simulation of a computer network, the capacity between pairs of border routers in a network domain is sold on a spot market. End-users establish point-to-point connections across several domains by buying capacity in the domains along a path in the network. This paper compares three different trading strategies: spot requests, null broker requests, and derivative broker requests. Their performance is measured in terms of the ratio of successful connections, and the cost to establish a connection. Simulations of a network results show that the derivative broker requests typically performs better than the other two, especially in networks where prices fluctuate rapidly.
Lars Rasmusson and Gabriel Paues
We describe the architecture of a network, in which the traffic ow is controlled by a market. The network access is controlled by a trusted access node, that separates traffic into best effort and first class traffic, adds a source route header, and shapes the traffic. The network core consists of rapid forwarding devices, such as label switches, and source routing gateways. Network services, including dynamic routing, load balancing, and fault tolerance, are built by bundling the transmission capacity in several independent network domains into a service, a bundle of resources with the right properties. The service is priced as financial derivative contract, and traded on a market, independent of the network access control. Besides describing the network model, we show how to implement parts of the network access node functionality on a standard Linux machine. The implementation has been tested on a system of virtual Linux machines.
Douglas Wikström
We describe an efficient mix-net. Its efficiency is based on a novel method, double encryption. We use a variant of "repetitive robustness", introduced by Jakobsson, to achieve robustness. The notion of double encryption enables us to avoid the large number of proofs of knowledge required in most mix-net constructions. For a large number n of senders each mix-center in our mix-net computes approximately 25n exponentiations in real time, which also gives the approximate execution time of the mix-net. Thus, our mix-net is faster than any known mix-net and the first mix-net in which the number of exponentiations computed by a mix-center is essentially independent of the number of mix-centers. Currently there exist no security proofs of our construction, but we describe the underlying ideas of the design.
Markus Bohlin, Waldemar Kocjan, Per Kreuger
In this work we present a novel method to automate the computation of global constraints cost for local search. The method is based on the representation of a global constraints as graph properties on a binary constraint network. This formulation simplifies the implementation of global constraints in local search, and provides a cost that can be readily compared to one obtained for subproblems using binary constraints exclusively. The cost obtained can be efficiently updated during the search using incremental methods. The representation of a global constraint as outlined above can also be used for generation of suitable neighborhoods for the constraint. This is done using simple repair functions applied on the elementary constraints in the global constraint graph. We show the usability of our approach by presenting formulations of global constraints in non-overlapping and cumulative scheduling.
Andreas E. Espinoza
Research has shown that training a user to apply a Mental Model while learning to use a system improves user performance. Researchers have also proposed that designing an interface, based on the mental model of an experienced user, may allow a new user to form the same mental model and be more successful in using the system. The following study proposes that presenting a novice user with a mental model based on the system to be used, which has been formed from several experienced users of the same system, will result in the new user being more successful immediately. The use of a complicated system was facilitated by the insertion of previous users mental models. The extracted mental model was presented with the introduction of the ServiceDesigner application (a system that allows the user to combine several Electronic Services). Users who received the mental model performed better with the application than the control group.
Mats Carlsson, Nicolas Beldiceanu
We present an arc-consistency algorithm for a chain of lexicographic ordering constraints on $m$ vectors of $n$ variables each. The algorithm maintains arc-consistency and runs in $O(nmd)$ time per invocation, where $d$ is the cost of certain domain operations.
Mats Carlsson, Nicolas Beldiceanu
We present a global consistency algorithm for the lexicographic ordering constraint on two vectors of $n$ variables. The algorithm maintains arc-consistency, runs in $O(n)$ time on posting plus amortized $O(1)$ time per propagation event, and detects entailment or rewrites itself to a simpler constraint whenever possible. The algorithm was derived from a finite automaton operating on a string which captures the relationship between each variable pair of the two vectors.
Fredrik Rosenhamer
In this thesis the term Authorisation Management (AM) refers to a process that begins in the real world when a decision is made concerning the delegation of authorisations. Such a decision is governed by policies. The process ends when the decision has been implemented within some computerised control mechanism in the IT-world. Today most of this process takes place in the real world. The authorisation-decision typically takes the form of a signed piece of paper that somehow is communicated to an administrator. The administrator then implements this decision, made by someone else. Besides enabling the implementation of an authorisation-decision, the process does not add any value to an organisation. It is manual, slow, involves several people and each time a decision is made, the whole process has to be initiated and performed. Further, the decision has to be expressed and implemented in terms of existing models and mechanisms and only the administrator interacts with the computerised control-mechanism in the IT-world. No widely used alternative exists. In a project named AMANDA (Authorisation Management for Distributed Applications) at the Swedish Institute of Computer Science (SICS) an alternative is being developed. AMANDA offers a mechanism that will allow AM to be decentralised in accordance with the ordinary chain of command. Using a graphical user interface, the decision-maker will implement his decision and it will take effect immediately. AMANDA will be flexible and will closely map and represent real world policies. Assuming the existence of a Public Key Infrastructure, attribute certificates are used to delegate authorisations, if needed in several steps. This thesis examines how AMANDA could simplify and improve AM. The theoretical part of this thesis describes AMANDA and the foundation on which she rests. The empirical part consists of a case study in a specific setting. First, the actual AM-process of today, with respect to a specific application, is modelled and described. Then, the future AM-process using AMANDA is modelled and described. The results indicate that AMANDA would offer a more flexible, precise, fast and secure way of AM in accordance with the operational chain of command. Though not considered in the problem statement, another result is the finding that no approach seems to exist towards modelling and describing AM as a process of it’s own. In order to perform the case study, ideas from enterprise modelling has been used to identify and understand the AM-process. Together with the Unified Modelling Language (UML), Enterprise Modelling has also inspired the notation used in the case study.
Erik Aurell, Mats Carlsson, Jan Ekman, Per Kreuger
This document summarizes the results obtained by SICS in project GENFUNK (2001). The project was carried out in collaboration with Global Genomics AB (Stockholm, Sweden). Jointly obtained results will be presented separately. Main funding was provided by Swedish Research Agency VINNOVA. Project GENFUNK studied a novel approach of measuring the global gene expression. In the method, mRNA is extracted from a tissue sample and transformed into cDNA captured on magnetic beads. This is then acted on by type IIS restriction endonucleases, which recognize certain short DNA sequences and cut the DNA close to those sequences. The resulting fragments are amplified in PCR with selected ligation fragments, and displayed in capillary electrophoresis. Determining the gene expression levels from the peak data is combinatorial optimization problem, which can in principle be solved, to give expression levels of most genes active in sampled cells, with good accuracy.
Nicolas Beldiceanu, Mats Carlsson, Sven Thiel
This article introduces the sum of weights of distinct values constraint, which can be seen as a generalization of the number of distinct values as well as of the alldifferent, and the relaxed alldifferent constraints. This constraint holds if a cost variable is equal to the sum of the weights associated to the distinct values taken by a given set of variables. For the first aspect, which is related to domination, we present four filtering algorithms. Two of them lead to perfect pruning when each domain variable consists of one set of consecutive values, while the two others take advantage of holes in the domains. For the second aspect, which is connected to maximum matching in a bipartite graph, we provide a complete filtering algorithm for the general case. Finally we introduce several generic deduction rules, which link both aspects of the constraint. These rules can be applied to other optimization constraints such as the minimum weight alldifferent constraint or the global cardinality constraint with costs. They also allow taking into account external constraints for getting enhanced bounds for the cost variable. In practice, the sum of weights of distinct values constraint occurs in assignment problems where using a resource once or several times costs the same. It also captures domination problems where one has to select a set of vertices in order to control every vertex of a graph.
Cecilia Borg
Traffic on the Internet today is routed on the shortest path to the destination. This is considered as the quickest path but if traffic congestion occurs on the route, packets are dropped and the traffic slows down due to the retransmission of the missing packets. If the network resources could be more evenly utilised, some congestions could be avoided and the problem with retransmissions could be reduced. In order to balance the load evenly over a network, the load variation has to be known and predictable. Other studies of IP traffic have shown that a small number of flows carry the main part of the network traffic, these flows are referred to as elephants. This property is studied in this report and the stability of these flows is examined. By aggregating with respect to the source and destination network of the traffic, individual flows are easily identified. This report also discusses how to identify the large flows during runtime in order to use their properties when calculating the stability for the future traffic demand. The traffic prediction is based on analysis of logged Internet traffic. The report concludes that the phenomenon with elephant and mice flows can be observed when aggregating traffic artificially by different lengths of their network prefixes. When calculating future stability of flows the network aggregation does not have a major impact.
Jakub Orzechowski Westholm, Adam Ameur
The aim of this project was to investigate a combinatorial optimization problem stated by Global Genomics AB. The problem has its background in genomics, and is part of a new method for measuring gene expression levels. This method involves experiments as well as post processing of the experimental data. The experiments take a cell sample as input, and the output is incomplete information about the genes expressed in the sample. To estimate the gene expression levels from this information, it has to be matched with a gene database. Since the experimental data is incomplete, there are many possible matchings. The problem investigated in this project is to find the best matching between the experimental data and the gene database, using some different local search techniques.
Gabriel Paues
Bandwidth markets is an approach to achieve quality of service. By dividing capacity into shares, capacity may be traded between actors in a net. These actors are typically clients, that want to reserve capacity, and net operators offering capacity. To realize a bandwidth market, a number of components have to be implemented. This thesis describes the implementation of some of these components, those used by a net operator offering capacity on a bandwidth market. The features needed by a net operator are access control, shaping and routing. The components that implement those features are an access manager, a packet marker, a shaper and a label switch. To differentiate packets using reserved capacity from unreserved ones, parts of the IP header were used. The difficulties were to understand which parts of the IP header (TOS-field or flowlabel) and what version of the IP protocol (IPv4 or IPv6) to use. The components were tested in a testbed. This testbed used virtual Linux machines connected together to form an IP network.
Magnus Ågren
The increasing interest in Constraint Programming (CP) we now witness gives rise to a demand for new and improved debugging techniques. Graphical tools, such as constraint- and search-tree visualizers, seem to be appropriate to get a general understanding of the complex process of constraint solving. However, many such tools have been built in an ad hoc way, forcing the developer to, for each new tool, provide relevant information from the constraint solver. In this thesis, we present a solution to the problem, limiting ourselves to Constraint Logic Programming over Finite Domains (\clpfd). In order to do this, we come up with a trace structure for describing the execution of \clpfd\ programs in detail. The trace structure consists of various trace events, each trace event containing different information depending on when in the solving process it is created. Among other things, the trace structure contains information about constraint posting, constraint awakening and domain narrowing. We also incorporate explanations in the trace structure, i.e.\ reasons for why certain solver actions occur. Furthermore, we come up with a format for describing the execution of the filtering algorithms of global constraints. An implementation of the trace structure in \sicstus\ Prolog is also presented, as well as a tool using the trace; an extension to the ordinary Prolog debugger.
Laura Marie Feeney
This report describes a power save protocol for ad hoc networks.
Markus Bohlin, Lars Bruce
This master of science thesis describes a new design and its implementation for an Oz compiler. The project is based on the existing Oz compiler. The new compiler is designed more modular, with separate software components that can be replaced and modified locally. A prototype has been implemented, but further development is necessary. We give an overview of the language Oz, its features and the underlying calculus. The features of Oz regarding object orientation, functional programming, logic and constraint programming are also discussed. The liveness analysis and register allocation problems in general and regarding Oz specific compilers are analyzed, together with current and future optimizations suitable for the Mozart platform. The design of the new compiler and information about the old one is presented, and future work regarding the compiler, optimizations, and analysis phases is discussed. Appendices describing the interfaces between the phases of the compiler is included, together with documentation regarding the internal code formats used.
Markus Bohlin
The constraint satisfaction problem and its derivate, the propositional satisfiability problem (SAT), are fundamental problems in computing theory and mathematical logic. SAT was the first proved NP-complete problem, and although complete algorithms have been dominating the constraint satisfaction field, incomplete approaches based on local search has been successful the last ten years. In this report we give a general framework for constraint satisfaction using local search as well as an different techniques to improve this basic local search framework. We also give an overview of algorithms for problems of constraint satisfaction and optimization using heuristics, and discuss hybrid methods that combine complete methods for constraint satisfaction with local search techniques.
Sameh El-Ansary, Luc Onana Alima, Per Brand, Seif Haridi
Locating entities in peer-to-peer environments is a fundamental operation. Recent studies show that the concept of distributed hash table can be used to design scalable lookup schemes with good performance (i.e. small routing table and lookup length). In this paper, we propose a simple framework for deriving decentralized lookup algorithms. The proposed framework is simple in that it is based on the well-known concept of k-ary search. To demonstrate the applicability of our framework, we show how it can be used to instantiate Chord. When deriving a generalized Chord from our framework, we obtain better performance in terms of the routing table size (38% smaller than the generalization suggested by the Chord authors). END of example.
Juan Alonso, Henrik Abrahamsson, Bengt Ahlgren, Anders Andersson, Per Kreuger
We prove a result concerning objective functions that can be used to obtain efficient and balanced solutions to the multi-commodity network flow problem. This type of solution is of interest when routing traffic in the Internet. A particular case of the result proved here (see Corollary 2 below) was stated without proof in a previous paper.
Stina Nylander, Annika Waern
Porting computer games to new platforms can be a cumbersome work, since many parts of a game is platform specific. This is due to the fact that game developers try to maximise user's experience when playing a computer game, and to make the most of every device the game runs on. We use game and device independent interaction acts to describe user-game interaction for networked games that are accessed from many different devices. A device independent description of the game interactivity allows for remote access from different (semi)-generic interaction engines, as well as device optimisation for the same game application.
Anders Holst (editor)
The DALLAS ("application of Data AnaLysis with LeArning Systems") project has been designed to bring together groups using learning systems (e.g. artificial neural networks, non-linear multi-variate statistics, inductive logic etc) at five universities and research institutes, with seven companies with data analysis tasks from various industrial sectors in Sweden. An objective of the project has been to spread knowledge and the use of learning systems methods for data analysis in industry. Further objectives have been to test the methods on real world problems in order to find strengths and weaknesses in the methods and to inspire research in the area.
Stina Nylander, Markus Bylund
People want user interfaces to services that are functional and well suited to the device they choose for access. To provide this, services must be able to offer device specific user interfaces for the wide range of devices available today. We propose to combine the two dominant approaches to platform independence, "Write Once, Run Every-where™" and "different version for each device", to create multiple device specific user interfaces for mobile services. This gives possibilities to minimize the work with development and maintenance, while still keeping the control of how the user interface is presented to the end user. A calendar service has been implemented with user interfaces for Java Swing, HTML and std I/O.
Lars Rasmusson
We show that one can evaluate the cumulative probability density function m weighted sums of n correlated lognormal variables with Monte Carlo simulation rapidly, by deriving its joint probability density function. The adaptive Monte Carlo method allows us to estimate the number of rounds required to achieve a given tolerance. The need for evaluating this function rapidly occurs in many applications, for instance for pricing combinatorial options for bandwidth markets.
Lars Rasmusson
We describe a model of a communication network that allows us to price complex network services as financial derivative contracts based on the spot price of the capacity in individual routers. We prove a theorem of a Girsanov transform that is useful for pricing linear derivatives on underlying assets, which can be used to price many complex network services, and it is used to price an option that gives access to one of several virtual channels between two network nodes, during a specified future time interval. We give the continuous time hedging strategy, for which the option price is independent of the service providers attitude towards risk. The option price contains the density function of a sum of lognormal variables, which has to be evaluated numerically.
Lars Rasmusson, Erik Aurell
We describe a model of a network of N sub-networks (or routers) where M network users making concurrent point-to-point connections by selling and buying router capacity to and from each other. The resources need to be acquired in complete bundles, but there is only one spot market for each router, i.e. no way to place bids on complete bundles. In order to describe the internal dynamics of the market, we model the observed prices by N-dimensional Ito-processes. Modeling using stochastic processes is novel in this context of describing interactions between end-users in a system with shared resources, and allows a standard set of mathematical tools to be applied. The derived models is intended to price contingent claims on network capacity and thus to price complex network services such as, trading resource bundles, pricing quality of service levels, multicast service, etc.
Adam Dunkels
Over the last years, interest for connecting small devices such as sensors to an existing network infrastructure such as the global Internet has steadily increased. Such devices often has very limited CPU and memory resources and may not be able to run an instance of the TCP/IP protocol suite. In this thesis, techniques for reducing the resource usage in a TCP/IP implementation is presented. A generic mechanism for offloading the TCP/IP stack in a small device is described. The principle the mechanism is to move much of the resource demanding tasks from the client to an intermediate agent known as a proxy. In particular, this pertains to the buffering needed by TCP. The proxy does not require any modifications to TCP and may be used with any TCP/IP implementation. The proxy works at the transport level and keeps some of the end to end semantics of TCP. Apart from the proxy mechanism, a TCP/IP stack that is small enough in terms of dynamic memory usage and code footprint to be used in a minimal system has been developed. The TCP/IP stack does not require help from a proxy, but may be configured to take advantage of a supporting proxy.
Pablo Giambiagi
Mobile code technology offers interesting possibilities to the practitioner, but also raises strong concerns about security. One aspect of security is secrecy, the preservation of confidential information. This thesis investigates the modelling, specification and verification of secrecy in mobile applications which access and transmit confidential information through a possibly compromised medium (e.g. the Internet). These applications can be expected to communicate secret information using a security protocol, a mechanism to guarantee that the transmitted data does not reach unauthorized entities. The central idea is therefore to relate the secrecy properties of the application to those of the protocol it implements, through the definition of a ``confidential protocol implementation'' relation. The argument takes an indirect form, showing that a confidential implementation transmits secret data only in the ways indicated by the protocol. We define the implementation relation using labelled transition semantics, bisimulations and relabelling functions. To justify its technical definition, we relate this property to a notion of noninterference for nondeterministic systems derived from Cohen's definition of Selective Independency. We also provide simple and local conditions that greatly simplify its verification, and report on our experiments on an architecture showing how the proposed formulations could be used in practice to enforce secrecy of mobile code.
Martin Aronsson, Adina Jägbeck
Vi presenterar en studie som jämför två branscher där planeringsmetoder är en viktigt komponent för lyckad produktion. För en trafikutövare inom järnvägssektorn är resursplanering en mycket viktig komponent för effektiv produktion, och inom byggsektorn är produktionsplanering likaså en mycket viktig komponent för effektiva byggen. Studien är gjord med fokus på möjligheterna att överföra verktyg framtagna för järnvägsoperatörers re-sursplanering inom projektet TUFF på SICS till planeringssituationen som den ser ut på byggsidan. Resultatet av studien är att de två branscherna planerar på olika sätt, framför allt skiljer ut-gångspunkten för planering: för trafikoperatören är framför allt resurserna styrande för plane-ringen, medan för byggaren är produkten styrande för planeringen. Vidare är planerna för trafikoperatören oftast cykliska och återkommande medan för byggaren är de specifika för en viss produkt eller del av produkt. Mot bakgrund av detta kan vi konstatera att de specifika planeringsmodeller som tagits fram i TUFF inte har en omedelbar och rättfram användning inom byggprojektplaneringen. Detta arbete finansierades av NUTEK och VINNOVA genom programmet Komplexa system under 1999-2001.
Waldemar Kocjan
A locomotive assignment is one of the subproblems in railway scheduling domain. In this report present general mathematical model of this specific subproblem and describe how methods known from other problems domain like traveling salesman problem, operation research and constraint programming can be used to solve it. We concentrate especially on method known as {\it k--interchange} for traveling salesman problem with time windows and give an outline how it can be adopted to locomotive assignment problem. Further, while turning from one trip to another a locomotive must often be reallocated from one station to another. This can be performed in two ways. A locomotive can be driven from one place to another not performing any specific trip and exclusively using track resource, i.e. performs so called deadhead transport, or can be attached to any other transport and passively drown to another station, i.e. perform so called passive transport. Because the cost of passive transport is much lower then cost of a deadhead it is advantageous to, if possible, replace any deadhead by passive transport. In this report we describe a method of converting deadheads into passive transports, describe conversion algorithm, its implementation and report computational result of the algorithm. Finally, we give directions for future research in locomotive planning problem domain.
Lars Albertsson
This is a state of the art report and literature overview of practical methods for constructing and analysing real-time systems. It covers operating system support, monitoring methods, and execution time prediction through simulation.
Nicolas Beldiceanu, Mats Carlsson
We describe a set of necessary conditions that are useful for generating propagation algorithms for the cardinality operator as well as for over-constrained problems with preferences. Constructive disjunction as well as the entailments rules originally proposed for the cardinality operator can be seen as simple cases of these necessary conditions. In addition these necessary conditions have the advantage of providing more pruning.
Per Kreuger, Mats Carlsson, Thomas Sjöland, Emil Åström
A constraint model for scheduling train trips on a network of tracks used in both directions, using a headway abstraction is described. We argue that a generalisation of a straightforward job-shop scheduling formulation using sequence dependent task extensions can decrease the required resolution of network representation and hence problem size. A geometric interpretation of the model of the constraints that can be used to visualise schedules is presented. Preliminary ideas on search heuristics are presented with performance results and a set of examples.
Nicolas Beldiceanu, Mats Carlsson
We first present a generic pruning technique which aggregates several constraints sharing some variables. The method is derived from an idea called \dfn{sweep} which is extensively used in computational geometry. A first benefit of this technique comes from the fact that it can be applied on several families of global constraints. A second main advantage is that it does not lead to any memory consumption problem since it only requires temporary memory that can be reclaimed after each invocation of the method. We then specialize this technique to the non-overlapping rectangles constraint, describe several optimizations, and give an empirical evaluation based on six sets of test instances of different pattern.
Nicolas Beldiceanu, Qi Guo, Sven Thiel
This paper deals with non-overlapping constraints between convex polytopes. Non-overlapping detection between fixed objects is a fundamental geometric primitive that arises in many applications. However from a constraint perspective it is natural to extend the previous problem to a non-overlapping constraint between two objects for which both positions are not yet fixed. A first contribution is to present theorems for convex polytopes which allow coming up with general necessary conditions for non-overlapping. These theorems can be seen as a generalization of the notion of compulsory part which was introduced in 1984 by Lahrichi and Gondran [6] for managing non-overlapping constraint between rectangles. Finally, a second contribution is to derive from the previous theorems efficient filtering algorithms for two special cases: the non-overlapping constraint between two convex polygons as well as the non-overlapping constraint between d-dimensional boxes.
Nicolas Beldiceanu, Mats Carlsson
This paper presents a new cumulatives constraint which generalizes the original cumulative constraint in different ways. The two most important aspects consist in permitting multiple cumulative resources as well as negative heights for the resource consumption of the tasks. This allows modeling in an easy way new scheduling and planning problems. The introduction of negative heights has forced us to come up with new propagation algorithms and to revisit existing ones. The first propagation algorithm is derived from an idea called sweep which is extensively used in computational geometry; the second algorithm is based on a combination of sweep and constructive disjunction, while the last is a generalization of task intervals to this new context. A real-life timetabling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.
Henrik Abrahamsson, Ian Marsh
Dynamic Transfer Mode (DTM) is a ring based MAN technology that provides a channel abstraction with a dynamically adjustable capacity. TCP is a reliable end to end transport protocol capable of adjusting its rate. The primary goal of this work is investigate the coupling of dynamically allocating bandwidth to TCP flows with the affect this has on the congestion control mechanism of TCP. In particular we wanted to find scenerios where this scheme does not work, where either all the link capacity is allocated to TCP or congestion collapse occurs and no capacity is allocated to TCP. We have created a simulation environment using ns-2 to investigate TCP over networks which have a variable capacity link. We begin with a single TCP Tahoe flow over a fixed bandwidth link and progressively add more complexity to understand the behaviour of dynamically adjusting link capacity to TCP and vice versa.
Per Persson, Jussi Karlgren, Panu Korhonen, Janet Galore, Mark Tierney, Chad Redmon, Juha Hemanus, Peter Lönnqvist, Jarmo Laaksolahti
We present a design for expressive multimodal messaging on mobile platforms. Strong context, simple text messages, and crude animations combine well to produce surprisingly expressive results.
Fredrik Espinoza, Per Persson, Anna Sandin, Hanna Nyström, Elenor Cacciatore, Markus Bylund
Location-based information systems allow the user to access information in relation to the user's position in geographical space. This paper outlines navigational and social aspects of such systems. It is argued that location-based systems must allow users to participate as content providers in order to achieve a social and dynamic information space. Moreover, as these systems allow commercial and private users to annotate space with information on a mass-scale, information filtering techniques will become essential in order to prevent information overload and user disturbance. We present a number of content-based and social filtering techniques to support this. We discuss implications for implementation and we describe a system (GeoNotes), which takes some of these aspects into account.
Markus Bylund, Annika Waern
We describe an approach for mobile and personalized use of electronic services that meet very high requirements on openness, user control, and mobility. The design is centered on the concept of personal service environments. These offer users mobile and network independent access to services from many different types of devices. The concept also allows services to interact locally. This can be used in several ways: services can for example share information but also make use of each other's services. In particular, we want to use this to support service personalization. The design has been successfully implemented and tested with a number of sample services and in several related research projects. This implementation, the sView system, is described.
Markus Bylund
This report presents an architecture overview and a system description of the sView system. The system provides developers, service providers, and users of electronic services with an open and extendible service infrastructure that allows far-reaching user control. This is accomplished by collecting the services of an individual user in a virtual briefcase. Services come in the form of self-contained service components (i.e. including both logic and data), and the briefcase is mobile to allow it to follow as the user moves between different hosts and terminals. A specification of how to build such service components and the infrastructure for handling briefcases is presented. A reference implementation of the specification as well as extensions in the form of service components is also described. The purpose of the report is to serve as a technical reference for developers of sView services and software infrastructure that builds on sView technology.
Per Kreuger, Martin Aronsson, Simon Lindblom
This paper explores the idea of using formalised abstraction as means of describing various operations on structured representations of planing, scheduling and resource allocation problems. We define a notion of structures on tasks, relations and resources. Each task consists of task parameters and an inductively defined substructure. The task parameters denote domain variables constrained by the relations of the structure while resources formalises resource constraints, typically presupposing the semantics of some global constraint. A notion of consistency of such structures is briefly outlined. We go on characterise properties of safeness and certain conservation properties on operations We claim that such properties are relevant to problem domains where tasks on several different types or levels of resources has to scheduled simultaneously or by partitioning the problem into several subproblems that has then to be coordinated. Finally we present, in some detail, a model of such a problem from the rail transport industry formalised as several task structures. We show how operations on these can be seen as solvers for the various subproblems but also used to transform a specification or a solution of one subproblem into a specification of an other one. We claim that properties of such operations can be used to characterise reasoning in coordination problems.
Martin Aronsson, Per Kreuger
We present a crew scheduling problem with time windows in the context of scheduling train personnel, which encompasses not only assignment of resources to tasks but also the introduction of extra tasks, passive journeys, depending on the problem instance. The representation of the problem is made as a constraint program, which relies heavily on some global constraints, notably a constraint for expressing non-overlap between rectangles on a surface. A search algorithm is described and we also point out some problems and deficiencies of the current model and its computational behaviour.
Fredrik Bromeé
This report aims to give an overview of software and hardware platforms available now or in the near future for building a prototype of an ExMS application (for an overview of the ExMS project, see Appendix). The report also gives an overview of the different technologies for building third-party mobile client software applications that are in use today. The report is composed of three sections. The first section is a general discussion on mobile client software and the different technologies that can be used to develop third-party mobile client software. The next section continues with a specific discussion on ExMS and answers the following questions: What is the general architecture of the ExMS application? What alternatives exist for implementing the ExMS prototype? The final section of the report is a recommendation of hardware and software platform for building the ExMS prototype.
Adrian Bullock, Per Gustafson
In this report we present our findings and results from the VITI program in 2000. The focus of the research work undertaken by VITI has been to provide electronic meeting environments that are easy to use and afford as natural a collaboration experience as possible. This final report is structured into three parts. Part one concerns the VITI infrastructure and consists of two sections. The first section describes the process of establishing the infrastructure, concentrating on how the work was done. The second section presents the actual infrastructure that is in place today, concentrating on what has been put in place. Part two examines the use the VITI infrastructure has been put to, giving examples of activities it has supported and discussing strengths and weaknesses that have emerged through this use. Finally part three considers the future of distributed electronic meeting environments. It is recommended that the report be read in the order in which it is presented. However, each section has been written as a standalone document and can be read independently of the others.
Henrik Nässen
The Swedish Institute of Computer Science (SICS) is the vendor of SICStus Prolog. To decrease execution time and reduce space requirements, variants of SICStus Prolog's virtual instruction set were investigated. Semi-automatic ways of finding candidate sets of instructions to combine or specialize were developed and used. Several virtual machines were implemented and the relationship between improvements by combinations and by specializations were investigated. The benefits of specializations and combinations of instructions to the performance of the emulator is on the average of the order of 10%. The code size reduction is 15%.
Mattias Östergren
Ad hoc networks are mobile wireless networks which do not have any kind of fixed infrastructure. The routing layer in an ad hoc network ties the network together into a seamless entity and provide transparent services to higher layer protocols. This thesis examines the interactions of two routing protocols, AODV and DSR and how the mobile ad hoc network environment affect TCP performance. The results presented here are as follows: the path length and the presence of competing traffic are the main factors of TCP throughput performance. The size of TCP window affects the loss rate, but the loss rate is not strongly correlated to throughput performance. Using TCP selective acknowledgement option does not improve throughput. Finally, there is hardly any difference in TCP throughput when using DSR and AODV. These conclusions are supported by extensive simulation experiments.
Per Holmberg
This thesis investigates how abstractions can be used to improve performance in a railroad scheduling system that uses constraint programming. The idea behind abstractions is to solve a large problem in smaller parts and extract information from these parts. That information can then be used when solving the entire problem. Two different types of abstractions are introduced: Relations and Net abstractions. The use of relations builds orders between trips or parts of trips. These orders can be used to reduce the search necessary to find a solution to the scheduling problem. When using net abstraction, the problem is solved in an abstract search space, where it is easier to solve. The solution computed in the abstract search space is then used to reduce search when solving the problem in the original space. It is shown that these two types of abstraction can improve performance in problems with various settings. Relations can successfully be used in problems that have few solutions and are hard to solve. Net abstraction on the other hand works best for problems with many valid solutions.
Report number was reserved June 2000. No report was produced.
Nicolas Beldiceanu
This paper presents generic propagation algorithms for the cardinality-path constraint family. This is a restricted form of the cardinality operator that allows stating constraints on sliding sequences of consecutive variables. Taking advantage of these restrictions permits coming up with more efficient algorithms. Moreover the paper shows how to extend these propagation algorithms in order to partially integrate external constraints that have to hold. From an application point of view the cardinality-path constraint allows to express a huge variety of regulation constraints occurring in personnel planning problems. This revised edition of the SICS report T2000/11 incorporates one correction as well as some minor improvements.
Nicolas Beldiceanu
The paper presents propagation rules that are common to the minimum constraint family and to the number of distinct values constraint family. One original contribution is to provide a geometrical interpretation of these rules that can be used by a generic sweep pruning algorithm. Finally one practical interest of the paper is to describe an implementation of the number of distinct values constraint. This is a quite common counting constraint that one encounters in many practical applications such as timetabling or frequency allocation problems.
Bengt Ahlgren, Anders Andersson, Olof Hagsand, Ian Marsh
Transmitting telephone calls over the Internet causes problems not present in current telephone technology such as packet loss and delay due to queueing in routers. In this undergraduate thesis we study how a Markov modulated Poisson process is applied as an arrival process to a multiplexer and we study the performance in terms of loss probability. The input consists of the superposition of independent voice sources. The predictions of the model is compared with results obtained with simulations of the multiplexer made with a network simulator. The buffer occupancy distribution is also studied and we see how this distribution changes as the load increases.
Nicolas Beldiceanu
This report presents a generic pruning technique that aggregates several constraints sharing some variables. The method is derived from an idea called sweep that is extensively used in computational geometry. A first benefit of this technique comes from the fact that it can be applied on several families of global constraints. A second main advantage is that it does not lead to any memory consumption problem since it only requires temporary memory that can be reclaimed after each invocation of the method. This technique has been used inside the SICStus finite domain solver in order to implement several global constraints.
Per Kreuger, Martin Aronsson, Per Holmberg, Simon Lindblom
I arbetet med att modellera ett produktionsplaneringsproblem i järnvägsindustrin har vi identifierat ett antal metoder och tekniker som vi hävdar är användbara även utanför järnvägsdomänen. I denna rapport presenterar vi kort problemställningarna i järnvägsdomänen, presenterar de viktigaste av de tekniker vi identifierat, använt och utvecklat samt indikerar en del andra problemdomäner för vilka vi bedömer att dessa tekniker skulle kunna användas.
Martin Aronsson, Per Kreuger, Simon Lindblom, Per Holmberg
TUFF är ett verktyg för strategisk planering av tågrörelser och resursomlopp (f.n. lok). Det unika med TUFF är inte att kunna utföra dessa planeringar var för sig, utan att de kan samverka. Detta är möjligt dels genom att de ingående komponenterna kan hantera vagare data, t.ex. tidsintervall i stället för fasta tider vilket är det vanliga annars bland kommersiella lösningar, dels att det finns en samordningsfunktion, som vi kallar samordningsagent, som samordnar olika planer från olika planeringsfunktioner. Denna samordnare är programmerbar via ett speciellt språk, så att ett stort problem kan splittras upp i mindre delar, och resultat från olika planeringar av dessa delar kan sedan kombineras och nya resultat genereras. Tanken med denna integrering av olika planeringsfunktioner är att åstadkomma globalt bättre lösningar, jämfört med när varje problem löses var för sig, genom att ta hänsyn till varje planeringsproblems krav tidigt i planeringscykeln.
Volker Scholtz
This report describes a study done as a masters thesis during 1998 within the Complex Operations Laboratory (COL) at SICS. The report describes a vehicle routing and scheduling problem occurring in the planning of rail traffic at the Swedish State Railways (SJ). The report contains a comprehensive description of the problem and describes several techniques that can be used to address the problem: Constraint Programming with a particular model (due to Helmut Simonis) of the routing problem. This model requires an efficient implementation of a particular called global constraint: the geometric diffn constraint. A propagation algorithm for a 2-dimensional version of this constraint is outlined in the report. The use of insertion heuristics to solve this class of problems have been in general use for some time. And adaption and evaluation of some of these heuristics are also analyzed in the report.
Kristofer Franzen, Jussi Karlgren
Users pose very short queries to information retrieval systems. This study shows that the apparent length of the query field has an effect on the length of the query users enter.
Anders Andersson
Transmitting telephone calls over the Internet causes problems not present in current telephone technology such as packet loss and delay due to queueing in routers. In this undergraduate thesis we study how a Markov modulated Poisson process is applied as an arrival process to a multiplexer and we study the performance in terms of loss probability. The input consists of the superposition of independent voice sources. The predictions of the model is compared with results obtained with simulations of the multiplexer made with a network simulator. The buffer occupancy distribution is also studied and we see how this distribution changes as the load increases.
No report was produced.
Nicolas Beldiceanu
This report introduces a classification scheme for the global constraints. This classification is based on four basic ingredients from which one can generate almost all existing global constraints and come up with new interesting constraints. Global constraints are defined in a very concise way, in term of graph properties that have to hold, where the graph is a structured network of same elementary constraints. Since this classification is based on the internal structure of the global constraints it is also a strong hint for the pruning algorithms of the global constraints.
Laura Marie Feeney
This report describes a series of simple experiments which measure the per-packet energy consumption of an IEEE 802.11 wireless network interface. The goal of this work is to develop a solid experimental basis for assumptions that can (or cannot) be made in the design and analysis of network protocols operating in the ad hoc wireless environment.
Majid Zandieh
The growth of the Internet in recent years has led to an enormous increase of the number of routing table entries. Address tables in IP routers require efficient and compact implementation to allow fast lookup of IP addresses. One solution for fast address lookup in software is to use the LC-trie data stucture. The search depth for the LC-trie increases slowly as function of the number of entries. This master thesis discusses the performance of the fast address lookup in the LC-trie algorithm. The main focus of this master thesis is to use the instruction set simulator, SimICS for performance evaluation of the address lookup in the LC-trie algorithm. The address lookup is performed for 100000 addresses in a LC-trie. The results are measured in terms of number of memory accesses and number of executed instruction per address lookup.
Björn Gambäck
The essay describes some of the main problems which meet us when trying to process human language on a computer. The overall approach is to look at what we would need to do in order to be able to build a device with the same general functionality as Douglas Adams' Babel fish. That is, a device which can take utterances spoken in one language and instantly translate them into speech in some other language.
Stefan Arnborg
This tutorial summarises the use of Bayesian analysis and Bayes factors for finding significant properties of discrete (categorical and ordinal) data. It overviews methods for finding dependencies and graphical models, latent variables, robust decision trees and association rules.
Laura Marie Feeney
A Mobile Ad hoc NETwork (manet) is a mobile, multi-hop wireless network which is capable of autonomous operation. It is characterized by energy-constrained nodes, bandwidth-constrained, variable-capacity wireless links and dynamic topology, leading to frequent and unpredictable connectivity changes. In the absence of a fixed infrastructure, manet nodes cooperate to provide routing services, relying on each other to forward packets to their destination. Routing protocols designed for the fixed network are not effective in the dynamic and resource-constrained manet environment; many alternative routing protocols have been suggested. This report provides an overview of a number of manet routing protocols. More importantly, it defines a taxonomy that is suitable for examining a wide variety of protocols in a structured way and exploring tradeoffs associated with various design choices. The emphasis is on practical design and implementation issues rather than complexity analysis.
Kent Saxin Hammarström
The present thesis is an overview and survey of interaction with real-time, text-based, multi-user systems, especially MUD systems, by persons with disablements. It is argued that these types of systems could be excellent "social tools" for those who cannot participate in social and leisure activities as easily as users without disablements. Based on the exploratory studies of two groups of such users, documented in this thesis, a preliminary conclusion is that one of the major software interface problems is information overload. The second major problem is that information is not always presented in the most appropriate mode for a particular disablement, and thus interaction does not take place in the most appropriate modality. Above all, this is a "white paper" or vision document, proposing one philosophy for developing augmentative and alternative communication systems. This philosophy has three main foci: Firstly, let the user/consumer, not the producer, decide how information is presented and how interaction is to take place. Secondly, explore minimal solutions that use existing services and that do not require the user to acquire new equipment, both to minimise disruptions in how the user normally does things, to minimise the cost, and to avoid creating special purpose systems instead of integrating with existing services. Lastly, be visionary. Instead of correcting things that do not work, try to create solutions that take disablements into account from the very start ("universal design"). We believe this to be absolutely necessary if we are to avoid the current situation where users with disablements always are one step behind in terms of technological developments. This philosophy together with the results from the pilot studies has resulted in our vision of a solution: Intermodal systems. An intermodal system is our extension of multimodal systems, where the "intelligent presentation" of information is augmented with "intelligent analysis." This means that information that arrives to the system tied to a particular representation/mode is analysed into a form that lends itself to presentation and interaction in whatever modality the user chooses. This solution has been partially implemented in the form of prototypes for the core system and for information extraction from text.
Henrik Abrahamsson
Measurement and analysis of real traffic is important to gain knowledge about the characteristics of the traffic. Without measurement, it is impossible to build realistic traffic models. It is recent that data traffic was found to have self-similar properties. In this thesis work traffic captured on the network at SICS and on the Supernet, is shown to have this fractal-like behaviour. The traffic is also examined with respect to which protocols and packet sizes are present and in what proportions. In the SICS trace most packets are small, TCP is shown to be the predominant transport protocol and NNTP the most common application. In contrast to this, large UDP packets sent between not well-known ports dominates the Supernet traffic. Finally, characteristics of the client side of the WWW traffic are examined more closely. In order to extract useful information from the packet trace, web browsers use of TCP and HTTP is investigated including new features in HTTP/1.1 such as persistent connections and pipelining. Empirical probability distributions are derived describing session lengths, time between user clicks and the amount of data transferred due to a single user click. These probability distributions make up a simple model of WWW-sessions.
Mats Carlsson, Greger Ottosson
We investigate different solution techniques for solving a basic part of configuration problems, namely linear arithmetic constraints over integer variables. Approaches include integer programming, constraint programming over finite domains and hybrid techniques. We also discuss important extensions of the basic problem and how these can be accommodated in the different solution approaches.
Fredrik Olsson
This thesis describes the work of providing separate morphological processing and part-of-speech tagging modules in the SVENSK system by integrating the Uppsala Chart Processor (UCP) and a Brill tagger into the system. SVENSK employs GATE (General Architecture for Text Engineering) as the platform in which the components are to be integrated. Two pre-processing modules, a tokeniser and a sentence splitter for Swedish, were developed in order to facilitate the preparation of the texts to be analysed by UCP and the Brill tagger. These four components were then integrated in GATE together with a newly developed viewer for displaying the results produced by UCP. The thesis introduces the reader to the SVENSK project, the GATE system and its underlying parts, especially the database architecture which is based on the TIPSTER annotation model. Further, the issues in connection with the development and design of the tokeniser and the sentence splitter for Swedish are elaborated on. The mechanisms behind transformation-based error-driven learning methods as employed by the Brill tagger are introduced as well as the principles of chart processing in general and UCP in particular. The greater part of the thesis is devoted to the process of integrating the natural language (NL) modules in GATE using the Tcl/Tk application programmers interface (API) and a so-called loose coupling. The results of the integration of the NL modules are very encouraging: it is possible to mix modules written in programming languages from completely different paradigms (in this case the languages are Common LISP, Perl and C) and to have them interact with each other, thus maintaining a high degree of reuse of algorithmical resources. However, the use of Tcl/Tk and the associated API for processing structurally relatively complex data, i.e. the output from UCP, is time consuming and considerably slows the processing in GATE.
Anette Hulth, Anna Jonsson
Within the framework of the Digital Library project at SICS, this thesis describes the implementation of a demonstrator prototype of a digital library (DigLib); an experimental platform integrating several functions in one common interface. It includes descriptions of the structure and formats of the digital library collection, the tailoring of the search engine Dienst, the construction of a keyword extraction tool, and the design and development of the interface. The platform was realised through sicsDAIS, an agent interaction and presentation system, and is to be used for testing and evaluating various tools for information seeking. The platform supports various user interaction strategies by providing: search in bibliographic records (Dienst); an index of keywords (the Keyword Extraction Function (KEF)); and browsing through the hierarchical structure of the collection. KEF was developed for this thesis work, and extracts and presents keywords from Swedish documents. Although based on a comparatively simple algorithm, KEF contributes by supplying a long-felt want in the area of Information Retrieval. Evaluations of the tasks and the interface still remain to be done, but the digital library is very much up and running. By implementing the platform through sicsDAIS, DigLib can deploy additional tools and search engines without interfering with already running modules. If wanted, agents providing other services than SICS can supply, can be plugged in.
Jesper Eskilson
The development of intelligent software agents and other complex applications which continuously interact with their environments has been one of the reasons why explicit concurrency has become a necessity in a modern Prolog system today. Such applications need to perform several tasks which may be very different with respect to how they are implemented in Prolog. Performing these tasks simultaneously is very tedious without language support. This paper describes the design, implementation and evaluation of a prototype multithreaded execution environment for SICStus Prolog. The threads are dynamically managed using a small and compact set of Prolog primitives implemented in a portable way, requiring almost no support from the underlying operating system.
Annika Waern, Mark Tierney, Åsa Rudström, Jarmo Laaksolahti
In this paper, we present new types of web information services, where users and information brokers collaborate in creating a user-adaptive information service. Such services impose a novel task on information brokers: they become responsible for maintaining the inference strategies used in user modeling. In return, information brokers obtain more accurate information about user needs, since the adaptivity ensures that user profiles are kept up to date and consistent with what users actually prefer, not only what they say that they prefer. We illustrate the approach by an example application, in which conference calls are collected and distributed to interested readers.
Dilian Gurov, Bruce Kapron
We consider proof systems with sequents of the form U |- F for proving validity of a propositional modal mu-calculus formula F over a set U of states in a given model. Such proof systems usually handle fixed-point formulae through unfolding, thus allowing such formulae to reappear in a proof. Tagging is a technique originated by Winskel for annotating fixed-point formulae with information about the proof states at which these are unfolded. This information is used later in the proof to avoid unnecessary unfolding, without having to investigate the history of the proof. Depending on whether tags are used for acceptance or for rejection of a branch in the proof tree, we refer to ``positive'' or ``negative'' tagging, respectively. In their simplest form, tags consist of the sets U at which fixed-point formulae are unfolded. In this paper, we generalise results of earlier work by Andersen, Stirling and Winskel which, in the case of least fixed-point formulae, are applicable to singleton U sets only.
Kristina Höök, ed., Alan Munro, ed., David Benyon, ed.
The workshop was organized in association with IFIP working group WG13.2 and the Navigation SIG of Esprit's i-net, Information Intelligence Interfaces network of excellence.
Nils Dahlbäck, ed.
This document is a slightly revised version of Deliverable 1.1.1 of the PERSONA project, submitted to the European Commission in February 1998. Only typographic errors have been corrected, leading to some changes in the lay-out of the individual pages. The contents and the general lay-out of the individual chapters, including their length are, however, the same as in the original document. PERSONA is an acronym for PERsonal and SOcial NAvigation. The name of the project illustrates its two-fold approach; studying the individual cognitive, social and cultural differences in navigational ability and recognizing that computer users are social beings in interacting with other people as they make their way through information spaces. Based on this understanding we are developing new approaches to interactive system design. One of these is to identify how and where we can adapt to the individual person's needs. At the same time we are developing alternative approaches to system design, breaking away from the lonely 'walker in the woods' picture of the information system user, to a social being able to interact with other users and so get help in achieving their goals. In this first deliverable from the project, we present a comprehensive review of literature which we see as having an impact on navigation in information space. This volume contains a number of individual and co-authored papers covering various aspects of geographic and electronic spaces and on navigation in geographic and electronic spaces; Individual and cultural differences; Social aspects of navigation; Design based on alternative or complimentary approaches that we believe hold the promise of making interfaces and systems more navigable. Keywords: Navigation, social navigation, individual differences, cultural differences, design, electronic spaces, information spaces
Daniel Fredholm
This paper consists of a review and comparison between Z/EVES and PVS--two tools designed for analyzing formal specifications. Z/EVES is a tool for analyzing specifications written in Z. PVS is a general theorem prover for a language that consists of higher order logic together with set theory. The review has its focus on the possibility to use these tools in an industrial context. The plan for the review was to get acquainted with the tools on a general level and then to use them to partially validate a formal specification of requirements for the safety function of railway signaling systems. The conclusion is that PVS is clearly superior to Z/EVES. PVS has such a good performance that it can be recommended for industrial use in the area of formal methods. Concerning Z/EVES, its applicability seems more restricted.
Preben Hansen
Information seeking is an dynamic and interactive process. Factors like users' information needs, individual differences, goals and tasks, knowledge and cognitive abilities etc. influence the information seeking process, and need to be identified and supported in the user interface design. We adopt a user-centered approach to establish a link between research within the IR interaction perspective and the methods in HCI on how to evaluate information seeking interaction in a hypertext IR system (Dienst). Our purpose with this exploratory study is to identify, describe and acquire knowledge of characteristics of the user population, and finally, to make suggestions for supporting users in user interface design. For the evaluation task, we have applied HCI evaluation techniques to our IR evaluation to make a connection between the traditional IR evaluation and HCI evaluation, combining different qualitative and quantitative data collection and analyzing methods, implemented in an experimental real-world online WWW setting. This methodology combined online (WWW-based) questionnaires and database log statistics. Preliminary results revealed several "hidden" realities: a mismatch between what people said they wanted to do as opposed to what they actually did. We also observed that people initially expected a specific function, but when using the system, they did not use it. Finally, we established some group differences concerning variables like previous experience searching information in hypertext systems, IR knowledge and browsing/searching strategies.
Peter S. Magnusson, Johan Montelius
Instruction-set simulators allow programmers a detailed level of insight into, and control over, the execution of a program, including parallel programs and operating systems. In principle, instruction set simulation can model any target computer and gather any statistic. Furthermore, such simulators are usually portable, independent of compiler tools, and deterministic-allowing bugs to be recreated or measurements repeated. Though often viewed as being too slow for use as a general programming tool, in the last several years their performance has improved considerably. We describe SIMICS, an instruction set simulator of SPARC-based multiprocessors developed at SICS, in its rôle as a general programming tool. We discuss some of the benefits of using a tool such as SIMICS to support various tasks in software engineering, including debugging, testing, analysis, and performance tuning. We present in some detail two test cases, where we've used SimICS to support analysis and performance tuning of two applications, Penny and EQNTOTT. This work resulted in improved parallelism in, and understanding of, Penny, as well as a performance improvement for EQNTOTT of over a magnitude. We also present some early work on analyzing SPARC/Linux, demonstrating the ability of tools like SimICS to analyze operating systems. (NOTE: A later version of this report was published in ILPS'97)
Fredrik Larsson
A simulator is a powerful tool for hardware as well as software development. However, implementing an efficient simulator by hand is a very labour intensive and error-prone task. This paper describes a tool for automatic generation of efficient instruction set architecture (ISA) simulators. A specification file describing the ISA is used as input to the tool. Besides a simulator, the tool also generates an assembler and a disassembler for the architecture. We present a method where statistics is used to identify frequently used instructions. Special versions of these instructions are then created by the tool in order to speed up the simulator. With this technique we have generated a SPARC V8 simulator which is more efficient than our hand-coded and hand-optimized one.
Daniel Adler
Three-dimensional interactive audio has a variety of potential uses in human-machine interfaces. After lagging seriously behind the visual components, the importance of sound is now becoming increas-ingly accepted. This paper mainly discusses background and techniques to implement three-dimensional audio in computer interfaces. A case study of a system for three-dimensional audio, implemented by the author, is described in great detail. The audio system was moreover integrated with a virtual reality system and conclusions on user tests and use of the audio system is presented along with proposals for future work at the end of the paper. The thesis begins with a definition of three-dimensional audio and a survey on the human auditory system to give the reader the needed knowledge of what three-dimensional audio is and how human auditory perception works. ---------------
Torkel Franzen
The report presents a decision procedure for assertions in an extension of the mu-calculus about finite-control pi-calculus agents. The procedure is based on the classical cut-free sequent calculus and associated techniques of automatic theorem proving.
Kristian T. Simsarian, Thomas J.Olson, N. Nandhakumar
This paper addresses the problem of mobile robot self-localization given a polygonal map and a set of observed edge segments. The standard approach to this problem uses interpretation tree search with pruning heuristics to match observed edges to map edges. Our approach introduces a preprocessing step in which the map is decomposed into 'view-invariant regions' (VIRs). The VIR decomposition captures information about map edge visibility, and can be used for a variety of robot navigation tasks. Basing self-localization search on VIRs greatly reduces the branching factor of the search tree and thereby simplifies the search task. In this paper we define the VIR decomposition and give algorithms for its computation and for self-localization search. We present results of simulations comparing standard and VIR-based search, and discuss the application of the VIR decomposition to other problems in robot navigation.
Annika Waern , Ola Stenborg
When applying plan recognition to Human - Computer Interaction, one must cope with users exhibiting a large amount of reactive behaviour: users that change tasks, or change strategies for achieving tasks. Most current approaches to keyhole plan recognition do not address this problem. We describe an application domain for plan recognition, where users exhibit reactive rather than plan-based behaviour, and where existing approaches to plan recognition do not perform well. In order to enable plan recognition in this domain, we have developed an extremely simplistic mechanism for keyhole plan recognition, "intention guessing". The algorithm is based on descriptions of observable behaviour, and is able to recognize certain instances of plan failures, suboptimal plans and erroneous actions. At run-time, the algorithm only keeps track of a limited number of the most recent actions, which makes the algorithm "forgetful". This property makes the algorithm suitable for domains where users frequently change strategies.
Robert P. Nilsson, Kent S. Saxin Hammarström
This thesis proposes a two-dimensional, visual, direct manipulation query language intended to be used as an alternate modality to natural language in a multimodal interface. The language focuses on the visualisation of the logic of queries, and is intended to be flexible, extensible, and to have at least the expressive power of first order predicate logic with constraints. The language provides a basis for future inclusion of higher order logic (and thus a framework for database navigation with the language itself), DBMS features, and generalised quantifiers. As far as we have been able to judge, no such visual language of equal expressive power already exists. A "proof of concept" prototype has been implemented that illustrates some of the key concepts of the language.
No report was produced.
No report was produced.
Jussi Karlgren
User models are a tool for guiding system behavior in interactive systems, and their utility and properties, desirable and undesirable, have been investigated in this context. There are several ways of utilizing information about the user that have NOT been implemented, however. In this paper a scheme for users to peek at other users' user models to extract information is proposed, in an information retrieval or information filtering domain. The material used for the study is a set of .newsrc files.
Jose Luis Vivas
The purpose of this thesis is to design and validate a telephony system using the formal description language LOTOS and a series of tools provided by the Lotosphere Integrated Tool Environment, LITE. The starting point is a requirements document containing a series of informal specifications of services common to modern telephony systems. Special emphasis has been laid on choosing a design that simplifies the integration of additional telephone services in the specification. Most design decisions were thus taken with the purpose of creating an environment that could help different designers to develop distinct functionalities without the need for each one to be acquainted with other existing features in the system. To this end, the design was structured in a fashion that might enhance the extensibility of the system, as well as prevention and detection of incompatibilities between different features. A methodology is thus proposed for dealing with what is commonly known as the feature interaction problem for telephony systems.
No report was produced.
Jussi Karlgren
This paper suggests a scheme for raising the cooperativeness of natural language interfaces without changing either modality or system linguistic competence, but by heightening the level of interactivity and by aiding the user in maintaining the responsibility for the discourse. In short: hands-off-pragmatics at the computer interface.
Peter Magnusson
Traditional simulation of a target architecture by interpreting object code can be improved by translating the object code to an intermediate format. This approach is called interpretive translation. Despite a substantial performance improvement over traditional interpretation, a large part of the overhead is unnecessary. An alternative approach is block translation, where one or more simulated instructions are translated to directly executable code. This approach has several drawbacks. We discuss the problems with block translation, analyse the overhead of interpretive translation, and describe a hybrid approach-partial translation-that combines the benefits of both approaches. Partial translation implements an intermediate format that supports the addition of run-time generated code whenever appropriate. The perfor- mance limit (slowdown) of interpetive translation is around 15, and real implementations have achieved 20-30. Partial translation will perform considerably better. Finally, we present results from an aggressive implementation of interpretive translation, and results from a proof-of-concept implementation of partial translation.
Magnus Nordstroem, Paul Pettersson
There have been several attempts to realize the idea of a fully automatic translation system for text translation to replace human translators. By contrast, little work has been put into building tools to aid human translators. This report describes the ideas behind such a tool. The tool is intended to aid human translators in achieving higher productivity and better quality, by presenting terminological information extracted from previous translations. The report documents the implementation and evaluation of a prototype. The prototype has been demonstrated to and used by professional translators with promising results.
Roger Palmersjö
A prototype uniform graphical interface to verification tools is presented. Tools and data objects are displayed as icons in a working area. Tools can be connected with pipes to provide automatic data flow. The implementation runs in Unix and X-windows. The report describing the implementation is in Swedish, but appendixes concerning use and configuration are in English.
Carl Brown, Rune Gustavsson, Kristina Höök, Per Lindewall, Annika Waern
In this report we present the more important research contributions made in the Interactive Route Guidance (IRG) project* carried out at SICS Knowledge Based Systems Laboratory. The emphasis has been to look at those issues which affect acceptability of the IRG system both from the driver's and society's point of view. These contributions include : - a hierarchical representation of maps. - a heuristic search algorithm for route-finding in a hierarchical space. - a description of navigator stereotypes which may be implemented as user models in a navigational system. - principles for description of routes to the resident-navigator. - a methodology for the description of dynamic information that may affect traffic and route planning. - an algorithm which tailors planned routes to constraints and considers dynamic information in the planning. - a methodology for the presentation of route changes. - a system architecture for the integration of the route planning mechanism with the mechanisms for planning and presenting routes suitable for human stereotypes. - a system architecture for the integration of in-car information systems.
Hans Nilsson
The usual Prolog predicates for reading and writing are powerful but with some time overhead. In some situations a much faster reading and writing is required for a machine to machine message sending. This report describes the design and implementation of such predicates in SICStus Prolog.
Patrick Ernberg
We present a method of specification and verification based on CCS and observation equivalence. The method is applied to an ISDN layer 3 access protocol and an automatic tool is used to verify the correctness of the specification. Finally, we evaluate the method and tools used in the case study.
Oskar Permwall
A Sketch is a categorical tool for presenting theories. This is a commented bibliography on sketches and their use within some areas of computer science. References to work on sketches not primarily related to computer science are also provided.
Annika Waern
We have performed a pre-study on route guidance. The study concerned drivers that are unfamiliar with the area. The topic was to gain experience that would help us to set up future, larger experiments. We used a route where suburban, highway and in-driving was mixed. The drivers were accompanied by a co-driver who was familiar with the area of the route. The goals were:- To gather sample dialogues between driver and co-driver as empirical data for use in developing a formal model of dialogues and an experimental dialogue management system.- To get indications as to what information is normally used in a route description.This report covers only some of the pre-study results. In particular, it does not contain any thorough analysis of dialogues. aThe dialogue analysis will be contained in a forthcoming SICS technical report.
Annika Waern
The paper describes a model for the presentation of route guidance information, that is able to incorporate both static and dynamic route guidance within the same general interface structure. The model distinguishes between two modes that are independent on the driver's knowledge: - Expert Mode: The driver has enough local knowledge to understand which route the system wants him to take.- Novice Mode: The driver has no knowledge about the advised route. During a route guidance session, the driver might change between the modes several times. Based upon this distinction, a conceptual model for interface design is presented and motivated. The paper discuss to what extent a presentation system must check for, and correct, driver misconceptions. Such checking requires the development of a formal model of the driver's knowledge about alternative routes.
Fredrik Nöu
ISTS, The Interactive Space-Time Scheduler, is an interactive system for scheduling static algorithms developed at SICS. The ISTS system is an experimental "CAD" system that supports the mapping of static algorithms in space-time. The system decreases the time taken to get a time-optimal or nearly time-optimal mapping of an algorithm. Improvements and extensions have been made to the first version of ISTS. A theoretical study of automatic scheduling algorithms that might be applied in the ISTS system is also included. The ISTS system now provides support for the user to model the algorithm in a hierarchical manner. It supports multiple windows and possibilities to conceal information in order to improve scalability. This makes ISTS both more useful and easier to use. Future plans for the system are discussed.
Anneli Avatare
We present a prototype implementation of a graphical editor for a subset of SDL(Specification and Description Language). SDL is a CCITT recommended standard for specifying and describing telecom systems. The editor is defined by the meta-tool LOGGIE, a tool for generating interactive language-oriented graphical editors. A short introduction to LOGGIE is given and the SDL application is described including a presentation of the chosen subset of the SDL syntax.
Patrik Ernberg, Lars-åke Fredlund, Bengt Jonsson
We present a specification of a simple Overtaking protocol for vehicles using the Formal Description Technique LOTOS. A detailed description of the design process leading to this specification is given. The design process involves early use of simulation and validation tools available for LOTOS. We discuss the applicability of existing tools in the context of this example.
Lars-åke Fredlund
(This paper is an extended version of an earlier paper : " An Implementation of a Translational Semantics for an Imperative Language" by L.Fredlund, B. Jonsson and J. Parow. Publ. in Proceedings of CONCUR'90 conference on Theories of Concurrency, Unification and Extension". Springer-Verlag, Volume 458, 1990, Pages 246-262.) Abstract: We present a semantics for an imperative programming language, Lunsen, with constructs for concurrency and communication. The semantics is given through a translation into CCS. This translation has been implemented within the framework of the Concurrency Workbench, which is a tool for analysis of finite-state systems in CCS. The point of the translational semantics is that by imposing restrictions on Lunsen, so that the semantics of a program is finite-state, we can analyze Lunsen programs automatically using the Concurrency Workbench. We illustrate this by analyzing the alternating bit algorithm and two mutual exclusion algorithms.
Bengt Ahlgren, Per Lindgren, Teet Sirotkin
This report is an effort to describe the state-of-the-art in computer network security focusing on the OSI Security architecture. Other sources of information include the NCSC "Trusted Network Interpretation of the TCSEC". The report describes the security threats imposed on networks and the countermeasures available. It gives a detailed description of the security services defined in the OSI Security architecture and the mechanisms proposed for realizing these services. An overview of security management with emphasis on key management is also included. The report contains numerous references to books and articles in the field of network security.
Claes Svensson, Jan Sundberg
Must is a graphical tracer for the Or-parallel Prolog language Muse. Its purpose is to aid development and evaluation of Muse. The program can also be used for demonstration purposes. Must runs under UNIX and X-windows. Our goal was to make it simple to use but still expressive. This report will describe the background, design and implementation of Must. It will be concluded by an evaluation of the Must impact on the development of Muse algorithms. The report will also include a description of Stat, a tool for evaluating potential Or-parallelism in Prolog programs.
Patrik Ernberg, Lars-åke Fredlund
We present results which identify some of the bottlenecks of the Concurrency Workbench (CWB). Our results concentrate on the Minimize command which computes an agent with the smallest state space that is observation equivalent with a supplied agent. Measurements show that three major bottlenecks can be identified and that the performance of the CWB depends heavily on the amount of available primary memory.
Anette Gäredal
This report describes knowledge acquisition work, performed during a three months period, as part of a knowledge-based system project at IBM. The aim with the work was to develop knowledge acquisition procedures for diagnosis of a specific performance problem.
Magnus Christersson
(Supplement PA 89/89002A, pages 54 - 85, not printed, see Appendix D.1-F). PLANKEE is a planner which is able to do re-planning when execution of the original plan has failed. In the report we first summarize the history of planners and then develop an own planner for the blocks world. The planner uses slightly modified ideas from [Sacerdoti 77]. PLANKEE is implemented in KEE+ PLANKEE is extended to be able to re-plan failed plans. A new initial state is asserted wherefrom the new plan should be applied. By associating information from the planning procedure to the operators in the pla, PLANKEE can use this information to do effective re-planning. The information needed for effective re-planning is (1) to divide the operators into different categories and (2) to extend the use of preconditions.
Johan Palmkvist
This report describes a planning system implemented in GCLA. A definition of planning in the house world, which is a superset of STRIPS-like planning, is given, as well as a short introduction to the programming language GCLA. The blocks world and STRIPS-like planning is described, followed by a comparison between STRIPS-like planning and planning in the house world.
Anneli Avatare
This is a thesis work for the M.Sc. degree in mathematics and computer science at the University of Stockholm, accomplished at SICS, Swedish Institute of Computer Science, Kista during the summer and autumn 1989. This thesis deals with hardware synthesis by space-time mappings. It is a method to map the steps in algorithm to distinct events in a space-time. If the pattern of an algorithm is known in advance then the algorithm can be implemented directly in the hardware when it is known where and then all steps in the algorithm will be executed then it can be determined where cells shall be placed and how they shall be connected to each other. I have developed a prototype, an Interactive Space-Time Scheduler, that can be used as an aid to schedule algorithms manually in the space-time. The user interface is developed in the Xerox/Interlisp-D environment.
Per Kreuger
Supplement PA89/89001A
This paper describes a procedure for unification in extensional higher
order logics. The procedure is due to Gerard Huet and was described in
Anna Bång, Per Lindberger
In this thesis we describe and develop a simple natural language interface for AI applications. The interface is based on TALK, a system originating from Fernando C. N. Pereira and Stuart M. Shieber. After a brief presentation of their system we delineate implementations of several indispensable language constructions. A complete example, a puzzle solving program combining the enhanced NL interface with a theorem prover, is included. Finally, we discuss and carry out a "purification" of our system, thus enabling it to run in a parallel logic programming environment not fully compatible with Prolog.
Jerker Andersson, Per Andersson
The aim of the thesis has been to define the domains of control structure specification and process station configuration in order to find a general approach applicable to problems concerning the configuration of a process control system or any similar system. These findings are then used as the foundation for constructing a knowledge based system capable of realizing a problem solving method pertaining to the domain of configuring a specific computer system.
Bengt Ahlgren, Per Lindgren, Teet Sirotkin
SPION: Secure Protocols in OSI Networks This report describes how security services can be realized in a computer network using the protocols of the Open Systems Interconnection (OSI) reference model for communication. The report starts with defining security requirements for a "typical" local area network in a company, university or similar organization. It is assumed that the organization does not use the network for transfer of extremely sensitive information, such as military secrets. A set of security services, as specified in the OSI security architecture, are selected in order to satisfy the requirements. The selected services are then placed in suitable layers of the OSI model according to the criteria in the security architecture, and to the taste of the authors. The report concentrates on the transport layer. An extension of the OSI transport protocol, class 4, including security services is described in detail. The protocol is a fully compatible extension of the standard transport protocol. Key management is another topic which is included in the report. A key management system for handling public keys and digital signatures based on an article by Dorothy E. Denning is described. The system includes functions for distributing and validating public keys, and registering and later verifying digital signatures. A key management protocol supporting these functions is defined for communication between ordinary open systems and special key server systems.
Martin Aronsson
No longer distributed.
Ahmed Hussain Khan
It is important to reason about a number of desirable protocol properties to ensure correctness of a designed communicating system. Such properties can be formulated in some temporal logic. If the specification of a communicating system is finite-state, that is, the system has a finite number of distinct states, it is often possible to verify automatically by an efficient algorithm, called a model checking algorithm, whether the system satisfies a property expressed in the logic. We describe a model checking method for Communicating Systems. An implementation of this model-checking facility is obtained by combining two automated tools, namely, CWB (the Concurrency Workbench developed at Edinburgh, Sussex and SICS) and EMC (the Extended Model Checker developed by Emerson and Clarke). In the EMC, there is an efficient model checking algorithm for branching time temporal logic(CTL) with the standard semantics. We change the standard semantics for CTL in terms of communication actions. We implement a transformation of the transition graph into a finite number of distinct states so that it can be fed into EMC to use our logic.
Anders Tunevi
A learning system for fault finding has been constructed. This system contains many different types of knowledge, three ways to find faults and four ways to learn fault finding. The constructed learning system works for a class of fault finding problems. This class has been described in the paper. The developed system could be viewed as an architecture of a general learning system for fault finding. The system could also be used as a testbench of learning mechanisms. The experiences from this project indicates that it is possible to build a learning system when the structure of the knowledge is known. In this paper the following ideas will be discussed: How can the fault finding and learning techniques be integrated? How can the knowledge structure, fault finding mechanisms and learning mechanisms emerge with the help of a simulator and general mechanisms?
Tunevi, Anders
A learning system for fault finding has been constructed. This system contains many different types of knowledge, three ways to find faults and four ways to learn fault finding. The constructed learning system works for a class of fault finding problems. This class has been described in the paper. The developed system could be viewed as an architecture of a general learning system for fault finding. The system could also be used as a testbench of learning mechanisms. The experiences from this project indicates that it is possible to build a learning system when the structure of the knowledge is known. In this paper the following ideas will be discussed: How can the fault finding and learning techniques be integrated? How can the knowledge structure, fault finding mechanisms and learning mechanisms emerge with the help of a simulator and general mechanisms?
Benzinger, Mikael, Nordström, Anna
This is a Masters thesis work in Computer Science at the University of Stockholm, accomplished at SICS (Swedish Institute of Computer Science) during autumn and winter 1988-89. In the area of Human-Computer Interaction, HCI, there is currently a lot of research. We are discussing some important aspects of HCI, mainly concerning design of graphical editors, as WYSIWYG, event driven actions, undo-mechanism and menu-arrangements. The report also describes a design and implementation of some graphical editors used in LOGGIE. These editors are used to design symbols, windows, menus, etc. to be used in LOGGIE.
Per Kreuger
(Report is written in Swedish.) Denna artikel presenterar, sammanfattar och granskar kritiskt en teori som läggs fram av Kurt Konolige i hans artikel "On the Relation between Default and Autoepistemic Logic." Detta material presenterades ursprungligen som examination på doktorandkursen "Logik for AI" som gavs under 1988 av Rune Gustavsson på SICS. Konoliges artikel tar upp förhållandet mellan två typer av logiker som använts för att föra default-resonemang, en typ av resonemang under ofullständig kunskap. De två system han tar upp är dels Reiters Default-logik, dels Moores Autoepistemiska logik. Det huvudsakliga resultatet i Konoliges artikel är att dessa tvä system kan visas vara ekvivalenta i en viss mening.
Hans Bogeby, Harri Vuorela
This master thesis work was accomplished at SICS (Swedish Institute of Computer Science) during the autumn of 1988. Abstract: The task of the master thesis work was to implement a subset of the Graphical Support System which is a part of a project called LOGGIE. The Graphical Support System is a general purpose package with high level graphics and with object oriented design and implementation.
Martin Aronsson
The basis for the language GCLA is a generalization of the concept inductive definitions, called partial inductive definitions. The program defines a logic, which is used to make inferences to prove if a query holds or not. This report first presents a short introduction to these ideas. Then, an abstract machine, called GAM, for GCLA is presented; the instructions as well as an introduction to the compiling schema is given together with some examples. The GAM instructions are also presented as transitions in an appendix.
Mikael Eriksson
(Report is written in Swedish.) Denna rapport beskriver ett sätt att automatiskt hitta beroenden i ett konceptuellt schema från en databas. En speciell form av induktiv inlärning, clustering, används. Två inlärnings-algoritmer som använder clustering-teknik beskrivs. Den ena, CLUSTER/2, använder en teknik som gör en uttömmande sökning för att hitta ett optimalt clustering, eller klassificering. Den andra algoritmen, A, använder en agglomerativ teknik. En algoritm har implementerats, som använder clustering-algoritmerna för att hitta beroenden mellan attribut i ett konceptuellt schema från en databas. De olika beroendena har olika sannolikheter och kan då betraktas som partiellt funktionella beroenden. Med hjälp av parametrar kan algoritmen konfigureras. Man kan t.ex välja vilken av de båda algoritmerna som skall väljas, vilka attribut som skall betraktas vid generering av beroendena samt vilken minsta sannolikhet ett beroende måste ha. Ett antal exempelkörningar samt förslag på utvidgningar presenteras också.
Chan-Hee Lee
(Report is written in Swedish.) Den här rapporten handlar om en del av implementeringen av ett programsystem kallat "CWB" (Concurrency Workbench) som utför ett flertal analyser av processer. Processerna beskrivs i språket CCS (Calculus of Communicating Systems) [Mil80], en metod att specificera och resonera om distribuerade datorsystem.
Ylva Gullestad
ALPHA is a support system for applications using interactive computer graphics. The ALPHA system is a subsystem of the PHIGS graphic standard (the PHIGS version presented in dpANS X3.144-198x of October 1986), specifically tailored to the Xerox/Interlisp-D environment. The Programmer's Hierarchical Interactive Graphics System (PHIGS) is a functional specification of the interface between an application program and its graphic support system. PHIGS supports hierarchical graphics, user interaction and 3-D modelling. ALPHA is a detached CommonLisp package in the Interlisp-D environment. The package exports all ALPHA functions to be used and only imports necessary Interlisp-D functions.
Jan Kristoferson
It has been suggested that in certain situations it would make sense to use different activation probabilities for writing and reading in SDM (Sparse Distributed Memory). However, here we model such a situation and find that, at least approximately, it is optimal to use the same probabilities for writing and reading. We also investigate the scaling up of SDM, in connection with some observations made by Sj{\"o}din, see \cite{Sjodin-97}. It is shown that the original SDM (here in Jaeckel's version) does not scale up if the reading address is disturbed, but that this can be remedied by using a kind of sparse SDM.
Fredrik Larsson, Peter Magnusson, Bengt Werner
A simulator is a powerful tool for both hardware and software development. However, implementing an efficient simulator by hand is a labour intensive and error-prone task. This paper describes a tool for automating significant portions of the work involved in developing instruction set architecture simulators while still generating an efficient simulator. We believe that the tool significantly shortens the design time. A specification file describing the instruction set is used as input to the tool. With this technique we have generated a SPARC V8 simulator which is more efficient than an earlier hand-coded and hand-optimized version. The tool has also been applied to APZ 21220, a proprietary embedded CISC processor, demonstrating the generality of the technique.
Mads Dam, Lars-åke Fredlund
A logic and proof system is introduced for specifying and proving properties of open distributed systems. Key problems that are addressed include the verification of process networks with a changing interconnection structure, and where new processes can be continuously spawned. To demonstrate the results in a realistic setting we consider a core fragment of the Erlang programming language. Roughly this amounts to a first-order actor language with data types, buffered asynchronous communication, and dynamic process spawning. Our aim is to verify quite general properties of programs in this fragment. The specification logic extends the first-order $\mu$-calculus with Erlang-specific primitives. For verification we use an approach which combines local model checking with facilities for compositional verification. We give a specification and verification example based on a billing agent which controls and charges for user access to a given resource.
Gunnar Karlsson
There has been much attention given to ATM Adaptation Layers (AAL) over the ten-year history of ATM standardization. Yet none of the existing standards include a retransmission protocol to ensure reliability of the transfers. In this paper we propose an AAL for doing selective retransmissions of individual segments that have been lost or corrupted in the transfer. Since the amount of retransmitted data equals the amount lost, there is little risk of aggravating congestion and the reliability is provided as economically as possible, which is a virtue for low-capacity radio links. The protocol relies on the orderly delivery of ATM virtual circuits so that data octets can be identified uniquely by their location in the data stream.
Mads Dam, Fredrik Orava
Roland Karlsson
The Kanerva Sparse Distributed Memory (SDM) is a mechanism for implementing a memory with a huge address space. The physical memory consists of substantially fewer locations than the virtual address space. The plain Kanerva SDM memory assumes address and data to be random bit vectors with equal probability for 0 and 1. To compensate for any bias in address or data, several more or less elaborate methods can be used. In this paper we describe one simple method for achieving this compensation within the framework of the ``Fast activation Mechanism'' for SDM.
Roberto Amadio, Mads Dam
We study the problem of specifying and verifying properties of pi-calculus processes while relying on a bisimulation semantics. As our property specification language we use a version of the modal mu-calculus adapted to the pi-calculus. We show that the logical language is sufficiently expressive to characterize by means of a finite formula a process up to any approximation of the bisimulation relation. We consider the problem of checking that a process of the pi-calculus satisfies a specification expressed in this modal mu-calculus. We develop an algorithm which is sound in general, and complete for processes having a finite reachability property. Finally, we present a proof system which can be applied to prove non-recursive properties of arbitrary processes. We show that the system is complete on the non-recursive fragment of the logical language.
Seppo Pohja
This survey is meant to serve computer scientists, mathematicians and others who need to get quickly acquainted with the most relevant results in the biology and psychology of the tactile senses but have little or no prior exposure to the field. The survey is written from the point of view of a computer scientists studying artificial neural networks (ANNs). Questions of relevancy - what to include and what to exclude in the survey - are always very subjective. This survey tries to include biological and psychological knowledge and results that could provide ANN research with new ideas and insights. Also, the survey includes matters that could make the opposite to take place: ANN research providing biology and psychology with new ideas or insights.
Kristina Höök, Marie Sjölinder, Nils Dahlbäck
This study derives from two important observations. First, that navigation in hypermedia is a difficult task, and second, that individual cognitive differences play a role in how well users are able to efficiently use computer systems. We found that of the cognitive abilities tested in our study, only spatial ability could be related to the time spent in completing a set of tasks in a large, hypermedia, information structure. We furthermore found that it was only certain aspects of spatial ability which were related to the ability navigate in hypermedia, namely those related to solving spatial problems mentally rather than solving spatial problems in the physical world.
Gunnar Karlsson
Video transfers across IP and ATM networks have received much research attention during the last ten years. Various video services are expected in the future, enabled by the rapid development in video coding and broadband network technology. This paper gives an introduction to the issues involved in asynchronous video transfers. Brief overviews of video coding, rate control, multiplexing, as well as delay, error and loss control are given.
Gunnar Sjödin
A new method for converging in the SDM memory, utilizing the Jaeckel/Karlsson activation mechanism, is presented. A set of new operations to utilize the memory is introduced.
Gunnar Sjoedin
A more efficient way of reading the SDM memory is presented. This is accomplished by using implicit information, hitherto not utilized, to find the information-carrying units and thus removing unnecessary noise when reading the memory.
Jan Kristoferson
An unknown number T of random data vectors have been stored in a sparse distributed memory with randomly chosen hard locations. A method is given to estimate T. The estimate is unbiased, and the coefficient of variation is roughly inversely proportional to the square root of MU, where M is the number of hard locations in the memory and U the length of data.
Roland Karlsson
The Kanerva Sparse Distributed Memory (SDM) is a mechanism for implementing a memory with a huge address space. The physical memory consists of substantially fewer locations than the virtual address space. In earlier implemen- tations of the SDM memory the addresses of all physical locations had to be scanned to determine which locations to activate. This is time-consuming, and massive parallel hardware support is needed for other than small appli- cations. This paper introduces a new mechanism for finding the active locations. Using this access mechanism, the access time may be speeded up several orders of magnitude.
Jan Kristoferson
The optimal probability of activation and the corresponding performance is studied for three designs of Sparse Distributed Memory, namely, Kanerva's original design, Jaeckel's selected-coordinates design and Karlsson's modification of Jaeckel's design. We will assume that the hard locations (in Karlsson's case, the masks), the storage addresses and the stored data are randomly chosen, and we will consider different levels of random noise in the reading address.
Kristina Höök
Adapting explanations to users with varying background knowledge and abilities is a difficult task: the explanation content, style, amount of details, terms used, etc. may be affected in various ways. We have used our analysis of the information seeking tasks of the users in one par ticular domain as a basis for adaptation. We structured the domain information into a set of in forma tion entities where each entity describes one aspect of a node in the in formation space. Each information entity is fitted to one or several infor ma tion seeking tasks, and by combining entities we create an explanation adapted to the user's current task. We do not avoid concepts which are unknown to the user in our information entities. Instead we al low the users to ask follow-up questions on those con cepts in order to cater the users' differences in background knowledge. Which follow-up questions are available also depends on the users' current task. Finally, we emphasise the need to make the difference between the adapted explanations obvious to the user. Only then can the users predict which ex planations best fit their need and thereby control the self-adaptive mecha nisms of the system. So, our system is adaptive to the information seeking task of the user, while the user's knowledge, abilities and roles, are catered for by other means..
Björn Lisper
We study systems where deterministic computations take place in environments which may behave nondeterministically. We give a simple formalization by unions of abstract reduction systems, on which various semantics can be based in a straightforward manner. We then prove that under a simple condition on the reduction systems, the following holds: reduction strategies which are cofinal for the deterministic reduction system will implement the semantics for the combined system, provided the environment behaves in a "fair" manner, and certain program transformations, such as folding and unfolding, will preserve the semantics. An application is evaluation strategies and program transformations for concurrent languages.
Erik Schön
This report features an introduction to lattice- and fixpoint theory and a survey of methods and recent results for fixpoint computations in static program analysis. As the number of equations in static program analysis tend to be very large, it is extremely important to avoid unnecessary computations and hence to find an optimal order in which to compute the functions. It is also important to have an efficient method for detecting stability. An algorithm satisfying these two requirements is Bourdoncle's algorithm for finding a weak topological ordering of a directed graph which may contain cycles. This algorithm is a generalization of Tarjan's algorithm for finding the strongly connected components of a directed graph. This report presents results from experiments with a fixpoint solver in the analysis framework for AKL (Agents Kernel Language, a concurrent constraint language developed at SICS) using the above ideas showing that a considerable speed-up (up to 3000%) can be achieved compared to that of a fixpoint solver based on strongly connected components. This is explained by showing how weak topological orders computed by Bourdoncle's algorithm incorporate many intuitively good heuristics. The report also introduces partially argument independent functions, a class of functions particularly suited to the repetitive scheme of computations that arise in fixpoint computations. A function of this type needs to be re-evaluated only with respect to those of its arguments which have changed since its latest evaluation.
Anders Andersson
LALR(1) parser generators in conjunction with imperative programming languages is the standard solution for parsing applications. Contrary to popular belief, this situation is not entirely satisfactory. With imperative tools like Yacc, it is difficult to add actions to a grammar without introducing conflicts. Also, LALR(1) is not powerful enough to meet the needs of languages like C++. We argue that LALR(1) parsing in conjuction with concurrent constraint programming is an interesting option that solves the former problem. We also show how deep guards and don't-know non-determinism can be exploited to solve the latter problem. These ideas have been incorporated in the Saga parser generator described in this report. Saga is an integrated generator for lexical analyzers and parsers. It is based on AKL, a multiparadigm programming language based on a concurrent constraint framework. It is intended both as a research tool to demonstrate the power offered by concurrent constraints, and as a practical tool for the Agents programming system. As a practical tool, Saga features many improvements over tools like Yacc. For example, Saga offers powerful syntax, elegant reporting and resolution of conflicts and powerful error handling in the generated syntax analyzers.
Ivan Bretan
An essay on rationale and methodology of combining natural language and other means of interaction in multimodal interfaces.
Gunnar Karlsson
The research on traffic control has not yet lead to a consensus on how to properly allocate resources in ATM networks. There are consequently no practicable methods available now when the initial deployment of ATM switches and terminals is under way. Yet, many of the applications which motivate the deployment uses multi-media and will thus require some degree of performance guarantees on the information transfer. Here we suggest a readily applicable method for reserving capacity in ATM networks. Cells using the reserved capacity may only depart at fixed time-instances, and have reserved buffers in the network nodes. The scheme gives a lossless performance, can be implemented with low complexity; it simplifies the call-acceptance and allows ``best effort'' traffic to use slack in the reserved and all of the non-reserved capacity.
Lars-åke Fredlund, Jan Friso Groote (Utrecht University, The Netherlands), Henri Korver (Utrecht University, The Netherlands)
In 1982 Dolev, Klawe & Rodeh presented an O(n log n) unidirectional distributed algorithm for the circular extrema-finding (or leader-election) problem}. At the same time Peterson came up with a nearly identical solution. In this paper, we bring the correctness of this algorithm to a completely formal level. This relatively small protocol, which can be described on half a page, requires a rather involved proof for guaranteeing that it behaves well in all possible circumstances. To our knowledge, this is one of the more advanced case-studies in formal verification based on process algebra.
David Samuelsson
An implementation of a system level interpreter of the SPARC V8 instruction set architecture is described. The goal is that the simulator, SimICS, should be sufficiently accurate to run an operating system on top of the simulator. The simulation is performed by direct threaded interpretation of an intermediate code. Simulation of condition codes is performed quickly and can handle all combinations of condition codes. The condition codes are evaluated lazily and unnecessary computations are avoided. Access to registers in a register window is as efficient as in a flat register file. To optimize instructions specialized variants are identified that can be executed faster. SimICS is tested using a comprehensive test suite. The suite exercises the instruction set using interesting combinations of input parameters and operands and compares the result to a reference implementation. A validation of the results is performed with SPEC benchmarks. The result is a stable and correct system level interpreter of SPARC Architecture Version 8 that runs 15 times slower than the real hardware.
Mads Dam
We present general results for showing process equivalences applied to the finite control fragment of the pi-calculus decidable. Firstly a Finite Reachability Theorem states that up to finite name spaces and up to a static normalisation procedure, the set of reachable agent expressions is finite. Secondly a Boundedness Lemma shows that no potential computations are missed when name spaces are chosen large enough, but finite. We show how these results lead to decidability for a number of pi-calculus equivalences such as strong or weak, late or early bismulation equivalence. Furthermore, for strong late equivalence we show how our techniques can be used to adapt the well-known Paige-Tarjan algorithm. Strikingly this results in a single exponential running time not much worse than the running time for the case of for instance CCS. Our results considerably strengthens previous results on decidable equivalences for parameter-passing process calculi.
Mads Dam
A critical dimension in the handling of change in computer-based systems for cooperative work is whether mechanisms for change should be explicitly embedded into systems, or whether change should be handled in a global and uniform manner, for instance by a process of editing and recompiling programs or scripts on the fly. We argue that to reflect the structure of organisations, powers of change must be local, structured, and dynamic. Thus a global and uniform handling of change is in general insufficient. We propose a formal basis for the description of dynamically modifiable objects, and explore its applicability in the field of CSCW by exposing it to three examples of increasing complexity: A system for dynamic communication channel creation; an adaptable conversation manager; and a rudimentary, yet quite general, awareness model.
Roberto Amadio, Mads Dam
We address the specification and verification problem for process calculi such as Chocs, CML and Facile where processes or functions are transmissible values. Our work takes place in the context of a static treatment of restriction and of a bisimulation-based semantics. As a paradigmatic and simple case we concentrate on (Plain) Chocs. We show that Chocs bisimulation can be characterized by an extension of Hennessy-Milner logic including a constructive implication, or function space constructor. This result is a non-trivial extension of the classical characterization result for labelled transition systems. In the second part of the paper we address the problem of developing a proof system for the verification of process specifications. Building on previous work for CCS we present an infinitary sound and complete proof system for the fragment of the calculus not handling restriction.
Peter S. Magnusson, David Samuelsson
Instruction set architecture (ISA) simulators are an increasingly popular class of tools for both research and commercial purposes. Common applications include trace generation, program development, and compatibility support. A major concern with ISA simulators is performance and memory overhead. A common technique for achieving good performance is to use threaded code, which involves translating the target object code to an intermediate format which is subsequently interpreted. We describe such an internal format, which we call the 64-bit format, that is compact and meets a range of requirements in terms of flexibility and simplicity. We show how a simulator using this format can be implemented efficiently by taking advantage of extensions to the C language supported by the GNU C compilers. We have used the format to write the core interpreter in SimICS, a system level multiprocessor simulator that supports the Motorola 88110 and the SPARC V8 instruction sets.
Peter S. Magnusson, Bengt Werner
We describe novel techniques used for efficient simulation of memory in SimICS, an instruction level simulator developed at SICS. The design has focused on efficiently supporting the simulation of multiprocessors, analyzing complex memory hierarchies and running large binaries with a mixture of system-level and user-level code. A software caching mechanism (the Simulator Translation Cache, STC) improves the performance of interpreted memory operations by reducing the number of calls to complex memory simulation code. A lazy memory allocation scheme reduces the size of the simulator process. A well-defined internal interface to generic memory simulation simplifies user extensions. Leveraging on a flexible interpreter based on threaded code allows runtime selection of statistics gathering, memory profiling, and cache simulation with low overhead. The result is a memory simulation that supports a range of features for use in computer architecture research, program profiling, and debugging. (NOTE: A later version was published in the 28th Annual Simulation Symposium)
Ashley Saulsbury, Tim Wilkinson, John Carter
We present design details and some initial performance results of a novel scalable shared memory multiprocessor architecture that incorporates the major strengths of several contemporary multiprocessor architectures while avoiding their most serious weaknesses. Specifically, our architecture design incorporates the automatic data migration and replication features of cache-only memory architecture (COMA) machines, but replaces much of the complex hardware of COMA with a software layer that manages page-grained cache space allocation, as found in distributed virtual shared memory (DVSM) systems. Unlike DVSM however, pages are sub-divided into cache-line sized blocks, and for shared pages the coherence of these blocks is maintained by hardware. Moving much of COMA's hardware functionality to software simplifies the machine design and reduces development time, while supporting fine-grain coherence in hardware greatly decreases the impact of DVSM software overheads. We call the resulting hybrid hardware and software multiprocessor architecture Simple COMA. By allowing shared data to be replicated in a node's main memory (in addition to its caches), the number of remote memory accesses is greatly reduced compared to a traditional cache coherent non-uniform memory access (CC-NUMA) architecture. Preliminary results indicate that despite the reduced hardware complexity and the need to handle allocation page faults in software, the performance of Simple COMA is comparable to that of more complex all-hardware designs.
Jussi Karlgren, Kristina Höök, Ann Lantz, Jacob Palme, Daniel Pargman
The first requirement on an interactive system in a domain such as information filtering is to be an interface to knowledge, rather than just a knowledgeable interface. We borrow the computation instruction metaphor of a system as "a black box in a glass box" as a means to conceptualize the problem of giving a user control over the actions of an interactive system. The application domain we work in is that of information filtering. In the "black box", we hide complex knowledge of the domain objects such as facts and assumptions about text genre identification, while the "glass box", which is what the user sees, only shows the neat top level knowledge of the domain conceptual categories such as e.g. categorization rules.
Thomas Sjöland, Dan Sahlin
We have defined and implemented a method for analysis of the CCP language AKL in the spirit of abstract interpretation that uses a static set of semantic equations which abstracts the concurrent execution of an AKL program. The method strictly separates the setting up of the equation system from the solving of the system with a fixpoint procedure. The computation strategies used, results for a number of test programs and the conclusions we draw from this experimental effort are reported. The software implementing the system described herein, is deliverable number D.WP.1.6.1.M2 in the ESPRIT project ParForce 6707.
Charles Grant Brown, Annika Wærn
Several approaches to intelligent tutoring monitor the learners actions in order to understand his/her abilities. This requires that the learner's actions can be monitored. In traditional single-user command interfaces this is straightforward. As a result action tracking has not been subject to much study. However, in more advanced interfaces and applications, it is no longer self-evident how action tracking should be done, or even what should be considered an action. This paper addresses two particular aspects of systems of today that make action tracking hard: The increasing naturalness of interfaces, and the introduction of environments for human collaboration. The DIVE environment is extremely advanced in both these aspects, being a virtual reality environment for unconstrained human collaboration. We characterize the possibilities and limitations for action tracking in DIVE, and suggest an architecture for the task.
Torkel Franzén
The Agents Kernel Language allows committed choice programming as well as nondeterministic logic programming based on the Andorra principle (and combinations of these), with a considerable degree of parallelism. In the present report the AKL computation model is formally defined and soundness and completeness results for a logical subset of AKL are presented. The computation model is extended to cover ports, a medium of communication used in AKL, and the solution collecting operation bagof. These extensions preserve the basic character of the computation model, and in particular the role played by the constraint theory. Declarative interpretations of these constructs are introduced, and the limitations of these readings are discussed. Finally, the confluence of strongly fair (possibly infinite) computations in a different subset of AKL is proved.
Yoram Hirshfeld, Mark Jerrum, Faron Moller
A polynomial-time algorithm is presented for deciding bisimulation equivalence of so-called Basic Parallel Processes: multisets of elementary processes combined by a commitative parallel-composition operator.
Yoram Hirshfeld, Mark Jerrum, Faron Moller
The previous best upper bound on the complexity of deciding bisimilarity between normed context-free processes, due to Huynh and Tian, is that the problem lies in the second level of the polynomial hierarchy: their algorithm guesses a proof of equivalence and validates this proof in polynomial time using oracles freely answering questions which are in NP. In this paper we improve on this result by presenting a polynomial-time algorithm which solves this problem. As a corollary, we have a polynomial algorithm for the equivalence problem for simple context-free grammars.
Peter Magnusson, Anders Landin, Erik Hagersten
Large-scale shared-memory multiprocessors typically have long latencies for remote data accesses. A key issue for execution performance of many common applications is the synchronization cost. The communication scalability of synchronization has been improved by the introduction of queue-based spin-locks instead of Test & (Test & Set). For architectures with long access latencies for global data, attention should also be paid to the number of global accesses that are involved in synchronization. We present a method to characterize the performance of proposed queue lock algorithms, and apply it to previously published algorithms. We also present two new queue locks, the LH lock and the M lock. We compare the locks in terms of performance, memory requirements, code size, and required hardware support. The LH lock is the simplest of all the locks, yet requires only an atomic swap operation. The M lock is superior in terms of global accesses needed to perform synchronization and still competitive in all other criteria. We conclude that the M lock is the best overall queue lock for the class of architectures studied.
Martin Eineborg, Björn Gambäck
The paper outlines a method for automatic lexical acquisition using three-layered back-propagation networks. Several experiments have been carried out where the performance of different network architectures have been compared to each other on two tasks: overall part-of-speech (noun, adjective or verb) classification and classification by a set of 13 possible output categories. The best results for the simple task were obtained by networks consisting of 204-212 input neurons and 40 hidden-layer neurons, reaching a classification rate of 93.6%. The best result for the more complex task was 96.4%, which was achieved by a net with 423 input neurons and 80 hidden-layer neurons. These results are rather promising and the paper compares them to the performance reported by rule-based and purely statistical methods; a comparison that shows the neural network completely compatible with the statistical approach. The rule-based method is, however, still better, even though it should noted that the task that the rule-based system performs is somewhat different from that of the neural net.
Ivan Bretan, Jussi Karlgren
We discuss the synergetic effects that can be obtained in an integrated multimodal interface framework comprising on one hand a visual language-based modality and on the other natural language analysis and generation components. Besides a visual language with high expressive power, the framework includes a cross-modal translation mechanism which enables mutual illumination of interface language syntax and semantics. Special attention has been payed to how to address problems with robustness and pragmatics through unconventional methods which aim to enable user control of the discourse management process.
M-S. Agnäs et al, Björn Gambäck
This document is the first-year report for a project whose long-term goal is the construction of a practically useful system capable of translating continuous spoken language within a restricted domain. The main deliverable resulting from the first year is a prototype, the Spoken Language Translator (SLT), which can translate queries from spoken English to spoken Swedish in the domain of air travel planning. The system was developed by SRI International, the Swedish Institute of Computer Science, and Telia Research AB. Most of it is constructed from previously existing pieces of software, which have been adapted for use in the speech translation task with as few changes as possible. The main components are connected together in a pipelined sequence as follows. The input signal is processed by SRI's DECIPHER(TM), a speaker-independent continuous speech recognition system. It produces a set of speech hypotheses which is passed to the English-language processor, the SRI Core Language Engine (CLE), a general natural- language processing system. The CLE grammar associates each speech hypothesis with a set of possible logical-form-like representations, typically producing 5 to 50 logical forms per hypothesis. A preference component is then used to give each of them a numerical score reflecting its linguistic plausibility. When the preference component has made its choice, the highest-scoring logical form is passed to the transfer component, which uses a set of simple non-deterministic recursive pattern-matching rules to rewrite it into a set of possible corresponding Swedish representations. The preference component is now invoked again, to select the most plausible transferred logical form. The result is fed to a second copy of the CLE, which uses a Swedish- language grammar and lexicon developed at SICS to convert the form into a Swedish string and an associated syntax tree. Finally, the string and tree are passed to the Telia Prophon speech synthesizer, which utilizes polyphone synthesis to produce the spoken Swedish utterance. The system's current performance figures, measured on previously unseen test data, are as follows. For sentences of length 12 words and under, 65% of all utterances are such that the top-scoring speech hypothesis is an acceptable one. If the speech hypothesis is correct, then a translation is produced in 80% of the cases; and 90% of all translations produced are acceptable. Nearly all incorrect translations are incorrect due to their containing errors in grammar or naturalness of expression, with errors due to divergence in meaning between the source and target sentences accounting for less than 1% of all translations. Making fairly conservative extrapolations from the current SLT prototype, we believe that simply continuing the basic development strategy could within three to five years produce an enhanced version, which recognized about 90% of the short sentences (12 words or less) in a specific domain, and produced acceptable translations for about 95-97% of the sentences correctly recognized. Since the greater part of the system's knowledge would reside in domain-independent grammars and lexicons, it would be possible to port it to new domains with a fairly modest expenditure of effort.
Björn Lisper
In LIsper: "Total Unfolding: Theory and Applications" some results were proved regarding properties of unfolding of purely functional programs. Especially, a theorem was shown that relates the termination of symbolic evaluation of a "less instantiated" term relative to the termination of a "more instantiated" term. An application is partial evaluation, where unfolding of function definitions is frequently performed to enable further simplifications of the resulting specialized program. The unfolding must then be kept under control to ensure that the partial evaluation terminates. In this paper, we extend the termination result from purely functional programs programs with nondeterministic operations. We give an operational semantics where the behaviour of operators is defined through rewrite rules: nondeterminism then occurs when the resulting term rewriting system is nonconfluent. For the confluent part, the previous termination results carry over. It is, however, not guaranteed in general that the resulting unfolded program has the same semantics as the original program. We give conditions on the rewrite rules that guarantee that both versions have the same semantics, and we show that they apply to a nontrivial class of nondeterministic languages.
Mads Dam
We introduce a temporal logic for the polyadic pi-calculus based on fixed point extensions of Hennessy-Milner logic. Features are added to account for parametrisation, generation, and passing of names, including the use, following Milner, of dependent sum and product to account for (unlocalised) input and output, and explicit parametrisation on names using lambda-abstraction and application. The latter provides a single name binding mechanism supporting all parametrisation needed. A proof system and decision procedure is developed based on Stirling and Walker's approach to model checking the modal mu-calculus using constants. One difficulty, for both conceptual and efficiency-based reasons, is to avoid the explicit use of the omega-rule for parametrised processes. A key idea, following Hennessy and Lin's approach to deciding bisimulation for certain types of value-passing processes, is the relativisation of correctness assertions to conditions on names. Based on this idea a proof system and decision procedure is obtained for arbitrary pi-calculus processes with finite control, pi-calculus correlates of CCS finite-state processes, avoiding the use of parallel composition in recursively defined processes.
Joachim Parrow
Interaction diagrams are graphic representations of concurrent processes with evolving access capabilities; in particular they illustrate the points of access and relations between them. The basic step of computation is the migration of an access point between processes. This paper explains interaction diagrams through a sequence of examples. Diagrams can be regarded as graphic counterparts of terms in the pi-calculus and illuminate some interesting points on its construction.
Martin Aronsson
The paper describes the basic implementation of GCLA II's control level. The basis of the implementation is a compiling scheme for transforming inference rules and strategies operating on the object level to an interpreter in Prolog, where the inference rules of the control level are coded inline. This is possible since the operational semantics of the control level is deterministic, i.e. the choice of inference rule to apply on a control level goal is determined solely by the parts of the goal. To handle dynamic clauses, a context list, accessible through some new C-functions linked together with the Prolog system. GCLA I and GCLA II are described shortly, followed by a discussion of a Horn clause representation of inference rules versus functions coding inference rules. Then the transformation of inference rules and strategies is described followed by some examples.
Martin Aronsson
The paper describes a tool for generating plans for the construction of a building. The application is implemented in GCLA, together with a simple constraint solving system. The main idea is that experiences from other plans are stored in methods; which are a systematic way of grouping activities together as higher level activities that can solve more complex tasks. Activities are entities that perform some action on a model of the real world, called the global state. Activities have preconditions, i.e. starting conditions, some representation of time and resource consumption, and postconditions, i.e. how and what to change in the global state. Scheduling activities amounts to allocating resources and placing the activities in time. The goal of the planning process, i.e what we want the planning process to achieve, is represented by a geometric model of the changed global state, i.e. a design of the specified building that one wants to build. To create plans, the system is divided into two main phases; the choice-of-method phase and the scheduling phase. In the choice-of-method phase suitable methods are chosen based on experience from the past. Such methods already exists in the building industry, although not in an explicit formal representation. Then the scheduling phase allocates resources and places the activities in time by reasoning about the activities' change of the global state. The goal of the planning process is that the objects of the specified design should be produced and represented in the global state. The user can change most of the behaviour of the system by indicating what he wants it to do. He can change activities, their preconditions, calculations and postconditions, he can change methods, or add or remove activities to them, he can change resources etc. By this flexibility, the user can form his system to reflect his own preferences about how to plan and what to plan.
Martin Aronsson
We present algorithms for computing A-sufficient substitutions and constraint sets together with the definiens operation. These operations are primitive operations in the language GCLA. The paper first defines those primitives, which together form a dual rule to SLD resolution, and then describes the different algorithms and some of their properties together with examples. One of the algorithms shows how a definition can be compiled into a representation holding all possible A-sufficient substitutions/constraint sets together with their corresponding definiens. This representation makes the computation at runtime of a definiens and an A-sufficient substitution/constraint set have the same complexity as the table lookup operation clause/2 in Prolog. The paper also describes the generalisation from unification (sets of equalities) to constraint sets and satisfiability of systems of equalities and inequalities.
Göran Falkman, Jonas Warnby
This paper describes an implementation of a small knowledge-based system in GCLA II. GCLA II is perhaps best described as a logical programming language, with some properties usually found among functional languages, and it includes hypothetical and non-monotonic reasoning as integral parts, which makes it easy to handle hypothetical queries, negation and AI-techniques like simulation and planning in a natural way. It also makes implementation of reasoning in knowledge-based systems (KBS) more direct than in Prolog. The application is an already existing KBS that guides a service technician in the task of diagnosing a specific device which is a measuring instrument for testing telecommunications equipment. The method used in the application is a problem solving method called TDFL. The TDFL method is a task specific problem solving method for technical diagnosis that gives strong support for knowledge acquisition. The method is adapted to cope with some features of the application. For example, it gives support for reducing the time required for observations and it handles parts that are not directly testable. This paper describes how to adjust the TDFL method to remedy some errors present in the original version; avoiding unnecessary search of the device and eliminating unnecessary confirmations. Some future extensions to both the TDFL method and the implementation are also presented; allowing the search for more than one fault and the possibility of turning the diagnosis backwards.
Björn Gambäck, Stefan Ljung
The paper describes how the Swedish Core Language Engine (S-CLE), a general-purpose natural-language processing system was extended to process questions posed to a Prolog database. Previous work on the S-CLE has included processing up to the level of quasi-logical form (QLF); here we address the problems encountered when extending that processing to ``pure'' logical form (LF) and translating the logical forms into questions to the SNACK-85 reginal database. We also show how some natural-language answers were generated from the original question-QLFs and the answers obtained from the database.
Björn Gambäck, Manny Rayner
The paper describes a Swedish-language customization (S-CLE) of the SRI Core Language Engine, A shorter version of this paper appears in L.Ahrenberg (ed.): Papers from the Third Nordic Conference on Text Comprehension in Man and Machine , Link Sweden, 1992. which has been developed at SICS from the original English-language version by replacing English-specific modules with corresponding Swedish-language versions. The S-CLE is intended to be used as a building block in a broad range of applications, such as data-base query system, machine translation systems, NL front-ends, speech-to-text/text-to-speech systems, and so on. Examples of the first two types of application already exist. The main part of the S-CLE is an extensive Swedish grammar that is compiled into parsing and generation modules. The grammar formalism is a type of unification grammar loosely based on Generalized Phrase Structure Grammar (GPSG). Generation is performed using the Semantic-Head-Driven algorithm. Analysis turns sentences into ``Quasi-Logical Form'' (QLF), a logical-form representation, while generation works in the opposite direction. Intermediate stages include processing of morphology, syntax and semantics. For knowledge-base applications, a separate module can convert QLFs into conventional scoped logical forms. After two-and-a-half years of work (approximately 45 person months), the first prototype system has a vocabulary of about 1900 words and covers a fairly broad range of possible grammatical constructions. Based on our experience in this project, we present in this paper detailed arguments to support the claim that customization of an English-language NLP system is a highly cost-effective way of constructing Swedish language systems with corresponding functionality.
Björn Gambäck
The paper describes S-VEX, the lexical acquisition component of the Swedish Core Language Engine (S-CLE). A shorter version of this paper appears in L.Ahrenberg (ed.): Papers from the Third Nordic Conference on Text Comprehension in Man and Machine , Link Sweden, 1992. The S-CLE is a general purpose natural language processing system for Swedish developed from its English counter-part, the SRI Core Language Engine. In parallel with the development of the S-CLE, a Swedish version of the English VEX (Vocabulary EXpander) system was designed. S-VEX allows for the creation of lexicon entries by users with knowledge of an application domain but not of linguistics or of the detailed workings of the system. The approach taken is based on eliciting grammaticality judgments and information of inflected forms interactively from the user. The S-VEX system and the lexicon of the S-CLE is described, as well as the problems of the specific lexical acquisition task and their solutions.
Thomas Sjöland
The functionalities of SICStus Objects, a system allowing object oriented programming in SICStus Prolog are shown and an example is presented: support software for building graphical user interfaces. This text assumes a basic knowledge about Prolog programming in SICStus Prolog and some intuition about object oriented programming. SICStus Objects was implemented as an embedded language in SICStus Prolog by Seif Haridi and Kent Boortz. SICStus Prolog is developed and maintained by Mats Carlsson, Stefan Andersson and Kent Boortz at SICS with support from Ellemtel Utvecklings AB.
Lars-Henrik Eriksson
The theory of partial inductive definitions is a mathematical formalism which has proved to be useful in a number of different applications. The fundamentals of the theory is shortly described. Partial inductive definitions and their associated calculi are essentially infinitary. To implement them on a computer, they must be given a formal finitary representation. We present such a finitary representation, and prove its soundness. The finitary representation is given in a form with and without variables. Without variables, derivations are unchanging entities. With variables, derivations can contain logical variables that can become bound by a binding environment that is extended as the derivation is constructed. The variant with variables is essentially a generalization of the pure GCLA programming language.
Mohammed Ali Khayri, Roland Karlsson, Shyam Mudambi
The Muse (multiple sequential Prolog engines) approach has been used to make a simple and efficient OR-parallel implementation of the full Prolog language. The performance results of the Muse system on bus-based multiprocessor machines have been presented in previous chapters, papers. This chapter paper discusses the implementation and performance results of the Muse system on switch-based multiprocessors (the BBN Butterfly GP1000 and TC2000). The results of Muse execution show that high real speedups can be achieved for Prolog programs that exhibit coarse-grained parallelism. The scheduling overhead is equivalent to around 8 -- 26 Prolog procedure calls per task on the TC2000. The chapter paper also compares the Muse results with corresponding results for the Aurora OR-parallel Prolog system. For a large set of benchmarks, the results are in favor of the Muse system.
Martin Aronsson
We will demonstrate various implementation techniques in the language GCLA. First an introduction to GCLA is given, followed by some examples of program developments, to demonstrate the development methodology. Other examples are also given to show various implementation techniques and properties of the system.
Mohammed Ali Khayri, Roland Karlsson
Almost any sequential Prolog system is in principle easy to extend for OR-parallelism, using the Muse execution model. To reduce your programming effort we have implemented the Muse scheduler, with a clean interface to the Prolog sequential engine. This interface is implemented as a set of C macros. The sequential Prolog system to be parallelized uses some of those macros provided by the Muse scheduler and must also provide some macros for the Muse scheduler. This chapter paper contains a definition and description of the required macros, emphasizing information needed by the Prolog engine programmer.
Roland Karlsson
This paper shows how to extend an existing Prolog system to automatically exploit OR-parallelism. The description starts with parallelizing pure Prolog, a Prolog version without either cut or side effects. The model is incrementally refined until finally reaching an efficient OR-parallel system for full Prolog with extra non-Prolog features. I have tried to keep the text as general as possible. When the text becomes too SICStus (my target Prolog system) specific some hints for the ordinary WAM is given. The chosen OR-parallel model is the Muse model. It is relatively straightforward using this model to extend most existing Prolog systems.
Bengt Ahlgren, Stephen Pink, Per Gunningberg
DTM, dynamic synchronous transfer mode, is a new time division multiplexing technique for fiber networks currently being developed and implemented at the Royal Institute of Technology in Stockholm, Sweden. This paper describes the hardware and software aspects of the design of an SBus host interface to the DTM network for a Sun SPARCstation. The interface is based on a dual port memory residing on the interface card and accesible over the SBus from the host CPU. The host operating system allocates message buffers directly in this memory. The interface has hardware support for segmenting and reassembling packets to and from the data units of the DTM. The software part of the interface manages the shared memory and the virtual circuits provided by the DTM network.
Anders Landin, Seif Haridi
The long latencies introduced by remote accesses in a large multiprocessor can be hidden by caching. Caching also decreases the network load. We introduce a new class of architectures called Cache Only Memory Archi-tectures (COMA). These architectures provide the programming paradigm of the shared-memory architectures, but have no physically shared memory; instead, the caches attached to the processors containallthe memory in the system, and their size is therefore large. A datum is allowed to be in any or many of the caches, and will automatically be moved to where it is needed by a cache-coherence protocol,which also ensures that the last copy of a datum is never lost. The location of a datum in the machine is completely decoupled from its address. We also introduce one example of COMA: the Data Diffusion Machine (DDM), and its simulated performance for large applications. The DDM is based on a hierarchical network structure, with processor/memory pairs at its tips. Remote accesses generally cause only a limited amount of traffic over a limited part of the machine.
Anders Landin, Seif Haridi
Large-scale multiprocessors suffer from long latencies for remote accesses. Caching is by far the most popular technique for hiding such delays. Caching not only hides the delay, but also decreases the network load. Cache-Only Memory Architectures (COMA), have no physically shared memory. Instead, all the memory resources are invested in caches, resulting in caches of the largest possible size. A datum has no home, and is moved by a protocol between the caches, according to its usage. It might exist in multiple caches. Even though no shared memory exists, the architecture still provides the shared memory view to a programmer. Simulation results from large programs running on 64 processors indicate that the COMA adapts well to existing programs for shared memory. They also show that an application with a poor locality can benefit by adopting to the COMA principle of no home for data, resulting in a reduced execution time of a factor three. In a COMA, a large majority of the misses are invalidation misses, or share misses caused by write-once/read-many behavior, or a producer-consumer relation, i.e. would ben- efit from write broadcast. A new protocol is proposed that behaves like a write-invalidate protocol by default for all data. A reader can detect its need for a write-broadcast behavior for a datum, which it enables by sending a subscribe request for the datum to the writer.
Björn Lisper
Concurrent assignments are commonly used to describe synchronous parallel computations. We show how a sequence of concurrent assignments can be formally derived from the schedule of an acyclic single assignment task graph and a memory allocation. In order to do this we develop a formal model of memory allocation in synchronous systems. We use weakest precondition semantics to show that the sequence of concurrent assignments computes the same values as the scheduled single assignments. We give a lower bound on the memory requirements of memory allocations for a given schedule. This bound is tight: we define a class of memory allocations whose memory requirements always meets the bound. This class corresponds to conventional register allocation for DAGs and is suitable when memory access times are uniform. We furthermore define a class of simple ``shift register'' memory allocation. These allocations have the advantage of a minimum of explicit storage control and they yield local or nearest-neighbour accesses in distributed systems whenever the schedule allows this. Thus, this class of allocations is suitable when designing parallel special-purpose hardware, like systolic arrays.
Pink Stephen, Craig Partridge
ST-2 is a revision of an experimental protocol designed to support applications which require guaranteed network services. ST-2 provides mechanisms for creating streams, tree-shaped delivery paths with performance guarantees, for applications which require such guarantees. As part of the MultiG project, the authors implemented ST-2 in the BSD system. The twin goals of this implementation were to see how easily a novel protocol like ST-2 could be incorporated into the BSD networking model and, more importantly, to thoroughly evaluate the ST-2 protocol. Our conclusions are that the BSD model proved quite general, requiring only modest changes (changes which were largely invisible to the application), but that the ST-2 protocol itself needs some reworking.
Hans Nilsson
The SICStus Prolog External Database implements an efficient way of storing possibly non-ground Prolog terms on disk with indexing on user specified parts of the terms. The model and the implementation are described and some performance data are given.
Martin Aronsson
We show how the programming language GCLA can be used to naturally express both relational and functional programs in an integrated framework. We give a short introduction to GCLA, and to the theory of partial inductive definitions on which GCLA is based. GCLA is best regarded as a logic programming language, but instead of saying that the query follows from the program in some a priori given logic, we say that the program defines the logic in which the query is proved. We then demonstrate how to implement both relational and functional programs as well as a combination of them in GCLA.
Gunnar Sjödin, Clas Löfwall
In this paper we prove that any subexpression of a correct judgement in Martin-Löf's Type Theory is strongly normalizable. We use the well-established technique with a ``computability predicate''. The logic used in the proof is classical set theory.
Sverker Janson, Seif Haridi
The Andorra Kernel Language (AKL) is introduced. It is shown how AKL provides the programming paradigms of both Prolog and GHC. This is the original goal of the design. However, it has also been possible to provide capabilities beyond that of Prolog and GHC. There are means to structure search, more powerful thanplain backtracking. It is possible to encapsulate search in concurrent reactiveprocesses. It is also possible to write a multi-way merger with constant delay.In these respects AKL is quite original. Although AKL is an instance of our previously introduced Kernel Andorra Prolog framework, this exposition contains important extensions, and a considerable amount of unnecessary formal overhead has been stripped away.
Dan Sahlin, Mats Carlsson
This paper describes how to extend the garbage collection for WAM so that it will shunt chains of bound variables if possible. Doing so has two advantages: 1. Space is saved by making it possible to deallocate the intermediate cells. This is particularly useful when those cells are associated with frozen goals. 2. Later dereferencing is speeded up by not having to follow long variable chains. The main complication of this optimization is the treatment of the trailed variables. We claim that all possible chains of variables are shunted by this algorithm. The algorithm has been implemented in SICStus Prolog, and benchmark results are presented in this paper. The full source code for the shunting algorithm is given in this paper.
Joachim Parrow, David Walker
In process algebras, bisimulation equivalence is typically defined directly in terms of the operational rules of action; it also has an alternative characterisation in terms of a simple modal logic (sometimes calledHennessy-Milner logic . This paper first defines two forms of bisimulation equivalence for the\031-calculus , a process algebra which allows dynamic reconfiguration among processes; it then explores a family of possible logics, with different modal operators. It is proven that two of these logics characterise the two bisimulation equivalences. Also, the relative expressive power of all the logics is exhibited as a lattice.
Anders Landin, Seif Haridi
Multiprocessors with shared memory are considered more general and easier to program than message-passing machines. The scalability is, however, in favor of the latter. There are a number of proposals showing how the poor scalability of shared memory multiprocessors can be improved by the introduction of private caches attached to the processors. These caches are kept consistent with each other by cache-coherence protocols. In this paper we introduce a new class of architectures called Cache Only Memory Architectures (COMA). These architectures provide the programming paradigm of the shared-memory architectures, but are believed to be more scal- able. COMAs have no physically shared memory; instead, the caches attached to the processors containallthe memory in the system, and their size is therefore large. A datum is allowed to be in any or many of the caches, and will automat- ically be moved to where it is needed by a cache-coherence protocol, which also ensures that the last copy of a datum is never lost. The location of a datum in the machine is completely decoupled from its address. We also introduce one example of COMA: the Data Diffusion Machine (DDM). The DDM is based on a hierarchical network structure, with processor/memory pairs at its tips. Remote accesses generally cause only a limited amount of traffic over a limited part of the machine. The architecture is scalable in that there can be any number of levels in the hierarchy, and that the root bus of the hierarchy can be implemented by several buses, increasing the bandwidth.
Joachim Parrow
(Revised and extended version of the paper "The Expressive power of simple parallelism" in the proceedings of PARLE '89 Vol. II, Eindhoven, June 1989, publ. as Springer Verlag LNCS 366 pages 389-405.) We explore an algebraic language for networks consisting of a fixed number of reactive units, communicating synchronously over a fixed linking structure. The language has only two operators: disjoint parallelism, where two networks are composed in parallel without any interconnection, and linking, where an interconnection is formed between two ports. The intention is that these operators corresponds to the primitive steps when constructing networks, and that they therefore are conceptually simpler than the operators in existing process algebras. We investigate the expressive power of our language. The results are: (1) Definability of behaviours: with only three simple processing units, every finite-state behaviour can be constructed. (2) Definability of operators: we characterise the network operators which are defiable wwithin the language; these turn out to include most operators previously suggested for describing parallelism. Our results hold for any cingruence between trace equivalence and observation equivalence.
Joachim Parrow
(Revised and extended version of a paper that appeared under the same title in the Proceedings of the 17th Colloquium on Automata, Languages and Programming, Warwick University, July 1990; Published as Springer Verlag LNCS 443 pages 540-552.) We define an algebraic language for networks of synchronously communicating processes. A node in the Network may have several ports; a port is either external to the whole network or connected through a link to another port. The language contains two types of operations: parallel composition of two networks, and interlinking of rwo external ports within a network. We interpret this language in two ways: first we give a structural semantics, where terms are mapped to graphs representing the structure of networks, and second we give a behavioural semantics, where terms are mapped to behaviour schemes. A schema corresponds to a behaviour parameterised on the behaviours of the network nodes. These semantics give rise to structural and behavioural equivalences. We compare the equivalences and give sound and complete axiomatisations.
Peter Sjödin
A technique is presented for translating LOTOS specifications into implementations executing as asynchronously communicating processes. This generation of implementations is described as transformations of LOTOS expressions. A protocol for implementing LOTOS synchronisation is described.
Hans Hansson, Bengt Jonsson
We present a logic for stating properties such as, "after a request for service there is at least a 98\045 probability that the service will be carried out within 2 seconds". The logic extends the temporal logic CTL by Emerson, Clarke and Sistla with time and probabil- ities. Formulas are interpreted over discrete time Markov chains. We give algorithms for checking that a given Markov chain satis- fies a formula in the logic. The algorithms require a polynomial number of arithmetic operations, in size of both the formula and\003This research report is a revised and extended version of a paper that has appeared under the title "A Framework for Reasoning about Time and Reliability" in the Proceeding of the 10thIEEE Real-time Systems Symposium, Santa Monica CA, December 1989. This work was partially supported by the Swedish Board for Technical Development (STU) as part of Esprit BRA Project SPEC, and by the Swedish Telecommunication Administration.1the Markov chain. A simple example is included to illustrate the algorithms.
Bengt Jonsson
(Revised and extended version of a paper that appeared under the title " A Fully Abstrtact trace Model for Dataflow Networks" in the Proceedings of the 16th Annual ACM Symposium on Principles of Programming Language, Austin Texas, January 1989.) A dataflow network consists of nodes that communicate over perfect unbounded FIFO channels. For dataflow networks containing only deterministic nodes, a simple and elegant semantic model has been presented by Kahn. However for nondeterministic networks the straight-forward generalization of Kahn's model is not compositional. We Present a compositional model for nondeterministic networks which is fully abstract, i.e. it has added the least amount of extra information to Kahn's model which is necessary for attaining compositionality. The model is based on traces. We also generalize our result, showing that the model is fully abstract also for classes of networks where nodes communicate over other types of asynchronous channels. Exaamples of such classes are networks with unordered channels, and networks with lossy channels.
Björn Gambäck , Manny Rayner
We argue that bidding in the game of Contract Bridge can profitably be regarded as a micro-world suitable for experimenting with pragmatics. We sketch an analysis in which a "bidding system" is treated as the semantics of an artificial language, and show how this "language", despite its apparent simplicity, is capable of supporting a wide variety of common speech acts parallel to those in natural languages; we also argue that the reason for the relatively unsuccessful nature of previous attempts to write strong Bridge playing programs has been their failure to address the need to reason explicitly about knowledge, pragmatics, probabilities and plans. We give an overview of Pragma, a system currently under development at SICS, which embodies these ideas in concrete form, using a combination of rule-based inference, stochastic simulation, and "neural-net" learning. Examples are given illustrating the functionality of the system in its current form.
Bengt Jonsson
We present a method for specification and verification of distributed systems that communicate via asynchronous message-passing. The method handles both safety and liveness properties. It is compositional, i.e., a specification of a composite system can be obtained from specifications of its components. Specifications are given as labeled transition systems with fairness properties, using a program-like notation with guarded multiple assignments. A specification denotes a set of allowed sequences of message transmissions and receptions, in analogy with the way finite automata are used as acceptors of finite strings. A lower-level specification implements a higher-level specification if all sequences allowed by the lower-level specification are also allowed by the higher-level one. We present a verification technique which reduces the problem of verifying the correctness of an implementation to classical verification conditions. Safety properties are verified by establishing a simulation between transition systems. Liveness properties are verified using methods for proving termination under fairness assumptions. Since specifications can be given at various levels of abstraction, the method is suitable in a development process where a detailed implementation is developed from an abstract specification through a sequence of refinement steps. The method is applied to a sliding window protocol, and to an algorithm by Thomas for updating a distributed database.
Roland Karlsson, Khayry Mohamed Ali
Muse(Multi-sequential Prolog engines) is a simple and efficient approach to Or-parallel execution of Prolog programs. It is based on having several sequential Prolog engines, each with its local address space, and some shared memory space. It is cur-rently implemented on a 7-processors machine with local/shared memory constructed at SICS, a 16-processors Sequent Symmetry, a 96-processors BBN Butterfly I, and a 45-processors BBN Butterfly II. The sequential SICStus Prolog system has been adapted to Or-parallel implementation. Extra overhead associated with this adapta-tion is very low in comparison with the other approaches. The speed-up factor is very close to the number of processors in the system for a large class of problems. The goal of this paper is to present the Muse execution model, some of its imple-mentation issues, a variant of Prolog suitable for multiprocessor implementations, and some experimental results obtained from two different multiprocessor systems.
Torket Franzén
Thomas Sjöland
An AND-parallel execution model for logic programs needs a representation of clauses that explicitly expresses the possible parallelism. It is natural to consider a clause body to be a set of indexed goals where the indices are partially ordered and the order represents the required execution model, so we need another representation which expresses the parallelism. We define an algorithm to generate balanced execution expressions for rapallel execution from the more general form with partially ordered indexed literals.
Mats Carlsson
This report describes algorithms for the compiler component of the Aurora Or-Parallel Prolog system. The compiler translates one Prolog clause at a time into a sequence of abstract instructions. The instruction set is based on the sequential Warren Ab- stract Machine (WAM) with extensions for full Prolog, shallow backtracking, memory management and garbage collection, and for the SRI model of or-parallel execution of Prolog. Most of the described algorithms apply to compilation of sequential Prolog programs. The extensions introduced to support or-parallelism are minor, and concern pruning operators (cut and commit) and compile-time allocation of binding array offsets for permanent variables (generalised environment trimming). Code generation proper is kept separate from register allocation, and uses heuristics for finding a compilation order which minimises the number of register-register copies. After such copies have been coalesced where possible, register allocation is performed in a single pass over the intermediate code. The various compilation phases are described in detail, and the implementation is compared with some other compilers.
Mats Carlsson, Péter Szeredi
Aurora is a prototype Or-Parallel implementation of the full Prolog language fot shared-memory multiprocessors, developed as part of an informal research collaboration known as the "Gigalips Project". This report describes the abstract machine of the implementation, expressed in terms of a Prolog engine adapted for Or-Parallel execution by means of the SRI model. An algorithms interface defining the communication between the engine and sheduler components of each Aurora process is described, and enables different engine and scheduler components to be used interchangeably. Both the interface and the engine are Fundamentally revised versions of those used in previous generations of the implementation.
Philippe Mathieu, Torbjörn Keisu
In this short paper, we show how to relate a constraint programming environment with some kind of functional attribute grammars.
Mats Carlsson
The cost of backtracking has been identified as one of the bottlenecks in achieving peak performance in compiled Prolog programs. Much of the backtracking in Prolog programs is shallow, i.e. is caused by unification failures in the head of a clause when there are more alternatives for the same procedure, and so special treatment of this form of backtracking has been proposed as a significant optimisation. This paper describes a modified WAM which optimises shallow backtracking. Four different implementation approaches are compared. A number of benchmark results are presented, measuring the relative tradeoffs between compilation time, code size, and run time. The results show that the speedup gained by this optimisation can be significant.
Seif Haridi, Sverker Janson
The logic programming language framework Kernel Andorra Prolog is defined by a formal computation model. In Kernel Andorra Prolog, general combinations of concurrent reactive languages and nondeterministic transformational languages may be specified. The framework is based on constraints. The languages Prolog, GHC, Parlog, and Atomic Herbrand, are all executable in the Kernel Andorra Prolog computation model. There are instances of the framework in which all of these languages are embeddable.
Philippe Mathieu, Torbjörn Keisu
This short note aims to present foundations for constraint logic programming. By logic programming, we understand in this paper the PROLOG paradigm. But it will be clear that we do reduce the problem to adding a new package to PROLOG. We argue that constraint logic programming should be defined as a new paradigm for programming: the LOGIC PROGRAMMING + SYMBOLIC COMPUTATION paradigm. Our system incorporates as a very basic, all the existing systems incorporating constraints in a logic environment.
Sverker Janson, Manny Rayner
We present a framework for reasoning about the concepts of "knowing what" and "finding out", in which the key concept is to identify "finding out the answer to question Q" with "achieving a situation in which Q is decidable" . We give examples of how the framework can be used to formulate non-trivial problems involving the construction of plans to acquire and use information, and go on to demonstrate that these problems can often be solved by systematic application of a small set of goal-directed backward-chaining rules. In conclusion, it is suggested that systems of this kind are potentially implementable in l-Prolog, a logic programming language based on higher-order logic.
Christer Samuelsson, Manny Rayner
Explanation-based learning is a technique which attempts to optimiz performance of a rule-based system by adding new rules constructed from generalizations of successfully-solved examples. The paper summarizes previous work showing how this idea can be used in natural language processing, and describes experiments in which the EBL method was applied to the CHAT-80 system of Pereira and Warren. In particular, we address the problem of assuring the utility of learning a rule, since the benefit of a learned rule may not outweigh the increased search time incurred in checking its applicability. We show that this problem can be overcome in the NL domain by indexing acquired rules by their lexical constraints, which in general vastly reduces the number of potentially applicable rules. Such an indexing method was implemented and timing studies were made comparing its access speed to that of normal linear search. The indexing scheme required an average access time of 35 - 40 ms independent of the number of learned rules. The results suggest that the overhead of the indexing scheme is small.
Dan Sahlin, Torkel Franzén, Seif Haridi
A complete theorem prover for intuitionistic predicate logic based on the cut-free calculus is presented. It includes a treatment of "quasi-free" identity based on a delay mechanism and a special form of unification. Several important optimizations of the basic algorithm are introduced. The resulting system is available in source form from SICS; an Appendix gives some idea of its performance.