Monografias em Ciência da Computação

2006

ABSTRACTS

Departmento de Informática 
Pontifícia Universidade Católica do Rio de Janeiro - PUC-Rio
Rio de Janeiro - Brazil

This file contains a list of the technical reports of the Departmento de Informática, Pontifícia Universidade Católica do Janeiro - PUC-Rio, Brazil, which are published in our series Monografias em Ciência da Computação (ISSN 0103-9741), edited by Prof. Carlos Lucena. Please note that the reports not available for download are available in their print format and can be obtained via the e-mail below.
For any questions, requests or suggestions, please contact:
Rosane Castilho bib-di@inf.puc-rio.br

Last update: 24/AUGUST/2006

INDEX

[MCC01/06]
GATTI, M.A.C.; LUCENA, C.J.P.; BRIOT, J.-P.; GUESSUOM, Z. Towards a fault-tolerant open multi-agent platform based on a law-governed approach. 25 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Multi-agent systems are composed by autonomous components (agents) which interact to achieve their goals. Due to their autonomy and no control point of decisions making, it is hard to control and forecast its behavior during their interactions. If we consider that fault tolerance is a technique which can be very useful to increase the reliability of a distributed system, and considering that an Open Multiagent System (MAS) is a special type of such systems, there is a need to study the particular characteristics of these Open MAS in order to reach higher degrees of dependability. Despite all the research done in the last years on the development of fault-tolerant applications and of approaches to enforce secure interaction protocols in multi-agent systems, there is no mechanism which uses the law elements of interaction’s control which improves the agent criticality analysis. As this mechanism would increase dependability of those systems, it is proposed a solution to achieve it through the integration of the DarX framework, which is a framework for dynamic replication, and the XMLaw, which is a declarative language for implementing the law enforcement approach for regulating agents’ interaction.

[MCC02/06]
STAA, A.v.; LUCENA, C.J.P.; CARVALHO, G.R.; BRIOT, J.-P.; CHOREN, R.; GUESSUOM, Z. Treating fault-tolerant concerns in models and architectures for multi-agent systems. 11 p. Eng. E-mail: arndt@inf.puc-rio.br

Abstract: In this paper, we propose the introduction of law-governance to describe fault tolerance aspects in multi-agent systems (MAS) design models since laws delimit the things that can happen in a system. In the design-time phase, we propose an extension to the ANote modeling language to incorporate the law-governed approach. In the run-time stage, agent architectures should provide the means for the correct execution of the system, i.e. they should ensure the system will execute according to its requirements. Thus we propose the use of the DimaX. Using DimaX, we will seek to provide mechanisms to detect and recover from failures in the system. The proposed approach is detailed in the paper.

[MCC03/06]
MORENO, M.F.; COLCHER, S.; SOARES, L.F.G. Adaptable resource management based on the virtual resource tree model. 13 p. Eng. E-mail: lfgs@inf.puc-rio.br

Abstract: This paper presents an abstract model for resource management mechanisms, called Virtual Resource Tree (VRT). The VRT model is developed aiming at meeting different end-to-end Quality of Service (QoS) requirements demanded by multimedia applications. Scalability plays an important role in this scenario, bringing new mandatory features for resource management, such as the distributed management of heterogeneous resources and the support for adapting the different underlying management algorithms. In addition, this paper discusses the main issues towards the definition of the VRT file system (VRT-FS). VRT-FS is a framework that shows how, with a simple and familiar design, the functionalities of the VRT model can be ported to network operating systems.

[MCC04/06]
GATTI, M.A.C.; STAA, A.v. Testing & debugging multi-agent systems: a state of the art report. 24 p. Eng. E-mail: arndt@inf.puc-rio.br

Abstract: Current research and development of agent-based systems has focused primarily on architectures, protocols, frameworks, messaging infrastructure and community interactions. As intelligent agent-based systems take over operations in the financial community, transportation, manufacturing, utilities, aerospace, and the military, assurances will need to be given to the owners and operators of these systems assuring that these non-deterministic learning systems operate correctly. In this State of the Art report (SotA), we will give an introduction to work presented in the area of testing and debugging distributed systems composed of complex autonomous entities (agents). We will provide pointers to work by large players in the field. We will also discuss the debugging of multi-agents systems. We will explain why this kind of system must be handled differently than less complex systems.

[MCC17/06]
COSTA, A.D.; LUCENA, C.J.P.; SILVA, V.T. Remodelando e estendendo o Agent Society Framework. 126 p. Port. E-mail: lucena@inf.puc-rio.br

