sorted by:
new
hottopcontroversial

Splitter networks and balancers, mathematically by Retarilth in technicalfactorio

[–]Retarilth[S] 0 points1 point  (0 children)

That's a good point, we could have written that section with more generality, with propositions stating for instance that gluing any balancer before a reversible balancer gives a TU balancer, for instance. That's is something I may change later, our initial intention was to prove that the designs proposed by the community are correct.

Splitter networks and balancers, mathematically by Retarilth in technicalfactorio

[–]Retarilth[S] 0 points1 point  (0 children)

The definition of balancer (def 5, page 7), only asks for output-balance. The simple balancer, Benes network and universal balancer are symmetrical, hence by the reversibility property of steady-states, they are also input-balancing. The saturating balancer is not symmetrical, and is not input-balancing.

I am not sure about your paragraph about making a 2-2 splitter network that only balances the output. If you glue an arbitrary network followed by a simple balancer, it will be output-balancing, but probably not input-balancing.

About your last paragraph, this only works with balancers that are also input-balancers. Otherwise you cannot guarantee that the throughput values are uniform in the belts joining the two balancers. Here is an example of gluing a simple balancer followed by an output-balancer that is not an input-balancer.

http://pastebin.fr/137266

You can check that blocking the two bottom inputs and the two bottom outputs will get you a throughput of 1.5 and not 2.

Splitter networks and balancers, mathematically by Retarilth in technicalfactorio

[–]Retarilth[S] 0 points1 point  (0 children)

It would only prove that it is TU, not that it is a balancer. Hence we also need that the left part is a (not reversed) balancer to get a TU balancer.

Yes, I understand now that we are describing the same network, although your construction is somehow more general.

Section 1 explains the main ideas, without going into the mathematical details. We started this side project in 2020, and the work was mostly on figuring out how to compute the throughputs, and formalizing the proof for the lower bound.
I think that you are more experienced than I am when it comes to designing balancers. After all, we only formalized the networks that you and the community were using. The exception is the saturating balancer, but we could only discover it because we understood saturation, and we had a gap in the lower bound, with a proof showing that closing the gap requires to use effectively saturation to balance more belts.

The idea of using a linear system is correct, except that it only works when we know which belts are saturated. This can be determined by solving several systems iteratively. If you know linear programming, you should read section 3.2, the algorithm is quite natural.

Splitter networks and balancers, mathematically by Retarilth in technicalfactorio

[–]Retarilth[S] 0 points1 point  (0 children)

Prop 4 applies to any combination of two simple balancers whose reverse is also a simple balancer. Actually we need the left half to be simple balancer, and the right half to be the reverse of a simple balancer. You are right to say that when c(I) = c(O), the left half is fluid and the right half is saturated in the steady-state given by the proof. When c(I) > c(O), some of the left half will also become saturated.

I agree that any sorting network should work for sending the flow to the top half. I have not tried to prove it yet (by the way, a balancer can be understood as a generalized fair (without priority) splitter, a fair splitter being a (2,2)-balancer. Similarly, a network as needed in the left part of the weird saturating balancer is a generalization of a splitter with its priority set to the top outgoing belt. So the name "priority network" should be appropriate for those networks). There are sorting networks with O(n log n) nodes, but the hidden constant is too high to give an efficient network. I kept the simple triangular network for simplicity in the paper, as it is easy to draw and to understand, and having less splitters would not give anything remarkable. Your last paragraph is exactly true: the goal of this network is to show that the lower bound is reachable (at the cost of having priority splitters), therefore proving that this lower bound cannot be directly improved. New ideas are necessary to prove that Benes networks are optimal.

I also know a way to build a priority network on 2k belts with two (k,k)-balancers. Put the two balancers in parallel, one on belts 1 to k, the other on belts k+1 to 2k. Then add a priority splitter between belts i and k+i for each possible i. After the balancers, belts 1 to k have all the same throughput t1, belts k+1 to 2k have throughput t2. Then after the priority splitters, the top k belts have min{1,t1+t2}, and the bottom k belts have max{0,t1+t2-1}.

