[erlang-questions] write the ant simulation in Erlang?

David Mercer <>
Sat Oct 11 06:12:05 CEST 2008


Actually, I'd just have two states: ant and antless.  Your pending state
could result in deadlocks.

David

On Fri, Oct 10, 2008 at 5:37 PM, Rick R <> wrote:

> You're right. I didn't think it through at all.
> Better than decreasing the amount of messages, it avoids having to transact
> (or resolve conflicts) at all.
> The cell can have three states, empty, full, or pending. Pending would be
> that it is waiting for a response from an adjacent cell on whether it's ant
> can move there. It would simply delay any of its own responses until
> receiving a response from it's suitor.
>
> One could argue for a fourth state which is empty-but-expecting.  But if an
> ant is guaranteed to travel to your location once you've agreed to let it,
> then this state is as good as full.
>
> Not treating the ant as its own actor does take the fun (and the expense)
> out it.
>
> On Fri, Oct 10, 2008 at 5:43 PM, David Mercer <> wrote:
>
>>  Actually Danny G's approach has merit.  Ant on square A wants to move to
>> square B.  The messages passed are quite simple:
>>
>>
>>
>>    1. A: B ! {A, 'I have an ant who wants to move to you'}
>>    2. B: Either:
>>       1. A ! 'Your ant moved here successfully'
>>       2. A ! 'No can do, mate; I'm already occupied'
>>
>>
>>
>> In the case of 2a, square A marks itself vacant and can now respond with
>> its own 'Your ant moved here successfully' message when another square
>> requests passage for its ant.  In case of 2b, square A tries another square.
>>
>>
>>
>> DBM
>>
>>
>>
>>
>>
>>
>>   ------------------------------
>>
>> *From:*  [mailto:
>> ] *On Behalf Of *Rick R
>> *Sent:* Friday, October 10, 2008 15:39
>> *To:* Erlang-Questions (E-mail)
>> *Subject:* Re: [erlang-questions] write the ant simulation in Erlang?
>>
>>
>>
>>
>>
>> 2008/10/10 Daniel Goertzen <>
>>
>> How about 1 process for each cell, but no processes for the ants.  The
>> ants exist as state inside each cell and as messages interrogating
>> neighboring cells.  I think you'll get nice fine-grained localized
>> transactions this way.
>>
>> Dan.
>>
>>
>> Using that method, I think you'll still have the same issue with
>> transactions. For instance: if two cells decide to move their ant to the
>> same adjacent cell, you will have the same conflict and one ant will have to
>> be rolled back.
>> It may not even be more efficient message-wise because instead of the ant
>> sending a message to an adjacent cell, the cell simply sends the same
>> message to the adjacent cell on behalf of the ant.
>>
>> Of course we could go existentialist and say that there is no board except
>> what the ants perceive, and since they can only see one square in any
>> direction, that would imply that there is 1 process for each ant and no
>> process for a board (or any data for that matter).  This would mean that if
>> there are no ants on a section of board it would cease to exist. The only
>> way to reconstitute it would be to mathematically prove that it exists. e.g.
>> The ant was at 5,5 and moved 3 east,  8 < 64, therefore, the board exists.
>>
>> One could extend this method with a Paxos algorithm so that the ants could
>> achieve consensus as to the existence of Board.
>>
>>
>
>
> --
> "Have more than thou showest,
> Speak less than thou knowest,
> Lend less than thou owest,
> Ride more than thou goest."
>  -- The Fool to King Lear
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20081010/2ae33eed/attachment.html>


More information about the erlang-questions mailing list