Message delay and DisCSP search algorithms

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been recently shown in experimental studies of asynchronous backtracking algorithms (Bejar et al., Artif. Intell., 161:117–148, 2005; Silaghi and Faltings, Artif. Intell., 161:25–54, 2005). To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the non-concurrent number of steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. Two families of distributed search algorithms on DisCSPs are investigated. Algorithms that run a single search process, and multiple search processes algorithms. The two families of algorithms are described and associated with existing algorithms. The performance of three representative algorithms of these two families is measured on randomly generated instances of DisCSPs with delayed messages. The delay of messages is found to have a strong negative effect on single search process algorithms, whether synchronous or asynchronous. Multi search process algorithms, on the other hand, are affected very lightly by message delay.     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

Asynchronous Forward-checking for DisCSPs

A new search algorithm for solving distributed constraint satisfaction problems (DisCSPs) is presented. Agents assign variables sequentially, but perform forward checking asynchronously. The asynchronous forward-checking algorithm (AFC) is a distributed search algorithm that keeps one consistent partial assignment at all times. Forward checking is performed by sending copies of the partial assignment to all unassigned agents concurrently. The algorithm is described in detail and its correctness proven. The sequential assignment method of AFC leads naturally to dynamic ordering of agents during search. Several ordering heuristics are presented. The three best heuristics are evaluated and shown to improve the performance of AFC with static order by a large factor. An experimental comparison of AFC to asynchronous backtracking (ABT) on randomly generated DisCSPs is also presented. AFC with ordering heuristics outperforms ABT by a large factor on the harder instances of random DisCSPs. These results hold for two measures of performance: number of non-concurrent constraints checks and number of messages sent. Research supported by the Lynn and William Frankel Center for Computer Sciences and the Paul Ivanier Center for Robotics and Production Management.     

Distributed constraint satisfaction with partially known constraints

Distributed constraint satisfaction problems (DisCSPs) are composed of agents connected by constraints. The standard model for DisCSP search algorithms uses messages containing assignments of agents. It assumes that constraints are checked by one of the two agents involved in a binary constraint, hence the constraint is fully known to both agents. This paper presents a new DisCSP model in which constraints are kept private and are only partially known to agents. In addition, value assignments can also be kept private to agents and not be circulated in messages. Two versions of a new asynchronous backtracking algorithm that work with partially known constraints (PKC) are presented. One is a two-phase asynchronous backtracking algorithm and the other uses only a single phase. Another new algorithm preserves the privacy of assignments by performing distributed forward-checking (DisFC). We propose to use entropy as quantitative measure for privacy. An extensive experimental evaluation demonstrates a trade-off between preserving privacy and the efficiency of search, among the different algorithms. Partially supported by the Spanish project TIN2006-15387-C03-01. Partially supported by the Lynn and William Frankel center for Computer Sciences and the Paul Ivanier Center for Robotics and Production Management.     

Algorithms for Distributed Constraint Satisfaction: A Review

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.     

New solutions for disjoint paths in P systems

We propose four fast synchronous distributed message-based algorithms, to identify maximum cardinality sets of edge- and node-disjoint paths, between a source node and a target node in a digraph. Previously, Dinneen et?al. presented two algorithms, based on the classical distributed depth-first search (DFS), which run in O(mf) steps, where m is the number of edges and f is the number of disjoint paths. Combining Cidon??s distributed DFS and our new result, Theorem 3, we propose two improved DFS-based algorithms, which run in O(nf) steps, where n is the number of nodes. We also present improved versions of our two breadth-first search (BFS) based algorithms, with the same complexity upperbound, O(nf). Empirically, for a large set of randomly generated digraphs, our DFS-based edge-disjoint algorithm is 39?% faster than Dinneen et?al.??s edge-disjoint algorithm and our BFS-based edge-disjoint algorithm is 80?% faster. All these improved algorithms have been inspired and guided by a P system modelling exercise, but are suitable for any distributed implementation.     

Dynamic Ordering for Asynchronous Backtracking on DisCSPs

An algorithm that performs asynchronous backtracking on distributed , with dynamic ordering of agents is proposed, . Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. Changes of ordering triggers a different computation of . The dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard . The algorithm with three different ordering heuristics is compared to standard on randomly generated . A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order by a large factor in run-time and improve the network load.     

