Abstract: A three-dimensional complex is a partition of a three-dimensional manifold into simple cells, faces, edges and vertices. We consider here the problem of automatically producing a `` nice '' geometric representation (in
, for
) of an arbitrary 3D complex, given only its combinatorial description. The geometric realization is chosen by optimizing certain aesthetic criteria, measured by certain `` energy functions. ''.
Summary: Alur et al. presented an algorithm for the problem of verifying probabilistic real-time processes against specifications given by temporal automata; and raised the issue of verifying specifications given by non-deterministic automata. In this article, we give a partial answer to the question, extending the method in such a way that processes, with an acceptable constraint, can be tested against any temporal automaton. Among these processes, for example, digital circuit models are included where the main property is that the delay distributions have a non-zero lower limit.
Abstract: Alur et al. presented an algorithm for the problem of verifying deterministic timed automata specifications of probabilistic real-time systems given as generalized semi-Markov processes; and posed the question of the verification of nondeterministic specifications. We give a partial answer to the question, extending their method so that processes, with a fairly acceptable restriction, can be tested against any timed automaton. These include, for instance, real-time models of digital circuits where the key property is that the delay distributions have non-zero lower bounds.
Summary: Geographic Information Systems have experienced important advances motivated by new information technologies, which have also expanded their potential for use beyond specialists in the field. In this sense, GIS should consider the user's familiarity with Cartography and its traditional way of representing natural or man-made phenomena. Understanding the construction and interpretation of maps as communication activities, this work aims to assess the power of expression of GISs with regard to the representation of cartographic elements, from the Semiotic approach. Results obtained from the comparison of the semiotic systems of Cartography and of the GISs show a great difference in the communication potential in each of the domains.
Abstract: Several improvements are noticed on Geographic Information Systems, motivated by the general trends in information technologies, expanding their potential uses to domain experts. In that sense, GIS should consider the user's familiarity with Cartography and its traditional way of representing natural phenomena. Understanding the construction and interpretation of maps as communication activities, this paper evaluates the expression power of GIS relatively to their cartographic elements, based on a Semiotic approach. Results obtained from the comparison between Cartographic and GIS semiotic systems show a great difference in the potential for communication for each one of the domains.
Abstract: The Cube Packing Problem (CPP) is defined as follows. Find a packing of a given list of (small) cubes into a minimum number of (larger) identical cubes. We show first that the approach introduced by Coppersmith and Raghavan for general online algorithms for packing problems leads to an online algorithm for CPP with asymptotic performance bound 3.954. Then we describe two other offline approximation algorithms for CPP: one with asymptotic performance bound 3.466 and the other with 2.669. A parametric version of this problem is defined and results on online and offline algorithms are presented. We did not find in the literature offline algorithms with asymptotic performance bounds as good as 2.669.
Abstract: Reassembling unknown broken objects from a large collection of fragments is a common problem in archeology and other fields. Computer tools have recently been developed, by the authors and by others, which try to help by identifying pairs of fragments with matching outline shapes. These tools have been succesfully tested on small collections of fragments; here we address the question of whether they can be expected to work also for practical instances of the problem (
to
fragments). To that end, we describe here a method to measure the average amount of information contained in the shape of a fracture line of given length. This parameter tells us how many false matches we can expect to find for that fracture among a given set of fragments. In particular, the numbers we obtained for ceramic fragments indicate that fragment outline comparison should give useful results even for large instances.
Abstract: In this paper, we generalize to the oriented projective plane
an algorithm for constructing all order
Voronoi diagrams in the Euclidean plane. We also show that, for fixed
and for a finite set of sites, an order
Voronoi diagram in
has an exact number of regions. Furthermore, we show that the order
Voronoi diagram of a set of sites in
is antipodal to its order
Voronoi diagram,
.
Abstract: A recovery line is the most recent consistent global checkpoint from which a distributed computation can be restarted after a failure. This paper presents a new quasi-synchronous checkpointing protocol where processes propagate their local knowledge about the recovery line, named PRL.
Protocols that enforce rollback-dependency trackability (RDT) are domino-effect free and are usually based on vector clocks. Protocols that avoid the domino effect without enforcing RDT are usually index-based. The protocol proposed by Baldoni, Quaglia, and Ciciani (BQC) was the first non-RDT domino-effect free protocol to use a vector clock. In BQC, each process keeps and propagates a matrix of
of integers, where
is the number of processes in the computation. PRL is also vector-clock based, domino-effect free, and non-RDT, but lowers the complexity of the required control information from
to
. We present theoretical and simulation results giving evidence that PRL reduces the number of induced checkpoints in comparison with BQC.
Abstract: Distributed computing often gives rise to complex concurrent and interacting activities. In many cases, several concurrent activities may be working together, ie, cooperating, to solve a given problem; in other cases the activities may be independent but sharing common system resources for which they should compete. In practice, different kinds of concurrency might coexist in a complex application which thus will require a general supporting mechanism for controlling and coordinating complex concurrent activities. Many difficulties and limitations occur when the object and action model is used to support cooperating activities. This paper discuss some of these difficulties and limitations and then presents an alternative model for constructing fault-tolerant distributed systems based on the concept of Coordinated Atomic (CA) actions which provides uniform support for both cooperative and competitive concurrency.
Abstract: We present a fast, synchronous, cryptographic protocol by means of which Alice can send Bob a stream B, with assurance of non-repudiation of reception of B or any prefix of it by Bob. Bob, on the other hand, can taste to any third party the origin of B or any prefix of it. While the protocol's synchronous nature may prevent its use in some broadcast-type applications, its speed and mutual non-repudiation capabilities make it well suited for several e-commerce applications.
Summary: In this text, major problems for labor scheduling are addressed and several solution strategies are described. Such problems are recognized as difficult problems in Combinatorial Optimization and have been solved until optimality. Proven optimal solutions for real and large instances are achieved using a hybrid approach that integrates techniques of Mathematical Programming and Programming by Constraints. A declarative programming environment was used to develop constraint-based models. The declarative nature of this environment proved to be valuable during the modeling of complex constraints of the problem and, particularly, when exploring, in an efficient way, the enormous space of viable solutions. The code was tested in real instances of the problem arising from the daily operation of two bus lines of a Brazilian urban transport company that serves a large metropolitan region. Some of these instances contain a number of entries greater than
and could be resolved to optimality on a typical personal microcomputer, in an acceptable computing time.
Abstract: We consider several strategies for computing optimal solutions to large scale crew scheduling problems, which are known to be notoriously difficult combinatorial optimization problems. Provably optimal solutions for very large real instances of such problems were computed using a hybrid approach that integrates mathematical and constraint programming techniques. A declarative programming environment was used to develop the constraint based models. The declarative nature of such an environment proved instrumental when modeling complex problem restrictions and, particularly, in efficiently searching the very large space of feasible solutions. The code was tested on real problem instances, stemming from the operation of two bus lines of a typical Brazilian transit company that serves a major urban area. Some of those instances contained an excess of
entries and could be solved to optimality in an acceptable running time when executing on a typical desktop PC.
Summary: The objective of this work is the application of formal specification techniques to model realistic distributed systems. The formal models are based on hybrid automata. The target system of this work are segments of a subway network. The analysis and verification of the model considered, as well as the synthesis of certain important parameters of the model, are aided by semi-automatic tools. In this way, the validation of the behavior of the described system was obtained automatically, as well as the synthesis of critical parameters for the mesh operation.
Abstract: The aim of this work is to apply formal specification techniques to model real-time distributed systems. The formal models are based on hybrid automata. The target systems of this work are segments of subway network. Semi-automatic tools aid in the analysis and verification of the model. The model is also used to synthesize some important parameters of the system under consideration.
Summary: Fault tolerance is an important requirement in the development of modern computer systems. However, building fault-tolerant systems is a complex specialized activity throughout the system's development cycle. In addition, ideally the provision of fault tolerance should be done in a structured and non-intrusive way. In this context, we propose a set of standards (design decisions) that help the development of fault-tolerant object-oriented systems. These standards are based on the ideal fault-tolerant component model. The concept of computational reflection is used in order to obtain an explicit separation between the normal and abnormal behavior of the components. Normal activities, which implement the functional requirements of the application, are implemented at the base level, while abnormal activities, which implement fault tolerance mechanisms, are implemented at the meta-level, through meta-objects. The standards represent design decisions that must be made in the development of fault-tolerant object-oriented systems in order to obtain a structured design, where the introduction of fault tolerance mechanisms is done in a controlled and consistent manner.
Abstract: Fault tolerance represents a major challenge to design of moderns computing systems. However, the construction of fault-tolerant systems is not a simple task. It requires the use of appropriate techniques during the whole software development cycle. Besides, ideally fault-tolerance mechanisms should be incorporated to the original system in a structured and non-intrusive manner. In this context, we propose a set of patterns (design decisions) that make easier the task of building fault-tolerant object-oriented systems. This patterns are based on idealized fault-tolerant component model. The computational reflection concept is used aiming a clear separation of the normal activity from the abnormal activity of a software component. The normal activities, that implement the functional requirements, are implemented by base-level objects, while the abnormal activities, that implement the fault tolerance mechanisms, are implemented by meta-level objects. The patterns are design choices that should be taken during the software development cycle aiming a structured design, where the fault-tolerance mechanisms is incorporated to the original system in a structured and controlled manner.
Summary: This paper explores mobility in the context of managing open distributed services. A set of agents is defined to explore the managed environment using a successive detailing approach to potential problems. The implementation considers distributed systems based on objects according to OMG / CORBA. An extension of the work is proposed to adjust the managed system, using the balance of computational resources with the aid of an availability service.
Abstract: This paper explores the mobility paradigm in the context of management of open distributed services. A pool of agents is defined in order to explore the managed environment based on the zooming of potential problems. The implementation considers an open distributed environment based on OMG / CORBA objects. An extension is presented for adjusting the managed system based on the balancing of the computational resources with the help of an availability service.
Abstract: the vertex deletion number
of the graph
is the minimum number of vertices that must be deleted from
to produce a planar graph. The splitting number
of
is the smallest number of vertex splitting operations that must be applied to
to make it planar. Here we determine these topological invariants for the graph family
, a regular triangulation of the torus obtained by adding parallel diagonal edges to the faces of the rectangular toroidal grid
. Specifically, we prove that the obvious upper bound
is also a lower bound.
Abstract: The vertex deletion number of a graph
is the smallest integer
such that there is a planar induced subgraph of
obtained by the removal of
vertices from
. In this work we study the vertex deletion number of
, the rectangular grid with toroidal topology. We prove the extact result
, where
is the number of true conditions among the following: (i)
and (ii)
.
Summary: This document describes the implementation and initial experiences with a restriction programming model for the monthly scheduling of more than 1500 nursing professionals at Unicamp University Hospital. The implementation includes a user-friendly interface.
This report is based on Denise G. Batista's final graduation project.
Abstract: This document describes the implementation and early experience with a constraint programming model for the monthly scheduling of more than 1500 nursing personel at Unicamp's University Hospital. The implementation includes a user-friendly interface.
This report is based on the final graduation project of Denise G. Batista.
Abstract: We propose a method for compressing programs running on embedded DSPs. Program expression trees are decomposed into opcode and operand sequences called patterns. We show that DSP program patterns have exponential frequency distributions. Based on that, we encode patterns using a mix of variable-length and fixed-length codewords. A decompression engine is proposed, which converts patterns into uncompressed instruction sequences. The experimental results reveal an average compression ratio of 67% for typical DSP programs running on the TMS320C25 processor. This ratio includes an estimate of the size of the decompression engine.
Abstract: This paper presents a method for minimizing test suites for embedded, nondeterministic Finite State Machines. The method preserves the fault coverage of the original test suite, and can be used in conjunction with any technique for generating test suites. The minimization is achieved by detecting and deleting redundant test cases in the test suite.
Summary: Fault-tolerant distributed systems are partially based on the existence of checkpointing and recovery mechanisms by state regression. Another important mechanism for these systems is that which allows the monitoring of their state and the prompt reaction to changes that affect their expected functioning. Although these two mechanisms are strongly associated, the vast majority of fault-tolerant systems built to date favor the implementation of checkpointing mechanisms, rather than mechanisms for monitoring. Progressive views are sequences of consistent global checkpoints that could have occurred in this order during the execution of the computations. They were called progressive because the algorithm for their determination minimizes the necessary setback during the system recovery phase, in case of partial hardware failure. In this article, we comment on the usefulness of progressive views for the development of more efficient protocols for checkpointing and for the integration of checkpointing, state recovery and monitoring mechanisms.
Abstract: Fault-tolerant distributed systems are partially based on the implementation of checkpointing and rollback-recovery mechanisms. Another important mechanism associated to tolerance of faults is the one that allows a system to monitor its state and to react to exceptional behavior. Checkpointing and rollback-recovery are already part of most of the fault-tolerant systems implemented to date. This situation does not apply to monitoring mechanisms, especially to systems that integrate monitoring, checkpointing and rollback-recovery. Progressive views are formed by a sequence of consistent global checkpoints that may have occurred in this order during the execution of the system. Progressive views are called progressive because they have been designed to minimize the rollback of the system when a partial failure of hardware occurs. This article dicusses the application of progressive views towards the deployment of more efficient checkpointing mechanisms and its application to the integration of checkpointing, rollback-recovery and monitoring for fault-tolerant distributed systems.
Summary: Algorithms for determining consistent global states in a distributed system are of great importance for tasks involving monitoring and reconfiguration, such as deadlock detection, token loss detection, debugging, garbage collection, among others. This document covers theoretical aspects of determining consistent global states and describes a programming environment designed and implemented to allow experimentation with algorithms to obtain consistent global states.
Abstract: Algorithms for the determination of consistent global states in a distributed system have major importantce in tasks that require monitoring and reconfiguration, such as the deadlock detection, token loss detection, debugging, and garbage colletion, among others. This document addressed theoretical aspects of consistent global state determination, and describes a programming environment designed and implemented to allow experimentation on algorithms for obtaining consistent global states.
Abstract: Running code downloaded from the network raises several security issues. Unlike the Java programming language, most existing reflective architectures have failed to address these issues. There is a clear need for mechanisms to impose some discipline on the interactions between objects and meta-objects, so as to retain or improve the security mechanisms offered by programming languages.
While the ability to dynamically associate objects with meta-objects is essential for developing flexible and adaptable reflective applications, reliability depends on mechanisms to regulate reconfigurations.
In the design of Guaraná, a language-independent meta-object protocol, we have attempted to address these issues. This papers describes and justifies some of the decisions we have made in order to allow developers of reflective applications to balance flexibility and security.
Abstract: We present a general algorithm to align two protein sequences that uses the concept of don't care regions. It is based on the classical Needleman-Wunsch dynamic programming method using affine penalty functions. We tested the algorithm on two problems, comparing it against the standard dynamic programming algorithm. Results were not consistently or significantly better, suggesting that refinements are needed.
Abstract: This work describes a meta-object library and a reflective object-oriented framework for cryptography-based security, which focuses on three points: the easy reuse of cryptography-aware code, the easy composition of cryptographic services and the transparent addition of cryptography-based security to third-party code, from the application programmer's point of view. Such a framework is applicable to both third-party commercial-off- the-shelf applications and legacy systems, and is based on a reflective variation of a pattern language for cryptographic software we had proposed. We are using Guarana, a reflective variation for the Java programming language which encourages composition of meta-objects, to implement our framework.
Abstract: In this work we show that compliance to Tropyc, a pattern language for cryptographic software, is a good criteria for Cryptographic Application Programming Interfaces (CAPIs) evaluation. Tropyc documents the constraints over cryptographic services combination by limiting the number of valid patterns. Also, we use this criteria to evaluate a group of six CAPIs: IBM's CCA, RSA's Cryptoki, Microsoft's CryptoAPI, Sun's JCA / JCE, X / Open's GCS-API and Intel's CSSM-API. We show that these CAPIs lack the ability of cryptographic service composition, an important feature of modern applications, such as electronic commerce systems.
Abstract: Object-oriented applications with non-functional cryptography-based security requirements can benefit from a flexible design in which cryptographic objects and application functional objects are weakly coupled. In this work, the combination of computational reflection and cryptographic design patterns is proposed in order to improve reuse of both design and code (while decreasing coupling and increasing flexibility) of cryptographic components. The usefulness of this approach is in the transparent addition of cryptography-based security to third-party commercial-off-the-shelf components. A reflective extension for the cryptographic design pattern is proposed. This extension is implemented in Guarana, the meta-object protocol for Java.
Abstract: This work description tropyc, a pattern language for cryptographic software based on a generic object-oriented cryptographic architecture. Nine patterns are described: Information Secrecy, Sender Authentication, Message Integrity, Signature, Signature with Appendix, Secrecy with Integrity, Secrecy with Sender Authentication, Secrecy with Signatureand Secrecy with Signature with Appendix. They are classified according to four fundamental objectives of cryptography (confidentiality, integrity, authentication and non-repudiation) and compose a closed set of patterns for this domain. These patterns have the same dynamic behavior and structure. We abstracted these aspects into a Generic Object-Oriented Cryptographic Architecture ( GOOCA).
Abstract: Synchronous user interface is a medium where all objects being shared on it can be viewed indifferently from the geographical location and its users can interact with each other in real-time. Designing such an interface for users working collaboratively requires to deal with a number of issues. Herein, our concerns lies on the design of control component of Human-Computer Interaction (HCI) and corresponding User Interface (UI) software that implements it. We make use of our approach to interactive system development based on the MPX - Mapping from PAN (Protagonist Action Notation) into Xchart (eXtended Statechart) - and illustrate it by presenting the case study of a collaborative application.
Abstract: In this paper, we describe an envelope process for the fractal Brownian motion (fBm) process. We investigate the time scale of interest of queuing systems fed by a fBm process. We also introduce the Fractal Leaky Bucket, a novel policing mechanism which is able to accurately monitor self-similar sources. Moreover, we show expressions for computing the equivalent bandwidth of an aggregate of heterogeneous self-similar sources.
Instituto de Computação :: State University of Campinas
PO Box 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas / SP - Brazil • Phone: [19] 3521-5838 |