Abstract: This project contemplates the extension of a framework called Agent Society Framework(ASF) created with the goal to represent a concept very spread out on the research area of Multi-Agent System: agents society, or either, systems that represent agents playing roles in organizations. The document presents which extensions were realized, which scientific contribution it offers for the area, and which is it's differentials in relation to others frameworks.

[MCC18/06]
IMPERIAL, J.C.; HAEUSLER, E.H. Some strategies for the automatic use of Hoare Logic. 9 p. Eng. E-mail: hermann@inf.puc-rio.br

Abstract: This papers aims at showing some strategies to construct a proof of correctness of a program in such way to increase the automation of the process. To achieve this, the proposed strategies reduce drastically the search space and the need of user interaction.

[MCC19/06]
MONTEIRO, J.M.; LIFSHITZ, S.; BRAYNER, A. Automated selection of materialized views. 11 p. Eng. E-mail: sergio@inf.puc-rio.br

Abstract: Materialized views can provide massive improvements in query processing time, especially for aggregation queries over large tables. Due to the space constraint and maintenance cost constraint, the materialization of all views is not possible. Therefore, a subset of views needs to be selected to be materialized. The problem is NP-hard, therefore, exhaustive search is unfeasible. Further, a judicious choice must be cost-driven and influenced by the workload experienced by the system. For this reason, some past papers have looked at the problem of automated selection of materialized views for SQL workloads. Though, no prior work considers the problem of dynamic and automated creation (self-maintenance) of materialized views. This paper presents an architecture for completely automatic selection and creation (maintenance) of materialized views.

[MCC20/06]
MONTEIRO, J.M.; LIFSHITZ, S.; BRAYNER, A. Estado da arte em auto-sintonia de transações. 21 p. Port. E-mail: sergio@inf.puc-rio.br

Abstract: Database Management Systems (DBMSs) are a vital component for the modern companies operation, and as such, they must provide great data availability and high performance in the data access. With this purpose, practically all DBMS supply tuning knobs that can be adjusted in accordance with the workload characterictics. However, this task becomes each time more difficult, due to increasing complexity of the databases (DBs). The autonomic computing systems have detached as a promising approach to deal with the tuning complexity. Such systems are intelligent enough to manage its proper performance, having as main characteristics the capacity to perceive the environment, particularly its workload, and automatically reconfigure its resources and parameters in a proper manner. This characteristic is called of self-tuning, or database self-tuning. Typically, databases are used in environments where many users work concurrently. The concurrent data access can generate inconsistencies in the database. For this reason, the concurrent data access need be controlled. The leaders approaches to control concurrency are based on locks. However, the great number of lock conflicts can lead to a data access containment, and consequently to undesirable delays and reworks that could be prevented. To minimize these problems the majority of the DBMSs provides a set of tuning knobs, related with the transaction management, that can be adjusted. In this work, we present the state of the art in transactions self-tuning.

[MCC21/06]
MONTEIRO, J.M.; ENDLER, M.; LIFSHITZ, S.; BRAYNER, A. Um mecanismo para a consistência de dados replicados em computação móvel. 22 p. Port. E-mail: endler@inf.puc-rio.br

Abstract: The recent advances in portable computer together with the developments in wireless communication technology are allowing users of portable equipment to maintain the network connection while they move about freely, having access to shared resources, services and information. This paradigm is called mobile computing. Mobile computing allows for the development of new and sophisticated database applications. Such applications require the reading of current and consistent data. In order to improve the data availability, increase performance and maximize throughput, data replication is used. However, due to inherent limitations in mobile environments, where there is typically great limitations for communications between mobile equipment and prolonged lack of connection between these pieces of equipment, making necessary changes in the concurrency control and replica control mechanisms be implemented. This paper proposes a new protocol that guarantees the consistency of replicated data in a mobile computing environment.

[MCC22/06]
MORENO, L.; ARAGAO, M.P.; UCHOA, E. Column generation based heuristic for a helicopter routing problem. 11 p. Eng. E-mail: poggi@inf.puc-rio.br

Abstract: This work presents a column generation based heuristic algorithm for the problem of planning the flights of helicopters to attend transport requests among airports in the continent and offshore platforms, on the Campos basin, for the Brazilian State Oil Company (Petrobras). We start from a previous MIP based heuristic for this Helicopter Routing Problem and add column generation procedures that improve the solution quality. This is done by extending the earlier formulation and providing an algorithm to find optimal passenger allocation to fixed helicopter routes. A post optimization procedure completes the resulting algorithm, which is more stable and allows consistently finding solutions that improves the safety and the cost of the one done by the oil company experts.