Min-domain retroactive ordering for Asynchronous Backtracking

Ordering heuristics are a powerful tool in CSP search algorithms. Among the most successful ordering heuristics are heuristics which enforce a fail first strategy by using the Min-domain property (Haralick and Elliott, Artif Intel 14:263–313, 1980; Bessiere and Regin, Mac and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In Proc. CP 96, pp. 61–75, Cambridge, MA, 1996; Smith and Grant, Trying harder to fail first. In European Conference on Artificial Intelligence, pp. 249–253, 1998; Dechter, Constraint Processing. Morgan Kaufman, 2003). Ordering heuristics have been introduced recently to asynchronous backtracking (ABT), for distributed constraints satisfaction (DisCSP) (Zivan and Meisels, Dynamic ordering for asynchronous backtracking on discsps. In CP-2005, pp. 32–46, Sigtes (Barcelona), Spain, 2005). However, the pioneering study of dynamically ordered ABT, ABT_DO, has shown that a straightforward implementation of the Min-domain heuristic does not produce the expected improvement over a static ordering. The present paper proposes an asynchronous dynamic ordering which does not follow the standard restrictions on the position of reordered agents in ABT_DO. Agents can be moved to a position that is higher than that of the target of the backtrack. Combining the Nogood-triggered heuristic and the Min-domain property in this new class of heuristics results in the best performing version of ABT_DO. The new version of retroactively ordered ABT is faster by a large factor than the best form of ABT.     

A Distributed Algorithm for Computing the Node Search Number in Trees

We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis et al. (Inf. Comput. 113(1):50–79, 1994). It can be executed in an asynchronous environment, requires an overall computation time of O(nlog?n), and n messages of log?₃ n+4 bits each. The main contribution of this work lies in the data structure proposed to design our algorithm, called hierarchical decomposition. This simple and flexible data structure is used for four operations: updating the node search number after addition or deletion of any tree-edges in a distributed fashion; computing it in a tree whose edges are added sequentially and in any order; computing other graph invariants such as the process number and the edge search number, by changing only initialization rules; extending our algorithms for trees and forests of unknown size (using messages of up to 2log?₃ n+5 bits).     

Concurrent checkpoint initiation and recovery algorithms on asynchronous ring networks

Checkpointing with rollback recovery is a well-known method for achieving fault-tolerance in distributed systems. In this work, we introduce algorithms for checkpointing and rollback recovery on asynchronous unidirectional and bi-directional ring networks. The proposed checkpointing algorithms can handle multiple concurrent initiations by different processes. While taking checkpoints, processes do not have to take into consideration any application message dependency. The synchronization is achieved by passing control messages among the processes. Application messages are acknowledged. Each process maintains a list of unacknowledged messages. Here we use a logical checkpoint, which is a standard checkpoint (i.e., snapshot of the process) plus a list of messages that have been sent by this process but are unacknowledged at the time of taking the checkpoint. The worst case message complexity of the proposed checkpointing algorithm is O(kn) when k initiators initiate concurrently. The time complexity is O(n). For the recovery algorithm, time and message complexities are both O(n).     

A scalable,parallel algorithm for maximal clique enumeration

The problem of maximal clique enumeration (MCE) is to enumerate all of the maximal cliques in a graph. Once enumerated, maximal cliques are widely used to solve problems in areas such as 3-D protein structure alignment, genome mapping, gene expression analysis, and detection of social hierarchies. Even the most efficient serial MCE algorithms require large amounts of time to enumerate the maximal cliques in networks arising from these problems that contain hundreds, thousands, or larger numbers of vertices. The previous attempts to provide practical solutions to the MCE problem through parallel implementation have had limited success, largely due to a number of challenges inherent to the nature of the MCE combinatorial search space. On the one hand, MCE algorithms often create a backtracking search tree that has a highly irregular and hard-or-impossible to predict structure; therefore, almost any static decomposition of the search tree by parallel processors results in highly unbalanced processor execution times. On the other hand, the data-intensive nature of the MCE problem often makes naive dynamic load distribution strategies that require extensive data movement prohibitively expensive. As a result, good scaling of the overall execution time of parallel MCE algorithms has been reported for only up to a couple hundred processors. In this paper, we propose a parallel, scalable, and memory-efficient MCE algorithm for distributed and/or shared memory high performance computing architectures, whose runtime scales linearly for thousands of processors on real-world application graphs with hundreds and thousands of nodes. Its scalability and efficiency are attributed to the proposed: (a) representation of the search tree decomposition to enable parallelization; (b) parallel depth-first backtracking search to both constrain the search space and minimize memory requirement; (c) least stringent synchronization to minimize data movement; and (d) on-demand work stealing intelligently coupled with work stack splitting to minimize computing elements’ idle time. To the best of our knowledge, the proposed parallel MCE algorithm is the first to achieve a linear scaling runtime using up to 2048 processors on Cray XT machines for a number of real-world biological networks.     

