To be written.
compression is finished in each node. Message tags are shown in boldface, and the integers in parenthesis with query messages are the message contents - 1(0) if the local image is compressed to a single pixel of white(black) color and 2 if the local image contains more than a single pixel and hence cannot be compressed with other portion of the image. At each iteration, compression is attempted at a given level of the bintree. Messages are exchanged between the siblings, with the processor with the higher identifier sending a message tagged as query containing its local image description to the processor owning the other sibling. If the two sub-images can be merged, the recipient sends a reply tagged as succ, or it sends a reply tagged as fail. At the start of the communication phase, all processors are Active. Processors receiving succ messages changes their state to Disable, whereas those receiving fail messages change their states to Waiting. At the end of the communication phase, all processors except those in Disable states write their local image content to the disk. The dotted lines show the implicit edges that are present between different nodes of the distributed bintree.
Although the pattern of communication is static (the
distance over which communication takes place depends only on the
iteration count), specifying it exactly is not trivial.
The two kinds of exchanges can be modeled separately by using the
regular expression based chain level description, and the fact that
messages carry a user-defined tag. The exchange, where components
of sub-images are not compressed further can be modeled at the chain
level as