International Journal of Foundations of Computer Science

This work reviews a number of algorithms to solve the location management problem in mobile networks for both static and dynamic scenarios. In the static mode, results of five algorithms are used to highlight the pros and cons for each algorithm. These results provide new insight into the mobility management problem that can influence the design of future wireless networks. In the dynamic mode in which mobile users' past movement patterns are used in making future paging decisions by the network, the performance of an online location management algorithm is examined under different deployment setups. Performance results of this algorithm show its advantages over the currently implemented and/or proposed static location management systems (including GSM).

In the present paper, we propose P systems that work in a constant number of steps. We first propose two P systems for computing multiple input logic functions. An input of the logic functions is a set of n binary numbers of m bits, and an output is a binary number defined by the logic functions. The first and second P systems compute AND and EX-OR functions for the input, and both of the P systems work in a constant number of steps by using O(mn) types of objects, a constant number of membranes, and evolution rules of size O(mn).

Next, we propose a P system for the addition of two binary numbers of m bits. The P system works in a constant number of steps by using O(m) types of objects, a constant number of membranes and evolution rules of size O(m²). We also introduce a P system that computes the addition of two vectors of n binary numbers of m bits by using the above P system as a sub-system. The P system for vector addition works in a constant number of steps by using O(mn) types of objects, a constant number of membranes, and evolution rules of size O(m²n).

We consider a game-theoretic bin packing problem with identical items, and we study the convergence time to a Nash equilibrium. In the model proposed, users choose their strategy simultaneously. We deal with two bins and multiple bins cases. We consider the case when users know the load of all bins and cases with less information. We consider two approaches, depending if the system can undo movements that lead to infeasible states. Let n and m be, respectively, the number of items and bins. In the two bins case, we show an O(log log n) and an O(n) bounds when undo movements are allowed and when they are not allowed, resp. In multiple bins case, we show an O(log n) and an O(nm) bounds when undo movements are allowed and when they are not allowed, resp. In the case with less information, we show an O(m log n) and an O(n³m) bounds when undo movements are allowed and when they are not allowed, resp. Also, in the case with less information where the information about completely filled/empty bins is not available, we show an O(m²log n) and an O(n³m³) bounds when undo movements are allowed and when they are not allowed, resp.