Space efficient and time optimal distributed BFS tree construction

In this paper, we give a simple distributed algorithm for constructing a BFS spanning tree in an almost anonymous, asynchronous, rooted network. The proposed algorithm is an improved version of an algorithm by Aspnes. The time complexity of the algorithm is optimal for this problem, i.e., O(diam), where diam is the diameter of the network, and the space complexity of each process is O(δP) for each process P, where δP is the degree of P. The message complexity is O(diam⋅|E|), where E is the set of links, and the size of each message is O(1).     

An affine-scaling derivative-free trust-region method for solving nonlinear systems subject to linear inequality constraints

In this paper, an affine-scaling derivative-free trust-region method with interior backtracking line search technique is considered for solving nonlinear systems subject to linear inequality constraints. The proposed algorithm is designed to take advantage of the problem structured by building polynomial interpolation models for each function in the nonlinear system function F. The proposed approach is developed by forming a quadratic model with an appropriate quadratic function and scaling matrix: there is no need to handle the constraints explicitly. By using both trust-region strategy and interior backing line search technique, each iteration switches to backtracking step generated by the trust-region subproblem and satisfies strict interior point feasibility by line search backtracking technique. Under reasonable conditions, the global convergence and fast local convergence rate of the proposed algorithm are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithms.     

Distributed algorithm to detect strong conjunctive predicates

This paper presents an on-line distributed algorithm for detection of Definitely(φ) for the class of conjunctive global predicates. The only known algorithm for detection of Definitely(φ) uses a centralized approach. A method for decentralizing the algorithm was also given, but the work load is not fairly distributed and the method uses a hierarchical structure. The centralized approach has a time, space, and total message complexity of O(n²m), where n is the number of processes and m is the maximum number of messages sent by any process. The proposed on-line distributed algorithm uses the concept of intervals rather than events, and assumes p is the maximum number of intervals at any process. The worst-case time complexity across all the processes is O(min(pn²,mn²)). The worst-case space overhead across all the processes is min(2mn²,2pn²).     

An Adaptive Distributed Channel Allocation Strategy for Mobile Cellular Networks

A channel allocation algorithm includes a channel acquisition algorithm and a channel selection algorithm. Most of the previous work concentrates on the channel selection algorithm since early channel allocation algorithms simply use a centralized channel acquisition algorithm, which depends on a mobile switching center (MSC) to accomplish channel acquisition. Recently, distributed channel acquisition algorithms have received considerable attention due to their high reliability and scalability. There are two approaches to designing distributed channel acquisition algorithms: search and update. The update approach has shorter acquisition delay and lower call blocking rate, but higher message complexity. On the other hand, the search approach has lower message complexity, but longer acquisition delay and higher call blocking rate. In this paper, we propose a novel distributed channel acquisition algorithm, which is a significant improvement over both approaches. Also, we identify two guiding principles in designing channel selection algorithms and propose an algorithm which has low call blocking rate and low intrahandoff overhead. By integrating the channel selection algorithm into our channel acquisition algorithm, we get a complete distributed channel allocation algorithm. By keeping the borrowed channels, the channel allocation algorithm makes use of the temporal locality and adapts to the network traffic; i.e., free channels are transferred to hot cells to achieve load balance. Simulation results show that our channel allocation algorithm significantly outperforms the search approach and the update approach in terms of call blocking rate, message complexity, and acquisition delay.     