[MCC23/06]
CUNHA, L.M.; LUCENA, C.J.P. Clustering the semantic web challenge's applications: architecture and metadata overview. 84 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: This paper describes a first attempt to classify the applications submitted to the Semantic Web Challenge, which is a parallel event in the International Semantic Web Conference. So far, 35 applications were submitted in the last 3 editions of the challenge. This work will investigate some aspects about the applications in order to come up with a(some) framework(s) for Semantic Web applications that attends the requirements of the challenge, consequently, showing the benefits of the Semantic Web techniques to the final user. Our first step in that direction is to present some metadata and the architecture of the submitted applications on this paper, as well as a first speculation about the categories of Semantic Web Applications submitted to the challenge so far.

[MCC24/06]
RUSSO, E.E.R.; RAPOSO, A.B.; FERNANDO, T.; GATTASS, M. Emergency environment for the Oil & Gas exploration and production industry. 6 p. Eng. E-mail: mgattass@inf.puc-rio.br

Abstract: The objective of this work is to present some of the key challenges faced when defining and building virtual workspaces for oil & gas Exploration & Production (E&P) activities, such as 3D geomodelling, seismic interpretation, real-time drilling follow-up and correction, offshore structures' design, static and dynamic simulations of these offshore structures, oil pipelines' monitoring and emergency situations' handling. Also a case study focusing on emergency scenarios with extreme conditions is discussed in details.

[MCC25/06]
RUSSO, E.E.R.; RAPOSO, A.B.; GATTASS, M.; FERNANDO, T. A metamodel for collaborative virtual workspaces configuration: application in disaster management of oil & gas offshore structures. 136 p. Eng. E-mail: mgattass@inf.puc-rio.br

Abstract: Many companies have been creating virtual teams that bring together geographically dispersed workers with complementary skills, increasing the demand for CSCW (Computer Supported Cooperative Work) applications. In order to facilitate the development of a wide range of these collaborative applications, we should offer a general architecture that is adaptable to different situations, tasks, and settings in a flexible way. This work investigates how a distributed workspace environment can support disaster management, involving distributed collaborative technical teams. We first identify the requirements for the distributed workspace, from the stakeholders involved in a disaster, and analyse the commercial emergency systems available. We then elaborate a multi-perspective metamodel to support configuring this collaborative virtual workspace. Finally a prototype for oil & gas offshore structures disaster management based on our multi-perspective metamodel is derived and an HLA (High Level Architecture) compliant implementation for this prototype is developed as a proof-of-concept of the metamodel technology.

[MCC26/06]
MELLO, H.; ENDLER, M. Identificação de região de congestionamento através de comunicação inter-veicular. 16 p. Port. E-mail: endler@inf.puc-rio.br

Abstract: IVC (Inter-Vehicle Communication) is a promising technology for the next generation of automotive vehicles. The envisaged benefits include safer vehicle control, multi-vehicle cruise control, better traffic planning, Internet connectivity, location-based services, etc. A typical application of IVC is traffic jam-avoidance. Recent publications already address this issue, but most of them focus on preventing the occurence of traffic jams. Conversely,this article addresses metropolitan-area scenarios where drivers are already trapped in a jam and need assistance in how to escape them. The proposed service employs a distributed algorithm to build an approximate congestion perimeter. This task is carried out by dissemination of positioning data of vehicles vertices of a polygon that is a close approximation of the congestion area. Given the polygon and its current location, a vehicle can then plan its escape-way route from the traffic jam.

[MCC27/06]
GATTI, M.A.C.; CARVALHO, G.R.; PAES, R.B.; LUCENA, C.J.P.; BRIOT, J.-P. Structuring a law case for law-governed open multi-agent systems. 30 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: In an open multi-agent system, where the complexity and uncertainty are issues that must be analyzed during the development and evolution, the experience of emergent behavior makes it even more important to consider dependability attributes. It is harder to design and implement requirements related to dependability in law-governed multi-agent systems mainly because there is no control point over such systems. To this end, the use of an enforcement mechanism and an adapted dependability case approach, which we define as a Law Case, permits to control the failures and to promote the benefits and also contributes to tame the uncertainty presented by open multi-agent systems. Therefore, the goal of this work is show how to struture a Law Case through a sample scenario in open multi-agent systems regulated by a law-enforcement mechanism.

[MCC28/06]
LIMA, L.S.; ENDLER, M.; SOARES, L.F.G.; GOMES, A.T.A.; ZIVIANI, N.  Grades sem fio: desenvolvendo aplicações baseadas no compartilhamento de recursos.  42 p. Port.  E-mail: endler@inf.puc-rio.br