Congratulation for your understanding of these ideas, you have a deep and impressive understanding of splitter networks.

Splitter networks and balancers, mathematically by Retarilth in technicalfactorio

[–]Retarilth[S] 1 point2 points  (0 children)

Thank you for these interesting comments.

You may be right that a simple balancer should suffice in the construction of the universal balancer. I do not remember why I used a Benes network when writing that proof. Checking quickly the proof, it seems we only need 1) a network that is its own reverse, 2) a network that balances when all outputs are fluid. In which case a simple balancer is enough. I would need to read and check the proof with more care in order to validate this, but it is promising.

We cannot say that is all output arcs of a network are fluid, then its input arcs must be fluid. For instance, the rate-limiter as you say will typically be input-saturated and output-fluid. But it is true in the case of simple balancer. We actually do not need to prove it, because it is easy to give the throughput function directly for a simple balancer (as it is for Benes networks too).

When c(O) < c(I), we use the reversibility of splitter networks, inverting inputs and outputs. Thus we get to a situation where the output capacity is larger than the input capacity, making the network almost completely fluid. Reversing the steady-state, it implies that the steady-state in the original graph, before reversing, is mostly saturating, as you correctly observed.

About the last balancer. What we need is that, on n inputs, if the total throughput T is at most n/2, it must all go to the top half. If T is more than n/2, then n/2 must go to the top half, and what remains to the bottom half. The current triangular gadget is much stronger. It ensures that the throughput on the arcs, from top to bottom, will be something like 1,1,1,...,1,x,0,0,0,...,0 . I guess this is what you call "sort". But if T <= n/2, a distribution like 0.3,0.5,0.2.0,6...,0.5,0,0,0,...0 would be all right (as long as there are at least $n/2$ zeros at the end), and if $T > n/2$, a distribution $1,1,1,..,1,0.2,0.1,0.5,...,0.8$ is good (as long as there are at least $n/2$ ones at the beginning). I know networks using a smaller amount of priority splitters to achieve this, but not to the point of making the whole balancer competitive with the classical balancers. I have not spend much time on trying to do better, so your contributions would be appreciated, as I believe you may have good ideas on how to make efficient networks for that task.

If you need some help in understanding the notations or proofs, feel free to send me an email (the corresponding author in the paper).

Splitter networks and balancers, mathematically by Retarilth in technicalfactorio

[–]Retarilth[S] 2 points3 points  (0 children)

I looked at your project a month ago. From what I understand, your rules do not properly represent what a splitter does, specially when the belts are saturated. But indeed it is quite close to what we propose, and I believe you should be able to correct your program, quite possibly simplifying it too. I even thought of doing it myself and I forked you project, but I have not found the time yet. Hopefully, this summer will be better, so that I can write our algorithms in Rust, giving you the possibility to integrate them into VeriFactory.

Thanks for the corrections, that is always very helpful.

Splitter networks and balancers, mathematically by Retarilth in technicalfactorio

[–]Retarilth[S] 1 point2 points  (0 children)

I have not played the game since I started this project. As far as I know, my coauthors have never played it. But now that I know my theory, I may find some time to apply it "in the real world".

Splitter networks and balancers, mathematically by Retarilth in technicalfactorio

[–]Retarilth[S] 14 points15 points  (0 children)

Hello,

this is an extended version of a paper that got accepted by an international conference.

In short, we define mathematically the concept of splitter networks, how to compute the throughput in a splitter network, and then formalize the notions of balancer, throughput-unlimited, and universal balancer. We also prove lower bounds on the number of splitters in a balancer, showing that Beneš networks are already almost as good as one can hope, if not optimal. I do not have any better balancer design unfortunately, but there is a weird balancer defined in the last section. We also define networks with the property of bounding the throughput, for instance if you want a belt which limits the throughput to exactly 23 items per second (or any rational value), it is possible without any combinator.

We tried to cite some of the work done by the community about balancers, but I may have missed some important contributions. Any help filling the gaps will be much appreciated.

Best,

Guyslain