Computing the correlation dimension on a network of workstations

We present a parallel algorithm for computing the correlation dimension (D₂) from a time series generated by a dynamic system, using the method of correlation integrals, which essentially requires the computation of distances among a set of points in the state space. The parallelization is suitable for coarse-grained multiprocessor systems with distributed memory and is carried out using a virtually shared memory model. The algorithm simultaneously gives all the correlation integrals at various state space dimensions needed to estimate the D₂. Two versions are discussed: the first computes all distances between points; the second computes only distances less than a fixed ϵ, and employs a box-assisted approach and linked lists for an efficient search of neighbouring points. The algorithms, coded in Fortran 77, are tested on a heterogeneous network of workstations consisting of various DEC Alphas of different powers, interconnected by Ethernet; the Network Linda parallel environment is used. A detailed analysis of performance is carried out using the generalization of speed-up and efficiency for heterogeneous systems. The algorithms are fully asynchronous and so intrinsically balanced. In almost all the situations they provide a unitary efficiency. The second version greatly reduces the computational work, thus making it possible to tackle D₂ estimation even for medium and high-dimensional systems, where an extremely large number of points is involved. The algorithms can also be employed in other applicative contexts requiring the efficient computation of distances among a large set of points. The method proposed for the analysis of performance can be applied to similar problems. © 1998 John Wiley & Sons, Ltd.     

Generation of Random Digital Simple Curves with Artistic Emulation

This paper presents two novel interdependent techniques for random digital simple curve generation. The first one is about generating a curve of finite length, producing a sequence of points defining a digital path ρ ‘on the fly’. The second is for the creation of artistic sketches from line drawings and edge maps, using multiple instances of such random digital paths. A generated digital path ρ never intersects or touches itself, and hence becomes simple and irreducible. This is ensured by detecting every possible trap formed by the previously generated part of ρ, which, if entered into, cannot be exited without touching or intersecting ρ. The algorithm is completely free of any backtracking and its time complexity is linear in the length of ρ. For artistic emulation, a curve-constrained domain is defined by the Minkowski sum of the input drawing with a structuring element whose size varies with the pencil diameter. An artist’s usual trait of making irregular strokes and sub-strokes, with varying shades while sketching, is thus captured in a realistic manner. Algorithmic solutions of non-photorealism are perceived as an enrichment of contemporary digital art. Simulation results for the presented algorithms have been furnished to demonstrate their efficiency and elegance.     

Self-stabilizing leader election in optimal space under an arbitrary scheduler

A silent self-stabilizing asynchronous distributed algorithm, SSLE, is given for the leader election problem in a connected unoriented (bidirectional) network with unique IDs. SSLE also constructs a BFS tree on the network rooted at that leader. SSLE uses O(logn) space per process and stabilizes in O(n) rounds, against the unfair daemon, where n is the number of processes in the network.     

Precision Evaluation of Search Engines

In this paper, we present a general approach for statistically evaluating precision of search engines on the Web. Search engines are evaluated in two steps based on a large number of sample queries: (a) computing relevance scores of hits from each search engine, and (b) ranking the search engines based on statistical comparison of the relevance scores. In computing relevance scores of hits, we study four relevance scoring algorithms. Three of them are variations of algorithms widely used in the traditional information retrieval field. They are cover density ranking, Okapi similarity measurement, and vector space model algorithms. In addition, we develop a new three-level scoring algorithm to mimic commonly used manual approaches. In ranking the search engines in terms of precision, we apply a statistical metric called probability of win. In our experiments, six popular search engines, AltaVista, Fast, Google, Go, iWon, and NorthernLight, were evaluated based on queries from two domains of interest: parallel and distributed processing, and knowledge and data engineering. The first query set contains 1726 queries collected from the index terms of papers published in the IEEE Transactions on Knowledge and Data Engineering. The second set contains 1383 queries collected from the index terms of papers published in the IEEE Transactions on Parallel and Distributed Systems. Search engines were queried and compared in two different search modes: the default search mode and the exact phrase search mode. Our experimental results show that these six search engines performed differently under different search modes and scoring methods. Overall, Google was the best. NorthernLight was mostly second in the default search mode, whereas iWon was mostly second in the exact phrase search mode.