Re: [LAD] Strange Jack1 problem

On Mon, Aug 10, 2015 at 04:43:01PM -0400, Paul Davis wrote:
 
> it provides output indicating the logic decisions that lead to the
> execution order.

I spent most of the day trying to convinve myself that I was
overlooking something. But in the end the conclusion of all
that work is this:

* The algorithm used by Jack1 to determine the order of
* running clients in each cycle is fundamentally flawed.

The reason in mathematical terms is quite simple.

Both the relations 'A feeds B' and its transitive closure
'A feeds B, maybe indirectly' define only a *partial order*
on the set of clients. Now all classical sorting algorithms,
including the merge sort used in this case, assume a *total
order* of the set to be sorted, and may not produce the
correct result if only a partial order is defined.

It's easy to see this in a less abstract way. All classical
sorting algos are designed to reduce the number of compare()
calls. For example, if they find that a == b and a == c
they will in most cases avoid testing b against c, since
under total order it must be true that b == c.

Now if a '0' return from the compare() function does not
mean equality but rather 'not connected' things change.
Using the example above, you *can not* conclude that b
and c are not connected.

So all it takes is a few unconnected clients or two
or more independent chains to increase the probability
that a classical sort algorithm will fail to produce
a correct sequence.

I actually worked out the example I posted yesterday
with pencil and paper, including all the merge sorts.
This produced exactly the results posted. So there
is no bug in the current code, it is just the wrong
algorithm.

To find a linear sequence preserving the order of a
partially ordered set you need what is known as
'topological sorting'. It's usually implemente using
depth-first search (DFS) with post-order output.

Ciao,

-- 
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)
_______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev@email-addr-hidden
http://lists.linuxaudio.org/listinfo/linux-audio-dev