Distributed Stochastic Search for Constraint Satisfaction and Optimization: Parallelism, Phase Transitions and Performance

Contents

Many distributed problems can be captured as distributed constraint satisfaction problems (CSPs) and constraint optimization problems (COPs). In this research, we study an existing distributed search method, called distributed stochastic algorithm (DSA), and its variations for solving distributed CSPs and COPs. We analyze the relationship between the degree of parallel executions of distributed processes and DSAs’ performance, including solution quality and communication cost. Our experimental results show that DSAs’ performance exhibits phase-transition patterns. When the degree of parallel executions increases beyond some critical level, DSAs’ performance degrades abruptly and dramatically, changing from near optimal solutions to solutions even worse than random solutions. Our experimental results also show that DSAs are generally more effective and efficient than distributed breakout algorithm on many network structures, particularly on over-constrained structures, finding better solutions and having lower communication cost.