Re: How difficult is the firing squad synchronization problem?

From: Siamak (taati_at_dpir.com)
Date: 04/28/04

  • Next message: Richard Harter: "Re: How difficult is the firing squad synchronization problem?" 
    Date: 28 Apr 2004 02:45:22 -0700

    Ralph Hartley wrote:
    > > Is it trivial how to do something *arbitrarily*??
    >
    > Perhaps you are confusing "arbitrarily" with "randomly".

    Actually, it was unclear to me whether you've assumed the nodes
    distinguishing between their neighbors or not.

    > > By the way, wouldn't it be better if we allow just non-oriented
    > > signals? That is, if we assume i) each node can only send the same
    > > message to all its neighbors at once, and ii) each node only senses *a
    > > set* of messages coming from all its neighbors?
    >
    > Better? How can one problem be *better* than another? It might be
    > *different*.

    He he!:)) You are right in a sense, *but*:
    A problem can be more than just a puzzle. It would be a surprise, if
    we find out that a mass of simple elements with completely random
    interconnections can reach to a global synchrony. The more primitive
    are the elements or their interconnections, the higher is the
    surprise.

    > > In contrast, getting clues from your thoughts, I tend to imagine that
    > > finite state machines can do the job.;-)
    >
    > Show me how! Just a summary in words is fine for the newsgroop. Note that
    > computing the depth of the tree does *not* work because it is not bounded.

    I follow your assumption that the communications can be directed.
    Here is a too rough sketch: (it may or may not work)

    Suppose that the tree contains only a root (p) and two children (c1
    and c2), but the children cannot imediately give response to the
    commands: Let c1 has delay m and c2 has delay n. The protocol goes as
    follows:
    p sends a command 'A' to both c1 and c2. Each of c1 and c2 give a
    response 'a' after m and n steps, respectively. Once p receives 'a'
    from c1, it sends 'B' to c2 and vice versa. After m+n steps (or
    m+n+1), p and c1 and c2 can simultaniously enter a state 'F':

    Time: 1 m n (m+n)
    p ->c1 A...........B.......F
    c1-> p .......a...........bF
    p ->c2 A.......B...........F
    c2-> p ...........a.......bF

    Now let, in addition, p have also a delay, say k steps. The protocol
    is a bit more complicated:

                              (m+k) (n+k) (m+2k)(n+2k)
    Time: 1 m n | | | |
    p ->c1 A...........................B...........C
    c1-> p .........a...........................b...
    p ->c2 A.....................B............C.....
    c2-> p ...............a.....................b...
                                                 |
                                              (m+n+k)

         (m+2k)(n+2k) (m+n+2k)
    Time: | | |
    p ->c1 .....C........F
    c1-> p ..b...........F
    p ->c2 C.............F
    c2-> p ..b...........F
              |
           (m+n+k)

    Now, for an arbitrary binary tree, the protocol goes recursively:
    (here is the place I'm not sure about!)
    Let the left sub-tree simulate c1 and the right one simulate c2. Each
    subtree manages its own synchrony. If in a level a node has only one
    subtree, it can simply follow the linear firing squad protocol for the
    synchrony of its subtree.

    The problem is if we do it just with a simple recursion, we will need
    an (intermediate) firing state for each level of the tree, which is
    not bounded. However, it might be possible to mix the synchronization
    processes of a tree T and its subtrees T_l and T_r to reduce the
    number of states.

    I'll think about it, but now I have to go back to my work or my
    superviser will kill me later!!;-)

    What do you think?

    ***

    Here are some related problems:

    - Which proerties of a graph can be recognized by finite state
    machines at each node? (e.g., is there an FSM that fires F1 if the
    graph is Hamiltonian and fires F2 if it is not?)

    - Let the graph be infinite (still with bounded degrees). Is it
    possible to simulate a Turing Machine?

    - How about if the nodes have different "clocks"?

    Cheers,
    Siamak

  • Next message: Richard Harter: "Re: How difficult is the firing squad synchronization problem?"

    Relevant Pages

    • Re: How difficult is the firing squad synchronization problem?
      ... > Now, for an arbitrary binary tree, the protocol goes recursively: ... > subtree manages its own synchrony. ... it can simply follow the linear firing squad protocol for the ...
      (comp.theory)
    • Re: Copy-on-write tree data structure
      ... >>Let Node be a suitably defined data structure. ... this could be implemented by creating copies both of the tree ... >>strategy that makes copies of shared subtrees only when a shared subtree ... pointers to the unchanged sub-trees below it. ...
      (comp.lang.c)
    • Re: insert number in binary tree
      ... does anyone know how do we insert numbers in a binary tree? ... If this subtree is empty, ... promoting the right successor of the root will fix this: ...
      (comp.programming)
    • Re: insert number in binary tree
      ... we give you the binary tree that has 10 nodes as shown below.. ... Now, starting at root, count the number of nodes in the left subtree. ... doesn't matter; ...
      (comp.programming)
    • Re: Recursive function going infinite and I cant see why.
      ... def replace_within_node(node, oldnode, newnode): ... Because if your tree of nodes contains a loop, ... that node 1 has a subtree with node 2 that has a subtree with node 3 that ...
      (comp.lang.python)
    Loading