Wyniki wyszukiwania - BazTech

1

A note on the complexity of scheduling of communication-aware directed acyclic graph

Musial J., Guzek M., Bouvry P., Blazewicz J.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2018

|

Vol. 66, nr 2

187--191

EN

The most recent incarnation of distributed paradigm is cloud computing. It can be seen as the first widely accepted business model of mass consumption of the distributed computing resources. Despite the differences in business models and technical details regarding cloud platforms, the distributed computing underlies cloud. Communications in cloud systems include transmissions of the results of cloud applications, users interactions, and exchange of data between different services that compose applications. The latter becomes more critical as applications become richer as well as more complex, and may consist of services operated by various providers. The effective communication between components of cloud systems is thus critical to the end user satisfaction and to the success of cloud services. We will discuss different cloud computing models (communication aware and unaware). Main focus will be placed on communication-aware directed acyclic graph (CA-DAG), which extends the classical DAG model by explicitly modeling communication tasks. Moreover, we will analyze and consult computational complexity of this innovative distributed computation model inspired by the characteristics of cloud computing. Providing a proof of strong NP-hardness of the problem allows for a future implementation and evolution of the communication-aware DAG models.

2

Exact and heuristic approaches to solve the Internet shopping optimization problem with delivery costs

Lopez-Loces M. C., Musial J., Pecero J. E., Fraire-Huacuja H. J., Blazewicz J., Bouvry P.

International Journal of Applied Mathematics and Computer Science

|

2016

|

Vol. 26, no. 2

391--406

EN

Internet shopping has been one of the most common online activities, carried out by millions of users every day. As the number of available offers grows, the difficulty in getting the best one among all the shops increases as well. In this paper we propose an integer linear programming (ILP) model and two heuristic solutions, the MinMin algorithm and the cellular processing algorithm, to tackle the Internet shopping optimization problem with delivery costs. The obtained results improve those achieved by the state-of-the-art heuristics, and for small real case scenarios ILP delivers exact solutions in a reasonable amount of time.

3

Algorithms solving the Internet shopping optimization problem with price discounts

Musial J., Pecero J. E., Lopez-Loces M. C., Fraire-Huacuja H. J., Bouvry P., Blazewicz J.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2016

|

Vol. 64, nr 3

505--516

EN

The Internet shopping optimization problem arises when a customer aims to purchase a list of goods from a set of web-stores with a minimum total cost. This problem is NP-hard in the strong sense. We are interested in solving the Internet shopping optimization problem with additional delivery costs associated to the web-stores where the goods are bought. It is of interest to extend the model including price discounts of goods. The aim of this paper is to present a set of optimization algorithms to solve the problem. Our purpose is to find a compromise solution between computational time and results close to the optimum value. The performance of the set of algorithms is evaluated through simulations using real world data collected from 32 web-stores. The quality of the results provided by the set of algorithms is compared to the optimal solutions for small-size instances of the problem. The optimization algorithms are also evaluated regarding scalability when the size of the instances increases. The set of results revealed that the algorithms are able to compute good quality solutions close to the optimum in a reasonable time with very good scalability demonstrating their practicability.

4

Predictive modeling in a VoIP system

Simionovici A. M., Tantar A. A., Bouvry P., Didelot L.

Journal of Telecommunications and Information Technology

|

2013

|

nr 4

32--40

EN

An important problem one needs to deal with in a Voice over IP system is server overload. One way for preventing such problems is to rely on prediction techniques for the incoming traffic, namely as to proactively scale the available resources. Anticipating the computational load induced on processors by incoming requests can be used to optimize load distribution and resource allocation. In this study, the authors look at how the user profiles, peak hours or call patterns are shaped for a real system and, in a second step, at constructing a model that is capable of predicting trends.

5

Hash function generation by means of Gene Expression Programming

Varrette S., Muszyński J., Bouvry P.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2012

|

Vol. 12, no. 3

37--53

EN

Cryptographic hash functions are fundamental primitives in modern cryptography and have many security applications (data integrity checking, cryptographic protocols, digital signatures, pseudo random number generators etc.). At the same time novel hash functions are designed (for instance in the framework of the SHA-3 contest organized by the National Institute of Standards and Technology (NIST)), the cryptanalysts exhibit a set of statistical metrics (propagation criterion, frequency analysis etc.) able to assert the quality of new proposals. Also, rules to design "good" hash functions are now known and are followed in every reasonable proposal of a new hash scheme. This article investigates the ways to build on this experiment and those metrics to generate automatically compression functions by means of Evolutionary Algorithms (EAs). Such functions are at the heart of the construction of iterative hash schemes and it is therefore crucial for them to hold good properties. Actually, the idea to use nature-inspired heuristics for the design of such cryptographic primitives is not new: this approach has been successfully applied in several previous works, typically using the Genetic Programming (GP) heuristic [1]. Here, we exploit a hybrid meta-heuristic for the evolutionary process called Gene Expression Programming (GEP) [2] that appeared far more efficient computationally speaking compared to the GP paradigm used in the previous papers. In this context, the GEPHashSearch framework is presented. As it is still a work in progress, this article focuses on the design aspects of this framework (individuals definitions, fitness objectives etc.) rather than on complete implementation details and validation results. Note that we propose to tackle the generation of compression functions as a multi-objective optimization problem in order to identify the Pareto front i.e. the set of non-dominated functions over the four fitness criteria considered. If this goal is not yet reached, the first experimental results in a mono-objective context are promising and open the perspective of fruitful contributions to the cryptographic community.

6

Cryptography based upon Cellular Automata

Seredyński F., Bouvry P., Szaban M.

Studia Informatica : systems and information technology

|

2003

|

Vol. 2(2)

73--85

EN

New results concerning application of cellular automata (CAs) to secret key cryptography is described in this paper. One dimensional nonuniform CAs are considered for generating pseudorandom number sequences used in a secret key cryptographic system. The quality of PNSs highly depends on set of applied CA rules. The search of rules relies on an evolutionary technique called cellular programming. Different rule sizes are considered. As the result of collective behavior of discovered set of CA rules very high quality PNSs are generated. Indeed the quality of PNSs outerforms the quality of known one dimensional CA-based PNS generators used for secret key cryptography. The extended set of CA rules proposed in this article makes the cryptography system much more resistant on attacks.