Abstract: Originally, a concept for sharing computing resources among wired participants, grid computing is gradually being extended to support scenarios, including wireless networks, which introduce a variety of novel devices and possible uses.  Wireless grids are resource sharing networks spontaneously formed by nomadic devices.  In this work we present the main challenges in the development of P2P applications for wireless grid netowrks, focusing on the resource management system.

[MCC29/06]
LIMA, L.S.;  SOARES, L.F.G.; ENDLER, M.  WiMAX: padrão IEEE 802.16 para banda larga sem fio. 57 p. Port. E-mail: endler@inf.puc-rio.br

Abstract: The main purpose of this work is to give an overview of IEEE 802.16, a standard for wireless broadband access, with a special focus on its mechanism for providing QoS.  We compare the standards IEEE 802.11, IEEE 802.16 and IEEE 802.20 with the intention to identify the part each standard plays, according to its characteristics, in an integrated wireless network infrastructure, and show how they coexist and complement each other in this network infrastructure.  We conclude with some discussion on a general architecture for provision of QoS in wireless networks integrating the standards IEEE 802.11 and IEEE 802.16.

[MCC30/06]
SILVESTRE, B.O.; RODRIGUEZ, N.L.R.; BRIOT, J-P. Sincronização em um modelo RPC orientado a eventos. 21 p. Port. E-mail: noemi@inf.puc-rio.br

Abstract: The growth of the Internet has caused distributed programmers to face highly geographically distributed scenarios. The ALua system offers a base for developing event-based applications, using a callback-based programming model to process events. We developed a RPC library for ALua that offers the programmer a more friendly abstraction to create event-based applications. However, the RPC model introduces concurrent event processing, even if only in explicit program points. In this work we analyze several inter and intra-process synchronization mechanisms which have been proposed in the literatures and implement some of them on our RPC library.

[MCC31/06]
FELICÍSSIMO, C.H.; LUCENA, C.J.P.; BRIOT, J-P.; BREITMAN, K.K.; CASANOVA, M.A.; CHOREN, R. Towards a normative ontology for implementing contextual regulations in open MAS. 14 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: We believe that the Semantic Web will be a huge machine-understandable open net composed of several information repositories plus intelligent cooperative entities, executing along the principles of multi-agent systems (MAS). Also, agents will be able to joint and leave MAS freely, seeking to achieve their designed goals faster. In such scenario, some level of regulation is necessary. Along these lines, this paper presents our ongoing work for dynamic contextual regulations in open multi-agent systems - called DynaCROM. DynaCROM is based on a top-down modeling of contextual laws, on a normative meta-ontology for laws semantics and on a rule support for composing contextual laws. DynaCRON results in a straightforward method for regulations in open MAS, obtained with few ontology-based rules. For instance, with only 19 rules for 4 particular MAS contexts (environment, organization, role and interaction), DynaCROM permits a total of 349 customized compositions of contextual laws.

[MCC32/06]
FELICISSIMO, C.H.; LUCENA, C.J.P.; BRIOT, J-P.; BREITMAN, K.K.; CASANOVA, M.A.; CHOREN, R. Inferring contextual laws with rules for regulations in open multi-agent systems. 14 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Rules and Rules-based inference engines have become a powerful technology to support basic Semantic Web tasks. In this work, we focus our attention in the essential task of regulation in open domains. More precisely, the rule layer of DynaCROM - our approach for dynamic contextual regulation in open multi-agent systems (MAS) - will be detailed. The DynaCROM rule layer permits developers of system regulation to easily customized several compositions of contextual laws, by activating and deactivating (few) rules.  Thus, by continuous snapshots of a regulated system, developers can analyze agents' performance and, then, manually influence both law enforcement and agents' behavior. The result is a more balanced regulation. Moreover, meta-rules can also be specified in order to automatically raise pre-defined sets of rules, when their conditions are satisfied. Therefore, the rule layer introduces flexibility and precision in the DynaCROM solution, as a straightforward method for regulation in open MAS.

[MCC33/06]
PAES, R.B.; GATTI, M.A.C.; CARVALHO, G.R.; RODRIGUES, L.F.C.; LUCENA, C.J.P. A middleware for governance in open multi-agent systems. 11 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: Interacting entities in many distributed systems have to follow certain protocols and interaction rules. This paper presents a middleware to regulate agent interactions in systems characterized mainly by the need of having control over the actions that an agent can perform. The solution is based on the ideas proposed in the field of governance of agent systems, where governance can be defined as the set of approaches that aim to establish and enforce some structure, set of norms or conventions, that articulate or restrain interactions in order to make agents more effective in attaining their goals or more predictable.