Stage is an implementation of actors in Ruby, influenced by the Erlang programming language's support for concurrency. To illustrate how to use Stage I have implemented a simple concurrent algorithm inspired by Andrew Cooke's parallel Sudoku solver written in Erlang. (Note that a more efficient approach to solving Sudoku puzzles has been demonstrated by Peter Norvig](http://norvig.com/sudoku.html).
In this implementation each of the 81 cells are represented by actors (instances of class SudokuCell) and one additional actor starts and supervises each of the cell actors (an instance of SudokuSolver). Cell actors keep track of their current value, and a number representing a level of confidence in that value. Cell actors with values that are provided as part of the initial puzzle have a special confidence level of "certain". Cell actors that do not have a value provided initially choose a random value and a confidence level of 0. During searching (described below), each time a cell actor changes its value it again resets its confidence level to 0.
Each cell actor is connected with all of the cells in the same column, row and 3x3 box. We refer to these connected cells as a cell's neighbours. To solve the puzzle, the cell actors communicate with their neighbours about their values using one of three kinds of messages: assert messages, cede messages and deny messages. Each of these messages is an array and the first element in the array is a symbol (similar to an enumerated type) which identifies the type of message:
Assert messsages are of the form [:assert, confidence, sender, value] where sender is the cell actor sending the message, value is that actor's current value (a number in the range 1 through 9), and confidence is that actor's current confidence level.
Cede messages are of the form [:cede, value] and are used to communicate agreement with an asserted value.
Deny messages are of the form [:deny, value] and are used to communicate disagreement with an asserted value.
Two additional kinds of messages are used for communicate between cells and the supervisor. A change message is sent from a cell actor to the supervisor to indicate that actor's value has been changed. A done message is sent from the supervisor to the cell actors to indicate that puzzle has been solved.
Based on those message types, the cell actors carry out the following simple algorithm. When a cell actor is certain about its value (most often this will be because its value was specified as part of the initial state of the puzzle) it will immediately broadcast an assert message to all of its neighbours. As this assert message will carry a confidence level of "certain", each of those neighbours will prune that asserted value from the values that they consider while searching for a solution.
Cell actors that are not certain about their value continually negotiate with their neighbours by periodically selecting a neighbour at random and sending that neighbour an assert message with the sending actor's current value and confidence level. A received assert message is considered a conflicting message if the asserted value is the same as the current value of the receiving actor. The negotiation protocol is summarized below.
When a cell actor receives a conflicting assert message from a neighbour and that neighbour is more confident than the receiving actor, the receiver changes its value and sends a cede message to the neighbour that sent the assert message.
On the other hand, if the receiver is more confident than sender, the receiver does not change values however it does slightly reduce its confidence level and it sends a deny message to the neighbour that sent the assert message.
When a cell actor receives an assert message that is not conflicting, it slightly increases its own confidence and replies with a cede message.
When a cell actor receives a cede message, assuming its current value is the same as the value sent with the cede message, it slightly increases its own confidence.
When a cell actor receives a deny messaage, assuming its current value is the same as the value sent with the deny message, it changes its value to a random alternative and resets its confidence to 0.
While following the above negotiation protocol, each time that a cell actor changes its value it sends a change message to the supervisor actor as described above. If there is a period of time in which the supervisor actor receives no change messages, it will assume that the cell actors have converged on a solution and will therefore stop the searchers (by broadcasting a "done" message) and print the solution.
Cell actors keep track of their current value and a number representing a level of confidence in that value. While executing, a cell actor can either be certain or searching. I use two different methods to capture this state. The first of these methods, is shown below. It fist sends an assert message to all of its neighbours and then waits for a done message to arrive, ignoring all other messages while waiting (see the other case in the code below).
def certain
broadcast(assert_message(), @neighbours)
while receive {|alt, msg|
alt.call(:done) {
false }
alt.other { true }
}
end
end
The search method is used to handle messages when a cell actor is uncertain about its value. This is essentially an implementation of the negotiation protocol described above in including the sending an assert message each time the timeout expires (see the after clause at the end of the message).
def search
while :done != receive(timeout) {|alt, msg|
alt.call(:done) {
:done }
alt.call(:assert, :certain, :_) {|t, conf, from, value|
prune_domain(value)
new_value() if value == @value }
alt.call(:assert, :_) {|t, conf, from, value|
self.when(certain?() && value == @value)
deny(from, value) }
alt.call(:assert, :_) {|t, conf, from, value|
self.when(value == @value && @confidence < conf)
new_value()
cede(from, value) }
alt.call(:assert, :_) {|t, conf, from, value|
self.when(value == @value)
doubt()
deny(from, value) }
alt.call(:assert, :_) {|t, conf, from, value|
confirm()
cede(from, value) }
alt.call(:deny, Integer) {|t, value|
new_value() if @value == value }
alt.call(:cede, Integer) {|t, value|
confirm() if @value == value }
alt.after {
assert() }
}
end
end
SudokuCell methods not listed in this paper include: assert, cede and deny which simply send messages to neighbouring cell actors, confirm and doubt which adjust an actor's confidence up and down respectively, prune_value which removes a value from an actor's domain and new_value which changes the actor's value and resets its confidence to 0. (Full code available from the Stage home page.)
An instance of the SudokuSolver class is used to supervise the cell actors. Each time a cell changes its value it sends a message to the supervisor (using the notify_linked_actors method). If the supervisor does not receive a message for a period of time (5 seconds in the code below), it assumes that the cells have converged on a solution and it stops each of the cells (by sending them the message :done) and prints the solution.
def run
while receive(5000) {|alt, message|
alt.call(:error, :_) {
# handle error ...
}
alt.call(:changed, :_) {
true
}
alt.after { false }
}
end
broadcast(:done, @cells)
print_solution()
end