2
$\begingroup$

Sorting algorithms have a huge literature behind them, and the algorithm I'm planning has some similarities to the topic, but I couldn't even find the correct search terms to know whether a field exists which studies such algorithms.

Imagine the following problem: there is a serial communication channel of a very low throughput, and you have to communicate with a number of devices through it. If all devices had the same priority, the solution would be obvious:

A B C D A B C D A B C D A ...

(In case of 4 devices, where "A" means "communicate with device A")

However, it can happen that some devices have a lower priority, and our goal is to improve the latency of high-priority devices, that is, the time between two consecutive communications with the same device should be small.

For example, we have devices A, B, C, and D with a high priority, and devices e, f, g and h, with a lower priority.

The naive solution would be to process the lower priority devices only every second turn, or every third turn, etc. Let's call this the "skipping factor".

Example: higher-case letters are twice as important:

A B e C D f A B g C D h A B e C D f A B g C D h ...   

Example: higher-case letters are three times as important:

A B C e D A B f C D A g B C D h A B C D e ...   

However, this solution quickly breaks down if the number of elements in the different priority categories differ greatly.

Take the example of "capital letters are twice as important", but with 8 capital letters and 2 lower case letters:

A B i C D j E F i G H j A B i ...

Here, the lower-case letters occur more often, even though that's opposite to our goal.

A solution would be to multiply the skipping factor by the ratio of the cardinalities of the priority groups. In the above example, the ratio is 8/2 = 4, we multiply it with the skipping factor of two, and we get 8, so after every 8 capital letter there can come a lower case one.

The problem

The above examples were by far not exhaustive. Even the latest solution in the above example breaks down easily if there are more than two priority groups, and especially if the priority of the elements can change over time. This last constraint can be a very difficult one, as even "smarter" algorithms where every element has its own "timeout" counter ticking down can be fooled by cases where an element changes priority back and forth so that it never gets executed. The complexity also grows because we have to crawl through the lists of elements of every priority level on each occasion we select a new element to be sent.

The question

I have many different ways in my mind to solve this problem, but I'm afraid of trying to re-invent the wheel, and arriving to a suboptimal solution. I'm therefore looking for a field of study which works with problems such as the one listed above. Does it have a name? Does it have a literature? I tried searching some terminology I guessed relevant for the topic, but I couldn't find anything.

$\endgroup$
3
$\begingroup$

By far the simplest solution is probabilistic. Let's suppose you have $k$ classes, and their relative importance is $c_1,\ldots,c_k$. Let's also suppose that there are $N_i$ objects in class $i$. You want the frequency of appearances of each symbol in class $i$ to be proportional to $c_i$.

Let $P = \sum_i c_i N_i$ and $p_i = c_i N_i/P$. At each step, choose class $i$ with probability $p_i$, and output a random element from the class. The probability that a specific element from class $i$ appears is $p_i/N_i = c_i/P \propto c_i$.

To increase fairness among class $i$, instead of outputting a random element, you can keep a counter for each class (counting modulo $N_i$), incremented any time the class is chosen, and output the corresponding element from the class.

A similar approach should work for fairness across classes, but here it's not as straightforward so I'll leave it to you.

$\endgroup$
2
  • $\begingroup$ This is very similar to one of the approaches I'm considering (it must be deterministic, so I have to use counters instead of random), and I appreciate your answer, but what I'm really looking for is whether this topic is large enough to have a name and a corresponding literature. Just as different sorting algorithms have different advantages and disadvantages (like worst-case complexity, average complexity, memory usage, etc.), there might be many ways to consider here (speed vs. memory usage vs. fairness of decision). $\endgroup$
    – vsz
    Sep 4 '17 at 11:31
  • $\begingroup$ Unfortunately I am not aware of any relevant topic. $\endgroup$ Sep 4 '17 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.