Hi all,
I have mostly finished writing a specification for a proposed distributed
pseudo-DFS scan. It can be found here:
https://bitbucket.org/shlomif/fc-solve/src/03d4e199635fb9176f5d79486797917686d17b0d/fc-solve/docs/distributed-pseudo-dfs-solver-spec.txt?at=master
(short URL -
http://is.gd/NipyLD )
This is going to be the next attempt at trying to determine whether MS deal
No. 384,243 is solvable using only two Freecells or not.
Comments are welcome.
Regards,
Shlomi Fish
===============================================================
Distributed Pseudo-DFS Solver SPEC:
===================================
Description:
------------
The pseduo-DFS solver will traverse a board using a stack of states and their
derived states (while making sure derived states do not repeat after first
encountered.). The primary item of communication will be a
Coordinates-Sequence (CoordSeq) that is:
struct CoordSeq
{
int64_t depth;
int32_t coords[0 .. depth-1];
}
This is generated when traversing the board using a predefined preset (say
"-to 01ABCDE -sp r:tf") using pseudo-DFS with the assumption that the states
collection/lookup only holds the states that were discovered earlier in the
stack. (There's also a local (per-client) cache of previous dead-end states,
but they still do not prevent these states from appearing in the DFS-stack,
just immediately marked as a dead end.).
The Server:
-----------
There will be one single server, which will be the first process to run,
and the clients (which will be based on libfreecell-solver.so) will all
connect for it and ask it for more to do, and more to delegate to clients
which are currently looking for something to help them with.
After setting up, the server accepts the connection from teh first client
to which it assigns the empty CoordSeq { depth == 0 }, then before
$CYCLE_LEN iterations, more clients ask to help other clients and the server
keeps their connection open. Then, the server asks the master client to
provide coordseqs to allocate for other clients, and they are allocated.
Occassionally, other clients will also ask for help and the server will help
them with.
Each client also reports on the currently reached CoordSeq and the server
keeps tracks (and logs) the initial CoordSeq allocated to each client and
its currently-reached CoordSeq.
The client allocates a CoordSeq by looking at the next states that need
to be traversed somewhere up the CoordSeq stack (a delta of
$DEPTH_ALLOC_DELTA from CoordSeq.depth or less), allocating the last (in the
following-chain of the current depth) non-allocated state as delegated,
marking it as delegated and delegating it.
Messages:
=========
This is a list of messages from server->client or from client->server. Every
message has a message ID (which can be implemented as a string or as a
fixed-size integer) and possibly some parameters.
---
END_CONN [client->server or server->client]
No parameters.
The end of the connection.
---
CLIENT_INIT [client->server]
No parameters.
A client connects to the server and requests the initialisation.
---
GIVE_ID_TO_CLIENT [server->client]
Parameters: id [64-bit int].
The server gives an ID to the client.
---
GIVE_SCAN_TO_CLIENT [server->client]
Parameters: 1. Scan [string_len+string (NUL/'\0' Terminated)]
2. Board [string_len+string (NUL/'\0' Terminated)]
The client MUST remember these.
---
I_AM [client->server]
1. ID.
2. Current CoordSeq or an empty one.
The client identifies itself. This MUST be the first message that a client
sends after he got its ID.
---
SOLVED [client->server]
Parameters: 1. CoordSeq
Indicating that the board was solved, and all other clients can be instructed
to quit.
---
NEEDHELP [client->server]
Parameters: [None]
Indicating the client's scan took longer than $CYCLE_LEN and it could use
some help. The server will respond with PLEASE_PROVIDE_COORD_SEQS if it has
more than one element.
---
PLEASE_PROVIDE_COORD_SEQS [server->client]
Parameters: 1. Count num to help [int64].
The server asks the client to provide CoordSeqs To help with. The client will
respond with PROVIDING_COORD_SEQS.
---
PROVIDING_COORD_SEQS [client->server]
Parameters: CoordSeqs coord_seqs[0 .. ]
Ending with a CoordSeqs whose depth is < 0.
A client provides coord seqs to help with to the server.
---
WANT_TO_HELP [client->server]
No parameters.
The client asks the server to help. The server will respond with
PLEASE_WORK_ON .
---
PLEASE_WORK_ON [server->client]
Parameters: 1. CoordsSeq.
Instructing a client that first said WANT_TO_HELP with what to work on.
---
SET_CYCLE_LEN [server->client]
Parameters: 1. int64 for cycle len.
Sets $CYCLE_LEN .
---
SET_DEPTH_ALLOC_DELTA [server->client]
Parameters: 1. int32 for depth_alloc_delta.
Sets $DEPTH_ALLOC_DELTA.
---
QUIT [server->client]
No parameters.
A server tells a client that there's nothing more to do and that it should
quit.
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Free (Creative Commons) Music Downloads, Reviews and more - http://jamendo.com/
<Su-Shee> Botje: “you can’t kill Botje” isn’t Newton’s first law.
<Su-Shee> It’s not even the 5th.
— http://www.shlomifish.org/humour/fortunes/sharp-perl.html
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Sat Dec 28 2013 - 09:57:34 IST