I am no academic, but I read a lot of papers and going to write one this year. I skimmed the paper without getting into details about the protocol itself, but made some observations about the paper in general.
My personal very subjective opinion on how the paper might be reinforced is presented below.
1. Add a system model description under which your protocol is expected to operate.
2. Add description of fault-tolerant properties of the protocol.
3. Do you plan to prove correctness of the algorithm more formally?
Maybe you could model the algorithm before publishing. If you prove a safety property using model checking it could considerably reduce doubt about an algorithm correctness.
As for #3, unfortunately we don't currently have plans to publish a formal proof (we're building a product). Some of our internal documentation is more formal, but we decided on a more readable presentation for this paper.
You will probably find it valuable to write that proof. Sometimes an edge case pops up or you end up proving that it doesn't work as expected. I've done this a few times in my work.
Unless you already have it but don't plan to publish, which seems a little odd to me. I get that you want readable documentation, but at least you could link to it somewhere for people who go digging.
Well personally I would rather suggest to write a model, not a rigorous proof. A formal proof of any real protocol is both long and tedious journey; production guys will hardly find it useful thing to do.
On the other hand a logical model can be encoded in a rather short amount of time by someone who is doing it periodically.
This hypothetical guy could benefit from this activity by co-authoring the paper. Original authors would benefit from it by reinforcing both the protocol and the paper.
1. Add a system model description under which your protocol is expected to operate.
2. Add description of fault-tolerant properties of the protocol.
3. Do you plan to prove correctness of the algorithm more formally? Maybe you could model the algorithm before publishing. If you prove a safety property using model checking it could considerably reduce doubt about an algorithm correctness.