---
title: "Optimistic Parallel biscrete Relaxation"
authors:
  - "Kinson Ho"
  - "Paul N. Hilfinger"
  - "Hans W. Guesgen"
doi: ""
url: "https://ijcai.org/proceedings/1993/38"
pdf: "https://ijcai.org/proceedings/1993/0038.pdf"
venue: "Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence"
year: 1993
pages: "268-274"
track: "Constraint Satisfaction Problems"
keywords:
---

# Optimistic Parallel biscrete Relaxation

Kinson Ho, Paul N. Hilfinger, Hans W. Guesgen

*Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence*, pages 268-274.

## Abstract

Discrete relaxation is frequently used to compute the fixed point of a discrete system X= /(X), where f is monotonic with respect to some partial order $. Given an appropriate initial value for X, discrete relaxation repeats the assignment X - /(X) until a fixed point for f is found. Monotonicity of f with respect to $ is a sufficient (but in general not necessary) condition for iterative, hill-climbing techniques such as discrete relaxation to find the fixed point of f. In this paper we introduce monotonic asynchronous iteration as a novel way of implementing parallel discrete relaxation in problem domains for which monotonicity is a necessary condition. This is an optimistic technique that maintains monotonicity without limiting concurrency, resulting in good parallel performance. We illustrate this technique with the parallel implementation of a constraint satisfaction system that computes globally consistent solutions, and present performance numbers for experiments on a shared-memory implementation. The performance numbers show that it is indeed possible to obtain a reasonable speedup when parallelizing global constraint satisfaction. We believe that monotonic asynchronous iteration is applicable to parallel discrete relaxation in general.