We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. This problem is closely related to the job scheduling on parallel machines, called the machine covering problem, where its goal is to assign jobs to parallel machines such that each machine is covered as much as possible. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 – ε for any constant ε > 0 in polynomial time unless P=NP, even if all edge weights belong to {1, 2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time -approximation algorithm for MAXMINO where w_max and w_min denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than w_min is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph.

Genetic algorithms (GAs) have been well applied in solving scheduling problems and their performance advantages have also been recognized. However, practitioners are often troubled by parameters setting when they are tuning GAs. Population Size (PS) has been shown to greatly affect the efficiency of GAs. Although some population sizing models exist in the literature, reasonable population sizing for task scheduling is rarely observed. In this paper, based on the PS deciding model proposed by Harik, we present a model to represent the relation between the success ratio and the PS for the GA applied in time-critical task scheduling, in which the efficiency of GAs is more necessitated than in solving other kinds of problems. Our model only needs some parameters easy to know through proper simplifications and approximations. Hence, our model is applicable. Finally, our model is verified through experiments.

In this paper we consider the operator mapping problem for in-network stream processing applications. In-network stream processing consists in applying a tree of operators in steady-state to multiple data objects that are continually updated at various locations on a network. Examples of in-network stream processing include the processing of data in a sensor network, or of continuous queries on distributed relational databases. We study the operator mapping problem in a "constructive" scenario, i.e., a scenario in which one builds a platform dedicated to the application by purchasing processing servers with various costs and capabilities. The objective is to minimize the cost of the platform while ensuring that the application achieves a minimum steady-state throughput. The first contribution of this paper is the formalization of a set of relevant operator-placement problems, and a proof that even simple versions of the problem are NP-complete. Our second contribution is the design of several polynomial time heuristics, which are evaluated via extensive simulations and compared to theoretical bounds for optimal solutions.

The goal of this work is to study the portfolio problem which consists in finding a good combination of multiple heuristics given a set of a problem instances to solve. We are interested in a parallel context where the resources are assumed to be discrete and homogeneous, and where it is not possible to allocate a given resource (processor) to more than one heuristic. The objective is to minimize the average completion time over the whole set of instances. We extend in this paper some existing analysis on the problem. More precisely, we provide a new complexity result for the restricted version of the problem, then, we generalize previous approximation schemes. In particular, they are improved using a guess approximation technique. Experimental results are also provided using a benchmark of instances on SAT solvers.

In this paper, we address the problem of k-out-of-ℓ exclusion, a generalization of the mutual exclusion problem, in which there are ℓ units of a shared resource, and any process can request up to k units (1 ≤ k ≤ ℓ). A protocol is self-stabilizing if, starting from an arbitrary configuration, be it initial state or after a corrupted state, the protocol can start behaving normally within a finite time. We propose the first deterministic self-stabilizing distributed k-out-of-ℓ exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process.

We consider the uniform scattering problem for a set of autonomous mobile robots deployed in a grid network: starting from an arbitrary placement in the grid, using purely localized computations, the robots must move so to reach in finite time a state of static equilibrium in which they cover uniformly the grid. The theoretical quest is on determining the minimal capabilities needed by the robots to solve the problem. We prove that uniform scattering is indeed possible even for very weak robots. The proof is constructive. We present a provably correct protocol for uniform self-deployment in a grid. The protocol is fully localized, collision-free, and it makes minimal assumptions; in particular: (1) it does not require any direct or explicit communication between robots; (2) it makes no assumption on robots synchronization or timing, hence the robots can be fully asynchronous in all their actions; (3) it requires only a limited visibility range; (4) it uses at each robot only a constant size memory, hence computationally the robots can be simple Finite-State Machines; (5) it does not need a global localization system but only orientation in the grid (e.g., a compass); (6) it does not require identifiers, hence the robots can be anonymous and totally identical.

Let g, h : {a, b}* → {a, b}* be marked morphisms of words. A pair (g1, h1) of marked morphisms {a, b}* → {a, b}* is called a successor of (g, h) if g ◦ g₁(a) = h ◦ h₁(a) and g ◦ g₁(b) = h ◦ h₁(b) and the images of g₁ and h₁ are shortest possible. Successors play an important role in studying the Post Correspondence Problem. Typically, they are simpler than the original morphisms, measured by the number of suffixes of their images (called the suffix complexity). In some cases, however, the suffix complexity is stable – it does not decrease. In this paper we give a full characterization of binary morphisms with stable suffix complexity.

Adaptation is a desirable requirement in a distributed system as it helps the system to perform efficiently under different environments. For many problems, more than one protocol exists, such that one protocol performs better in one environment while the other performs better in another. In such cases, adaptive distributed systems can be designed by dynamically switching between the protocols as the environment changes. In this work we propose an adaptive distributed mutual exclusion scheme that dynamically switches between two token based distributed mutual exclusion protocols; the Raymond's algorithm [15] and the Martin's algorithm [13]. Algorithms are proposed for switching in both directions and their correctness are proved. For each switching algorithm, it is shown that no more than one node can access the shared resource during the switching and no deadlock happens during the switching.

For securing confidential applications such as credit card transactions, on-line auctions and business contract signing, etc., a convertible authenticated encryption (CAE) scheme simultaneously satisfying the properties of authenticity, confidentiality and non-repudiation is a better choice. By combining the advantages of identity-based systems and key-insulated ones, in this paper, we propose the first novel identity-based key-insulated CAE (IB-KICAE) scheme from pairings. Integrating with key-insulated systems, our scheme can effectively mitigate the impact caused by key exposure, as each user can periodically update his private key while the corresponding public one remains unchanged. The proposed scheme is conversion-free and supports unbounded time periods and random-access key-updates. Moreover, to guarantee its practical feasibility, the essential security requirement of confidentiality against indistinguishability under adaptive chosen-ciphertext attacks (IND-CCA2) and that of unforgeability against existential forgery under adaptive chosen-message attacks (EF-CMA) are realized in the random oracle model.