Scientific Annals of Computer Science
"Alexandru Ioan Cuza" University of Iaşi
Volume XI, 2002
Agent-Client Interaction in a Web-Based E-Commerce System.,
pages 1-10
Minor GORDON, Marcin PAPRZYCKI, Violetta GALANT
Abstract |
BibTeX
| Article page
In order for agent technology to fulfill its promise, it must be
integrated with other existing technologies. In this paper we address one
of the problems occurring in a real-world agent integration project --
interaction between agents and non-agents. The proposed solution is
designed to provide non-agents (clients in particular) access to the agent
services, without restricting the agents.
Cluster and Grid Computing for Solving Large Structural Biology Problems.,
pages 11-45
Dan MARINESCU, Yongchang Ji, Gabriela MARINESCU
Abstract |
BibTeX
| Article page
In this paper we present some of the most challenging computational
problems posed by the three-dimensional atomic structure
determination of viruses that do not exhibit icoshedral symmetry. The algorithms
for solving these problems on clusters and computational grids
use information gathered from electron microscopy.
Constructing Correct Communicating Systems,
pages 46-68
Traian MUNTEAN
Abstract |
BibTeX
| Article page
This paper presents a model for the design of correct distributed
systems of communicating mobile objects. It first makes a proposal for
introducing a new refinement operator for construction of complex systems that
is dedicated to take into account distribution from the very specification level
through all stepwise refinement process towards implementations. Our operator
expresses how a whole system composed of many concurrent and
communicating processes can be designed by refinement. The proposed
operator is compatible with classical algorithmic and data refinements found for
instance in the B Method, CSP, Action Systems and others models.
Then we introduce a diffuse-model, based on broadcasting communications
instead of largely used point-to-point communication schemes. For this model
we have developed a process calculus for reconfigurable communicating
systems based on mobile processes which has broadcast as unique basic
exchange mechanism, b$pi$ calculus 15,16?. We have provided a full operational
semantics for this calculus and we illustrate its expressiveness through some
examples taken from complementary classes of applications (built correct
exchange mechanisms for messages in reconfigurable networks, checking for
inconsistencies of transactions between mobile distributed processes). We have
proposed three behavioural equivalencies for reasoning about such systems,
namely, barbed equivalence, step-equivalence and labelled bisimilarity. An
important result 15?, is that all these relations coincide, providing different
ways to study the equivalence/non-equivalence of two systems and also a
further refinement model for broadcasting systems.
Parallel Processing Approaches for Multi Disciplinary Optimization,
pages 69-79
Florin MANOLACHE, Sorin COSTINER, Ricardo MUNOZ, Shubhro GHOSH, Nikunj GUPTA, Roderick ROSS
Abstract |
BibTeX
| Article page
Multi Disciplinary Optimization (MDO) problems are often
encountered in many industrial areas. MDO refers to the
optimization of systems of subsystems (disciplines). The
optimization of the full system is often reduced to a hierarchy of
optimizations at subsystem and system levels. This paper presents
a concise survey of major MDO approaches and discusses
opportunities of parallel processing (PP) at four algorithmic
levels of the approaches, i.e., the subsystem solver level, the
subsystem optimization level, the full system optimization level,
and the sequence of problems level. Advantages of different PP
implementations of the MDO approaches are outlined. Special
emphasis is put on vertical PP processing, where one thread treats
a hierarchical structure (e.g., a full system evaluation),
inter-thread communication is low, and processor loads are uniform.
Parallel Extension of a Dynamic Performance Forecasting Tool,
pages 80-93
Eddy CARON, Frederic SUTER
Abstract |
BibTeX
| Article page
This article presents an extension of the textsc{Fast} library to handle parallel routines.
textsc{Fast} is a dynamic performance forecasting tool in a metacomputing environment.
Here we propose to combine estimations given by textsc{Fast} about sequential computation
routines and network availability to parallel routine models coming from analysis. This association
will be defined and detailed on two examples and validated experimentally.
Distributed Threads in Java,
pages 94-109
Danny WEYNS, Eddy TRUYEN, Pierre VERBAETEN
Abstract |
BibTeX
| Article page
In this paper, we study the problems of thread identity that arise with adapting a local Java program for execution in a distributed environment. When using a distributed control flow programming model like Java RMI or OMG CORBA, the programmer should take into account an inherent shift of semantics. We experienced a particular problem with shift of thread semantics when extending a serialization mechanism for JVM threads to a distributed setting. More specific, we encountered the problem of losing logical thread identity when the control crosses system boundaries. We solved this problem by introduced the generic notion of distributed thread identity in Java programming. Propagation of a globally unique, distributed thread identity provides a uniform mechanism by which all the program�s constituent objects involved in a distributed control flow can uniquely refer to that distributed thread as one and the same computational entity. We have implemented distributed thread identity by means of byte code transformation of application programs. In the paper, we will use the serialization of a distributed execution state as a case to illustrate the value of our Java extension.
Dynamic Load Balancing Strategies for Parallel Computers,
pages 110-120
A. OSMAN, H. AMMAR
Abstract |
BibTeX
| Article page
This paper deals with the problem of load balancing of parallel applications. Based on the study of recent work in the area, we propose a general taxonomy for describing and classifying the growing number of different load balancing techniques. This gives a thorough overview of different algorithms, helping designers to compare and choose the most suitable strategy for a given application. To illustrate the applicability of the taxonomy, different well-known load balancing algorithms are described and classified according to it. Also, the paper discusses the use of the taxonomy to construct the most suitable load balancing algorithms for different parallel algorithmic paradigms.
A Recursive Method for Graph Scheduling,
pages 121-131
Claude TADONKI
Abstract |
BibTeX
| Article page
In this paper, we propose a formal method for scheduling regular graphs. The idea is to perform
a decomposition of the graph into semi-isomorphic subgraphs, and then recursively propagate a given schedule
of the initial subgraph of the chain over the whole graph. The method derives regular schedules, and the class of problems
on which it can be applied is less restrictive than what we usually observe. Some complexity results
are provided, together with a study on how to use the method as best as possible. The tiling
issue is studied in many of its aspects, assuming that the method has been first applied
in a fine grain context.
A Convergence Proof of FGDLS when the Workload is Monotous,
pages 132-141
Tatiana TABIRCA, Len FREEMAN, Sabin TABIRCA
Abstract |
BibTeX
| Article page
In this paper we consider convergence of the feedback-guided dynamic
loop scheduling (FGDLS) method that was proposed in Bull et al.~
cite{BullFD} and Bull cite{Bull}. The method uses a feedback-guided
mechanism to schedule a parallel loop within a sequential outer loop.
Computational studies have shown that the loop bounds defined by the
method are convergent (for a constant workload or for a workload that
changes only slowly with the outer sequential loop) to the optimal
loop partition. In an earlier paper cite{Tab2001b} we established
formally that the FGDLS algorithm is guaranteed to converge, for a
constant workload, provided that the variations in workload with
iteration index are bounded. In this paper we extend this analysis to
establish convergence of the method when the workload is monotone with
iteration index.
Designing and Developing Multi-Agent Systems,
pages 142-153
Sinica ALBOAIE, Gabriel CIOBANU
Abstract |
BibTeX
| Article page
This article presents the experience of the authors in designing and
developing multi-agent software systems. We describe LFlag, a library that
implements a simple name service for agents within an Intranet and some
mechanisms for agents mobility and for their communication. We also
present a distributed address space for active objects and a software
implementation of this called Omega. Finally, we describe a new
development called AgKA and the possible ways AgKA could improve our
work and interactions in a distributed environment.
A database for Dynamic Distributed Content and its Application,
pages 154-170
Wolfgang HOSCHEK
Abstract |
BibTeX
| Article page
In a distributed system such as a DataGrid, it is often desirable to maintain
and query dynamic and timely information about active participants such as services,
resources and user communities. This enables information discovery and
collective collaborative functionality that operate on the system as a whole,
rather than on a given part of it. However, it is not obvious how a database
(registry) should maintain information populated from a
large variety of unreliable, frequently changing, autonomous and heterogeneous
remote data sources. In particular, how can one avoid sacrificing reliability,
predictability and simplicity while allowing to express powerful queries over
time-sensitive dynamic information?
We propose the so-called textit{hyper registry}, which
has a number of key properties. An XML data model allows for structured and
semi-structured data, which is important for integration of heterogeneous
content. The XQuery language allows for powerful searching, which is critical
for non-trivial applications. Database state maintenance is based on soft
state, which enables reliable, predictable and simple content integration from
a large number of autonomous distributed content providers. Content link,
content cache and a hybrid pull/push communication model allow for a wide range
of dynamic content freshness policies, which may be driven by all three system
components: content provider, hyper registry and client.
Implementing the WebCam 2 Distributed Computing Platform with XML,
pages 171-179
John MORRISON, Philip HEALY
Abstract |
BibTeX
| Article page
Implementation details of the WebCom 2 distributed computing platform are
presented, focusing in particular on the benefits gained through the use of XML
for expressing, executing and and pickling computations. The operation of
various WebCom 2 features implemented with the aid of XML are examined,
including specifying computations, code distribution, and exception handling.
The area of interoperabilty with common middleware protocols is also explored.
Decomposition of the Computation Area in the Parallel Implementation of the FDTD Algorithm.,
pages 180-192
Wojciech WALENDZIUK, Jaroslaw FORENC
Abstract |
BibTeX
| Article page
In the following paper a two-dimensional parallel algorithm FDTD is presented. This algorithm uses a decomposition of a space domain into sub-areas. In addition, the shapes of the dielectrics are approximated with the groups of rectangles, which are described by coordinates. The paper also contains the results of the tests analysing the relation of the computation times to the communication times into two types of the connection topology of the computation nodes. The computations were made on a homogeneous cluster of personal computers.
Implementation of the Approximate String Matching Application on a Cluster of Heterogeneous Workstations,
pages 193-204
Panagiotis MICHIAILIDIS
Abstract |
BibTeX
| Article page
In this paper we present a distributed approximate string matching
implementation on a parallel architecture with heterogeneous workstations
using MPI library. This implementation is based on the following
optimal distribution strategy in order to minimise the string matching time:
text collection is distributed proportional to workstation's speed. We tested
this distributed implementation and drew experimental results. Using the
optimal distribution method, the obtained time reduction of approximate string
matching algorithm were between 73.75% and 83.05%, compared to the uniform
allocation method. Further, we also proposed an analytical model that agrees
well with our experimental measurements.
Constructing Energy-Efficient Broadcast Trees in Wireless Ad Hoc Networks,
pages 205-213
A.T. CHRONOPOULOS, S. PONIPIREDDY, J. SARANGAPANI
Abstract |
BibTeX
| Article page
The wireless networking environment presents formidable challenges to the study of
broadcasting and multicasting problems. Energy efficiency is a measure of performance in broadcast
and multicast operations. We consider the problem of broadcast in Ad Hoc wireless networks. We study
the feasibility of constructing a broadcast tree while maintaining the quality of
service (Qos) in terms of Signal to Interference
ratio (SIR). We present simulation results and comparisons.
Testing Theories for Broadcasting Processes,
pages 214-230
Cristian ENE, Traian MUNTEAN
Abstract |
BibTeX
| Article page
This paper presents a theory of testing for processes calculi which have
broadcast as basic communication primitive. Firstly, we justify the necessity of an
alternative theory to bisimulations for broadcasting calculi.
Then, we remind $CBS$ without message passing and $bpi$-calculus, and we adapt the
definitions of {sl may testing} and {sl must testing} in the framework of broadcasting
calculi. Finally, we give a direct characterization for these pre-orders.
A Process Algebra for Predictible Control Systems,
pages 231-245
Nicolae MARIAN
Abstract |
BibTeX
| Article page
This paper presents Process Algebra for Predictible Control Systems (PAPCS) as a model for specifying and analysis of concurrent, time and resource dependent, distributed control systems. Instantaneos, prioritized events are used for process synchronization, more or less as in other existing process algebra approaches. Events with bound delays are used for interprocess communication. The building blocks of PAPCS are processes, consisting of activities, by their turn combining resource, priority, and time consuming composite functions. Activities can generate specific reactions to timing and/or events. They can also include variables in a C like statement. Because of introducing prioritized resources and events, our algebra allows activities or events to take priority over others and therefore to capture a notion of preemption. Fixed-priority scheduling of execution and communication is used in order to assure safe and preditable behaviour, in the context of local and remote interactions. Timing analysis techniques can be carried out. Operators like interrupt and timeout are integrated in PAPCS. Using the notion of bisimulation as a basis, we develop a behavioral equivalence and axiomatize it for finite processes. Simple examples are given that highlight the utility of the model
Development Methodology of Multichannel Symmetric Block,
pages 246-258
A. MELNYK, T. KORKISHK
Abstract |
BibTeX
| Article page
Modern tasks of information protection permanently demand to increase the performance of the computer means for the symmetric block cipher (SBC) algorithms execution, especially in the multichannel processing of the intensive data streams in the real time scale, thus causing the usage of the application-specific multichannel block cipher processors. In this work the development methodology of the multichannel SBC processors is proposed because of very tedious and complex development cycle, the necessity of the high quality design assuring and design errors elimination. The structure of the application-specific multichannel SBC processor based on dedicated to the channels processing units is the result of the development process by the proposed methodology. Formalization of every design methodology step establishes the preconditions for the creation of the multichannel SBC processors automated development means.
Impact of a Realistic Workload in Perr-to-Peer Systems. A Case Study: Freenet,
pages 259-270
Georges Da COSTA, Olivier RICHARD
Abstract |
BibTeX
| Article page
This paper addresses the problem of the study of the performance
evaluation and behavior of the large scale Peer-to-Peer file sharing
systems. In particular the impact of realistic workload is considered
by evaluating the Freenet system. This evaluation is achieved by a
simulation approach. A set of inputs is determined as well as their
distribution law in order to generate a more realistic workload. One of
them is an original characterization of user's requests. An other
contribution is to show the impact of these more realistic inputs on the
overall system performances. Notably new abrupt behaviors in the
learning process are described.
Ad Hoc Metacomputing with Compeer,
pages 271-277
Keith POWER, John MORRISON
Abstract |
BibTeX
| Article page
Although metacomputing allows the exploitation of geographically seperate, heterogenous networks and resources,
use of current metacomputing environments is not feasible for everyone.
Most metacomputers are so feature rich that they carry a long, complicated installation procedure, requiring knowledge
of accounting procedures, access control lists and user management, all of which differ between systems. They can have high
administrative overhead, and a steep learning curve which restricts their utility to organisations which can afford these
costs.
This paper presents a framework for dynamic construction of an ad hoc metacomputer, temporarily established
as needed for the sole purpose of executing once off applications.
The system incorporates fault tolerance, load balancing and addresses security.
It is described here together with two sample applications.
Probes Coordination Protocol for Network Performance Measurement,
pages 278-286
R. HARAKALY, P. PRIMET, F. BONASSIEUX, B. GAIDIOZ
Abstract |
BibTeX
| Article page
Fast expansion of Grid technologies and of distributed computing on Internet
emphasizes the importance of network performance measurement. The nature of some
network measurements methods like TCP throughput or latency evaluation, are very
sensitive to concurrent measurements that may devalue the results. We present
Probes Coordination Protocol (PCP) which can be used to schedule different
network monitoring tasks. The protocol we propose is designed to be open,
customizable, robust, secure and scalable. We present results of its evaluation
and of experiment periodicity measurements.
Communication on the Fly in a System of Dynamic SMP Clusters,
pages 287-303
Marek TRUDUJ, Lukasz MASKO
Abstract |
BibTeX
| Article page
The paper presents new architectural solutions for parallel systems built of dynamic shared memory processor clusters based on busses. The proposed architecture enables run-time switching of processors between clusters combined with parallel data reads by many processors what is called communication on the fly. Before execution, programs are structured accordingly to macro-data flow graphs in which task composition and communication are so defined, as to eliminate reloading of data caches during task execution. A task can be executed if all data it requires have been introduced to the respective processor�s data cache. An extended macro-data flow graph representation is introduced that includes modeling of program execution control in the system regarding data cache functioning, data bus arbiters, switching processors between clusters and multiple parallel reads of data on the fly. The proposed graph representation enables simulated realistic symbolic execution of program graphs, based on decomposition of parallel processes onto dynamic SMP clusters and communication on the fly.
On the Speedup of Parallel Iterative Numerical Methods,
pages 304-317
Dana PETCU
Abstract |
BibTeX
| Article page
Arguments are given for the fact that the speedup of parallel iterative methods is mainly influenced by the speedup at one
iterative step. A performance model is build under the assumption of a message-passing computing system. Numerical tests on
pa-ral-lel and distributed computing environments confirm the correctness of the theoretical model at least in the case of
iterative methods for ordinary differential equations and time-dependent partial differential equations.
Comparison of WebCom in the Context of Job Management Systems,
pages 318-326
John MORRISON, Brian CLAYTON, Adarsh PATIL
Abstract |
BibTeX
| Article page
A 2001 report for the NSA LUCITE Task Order on Productive Use of
Distributed Reconfigurable Computing compares 12 Job Management Systems
using 25 criteria designed to reflect "the most relevant system characteristics
needed in the targeted distributed system for reconfigurable computing".
This paper presents a brief overview of the WebCom Meta computer and uses
the previously mentioned characteristics to position it in relation
to existing systems.
Agent-Client Interaction in a Web-based E-Commerce System,
pages 327-336
M. GORDON, M. PAPRZYCKI, V. GALANT
Abstract |
BibTeX
| Article page
In order for agent technology to fulfill its promise, it must be
integrated with other existing technologies. In this paper we address one
of the problems occurring in a real-world agent integration project --
interaction between agents and non-agents. The proposed solution is
designed to provide non-agents (clients in particular) access to the agent
services, without restricting the agents.
a Protocol to Manage Distributed Real-Time Transaction Commit,
pages 337-348
Laurent AMATON, Bruno SADEG, Samia SAAD-BOUZEFRANE: RT-DIS-COM
Abstract |
BibTeX
| Article page
In a real-time distributed database system, the main problem is to maintain the database consistency, while insuring that each transaction meets its deadline. Moreover, in many current applications, there is a great need to deal with precedence relationships between transactions. Managing the distributed transaction commit is the main operation that influences these characteristics. In this paper, we exploit a causal-ordering protocol to manage the global commit of real-time transactions in a distributed database, by insuring the precedence relationships between transactions on one hand, and by taking account of messages priorities on the other hand. This protocol is also based on the subtransactions duplication and parallelization within each site and the borrowing of data that allows the use of data before and after they are updated. Then we show that the protocol we propose permits to the global transactions to respect their precedence relationships, and to more of them to meet their deadlines.
Distributed Data Mining,
pages 349-
Valerie FIOLET (University of Lille), Bernard TOURSEL
Abstract |
BibTeX
| Article page
The knowledge discovery in databases, equally called Data Mining, is an engineering more and more valued. The huge amount of data to process is more and more significant and requires to have ressort to parallel processing.
We take special interest in the search of association rules, and consider a distributed approach to the problem. Such an approach requires to distribute data to process independently the obtained fragments. The research of association rules generally based on a global criterion on the entire dataset, existing algorithms set number of communications unsuited to a distributed approach on a network of stations.
Therefore we took interest in heuristic approaches aiming to distribute the database in a coherent way so that independent processes on the obtained parts allow to lose a minimum of rules.
