Venue: JSYS 2022 Oct_Papers

Reviews:

final_score: rating: Weak accept: good paper with flaws that can be fixed in three months
review_content: 
### Overview (Problem, Contributions, and Proposed Solutions)
This paper studies the cluster-sending problem defined from Hellings et al. [17, 19].
There are two clusters of replicas C1 and C2, and the goal is to have C1 send (and confirm) a value v to C2.
The communication model assumes that 
* Local communication within a cluster is free.
* Global communication between different clusters is expensive.
* (Section 3, 4, 5): Synchronous and reliable communication.
* (Section 6): Asynchronous communication and unreliable protocols are discussed (but no proofs).
The model is supported by real world settings [7, 15].
Replicas may behave Byzantine, but a set of faulty replicas are oblivious (the set f(C1) and f(C2) are pre-determined prior to the beginning of the protocol.)

The problem is defined by the following properties:
* [should be Def 2.1, part (3)] Agreement-Send(C1): all non-faulty replicas in C1 agrees to send v. 
* [should be Def 2.1, part (1)] Agreement-Receive(C2): all non-faulty replicas in C2 receive v. (I believe “receive” here is a state where each replica reaches.)
* [should be Def 2.1, part (2)] Agreement-Confirm(C1): all non-faulty replicas in C1 confirm v. (“confirm” here seems to be another halting state.)
* Validity&Integrity (C2): if a non-faulty replica in C2 receives v, then v must be sent from some replica in C1.
* Validity&Integrity (C1): a non-faulty replica in C1 confirms v iff a non-faulty replica in C2 receives v.


The main contribution of this paper are:
1. Give a protocol with an expected constant inter-cluster messages.
2. Give a protocol with an expected constant and worst-case linear inter-cluster messages.
3. Brings attention to the cluster sending problem when local and global communication have huge differences in costs.

The main idea to solve the problem is to use Local consensus protocols within each cluster C1 and C2, and a two-phase commit between clusters if we view each cluster as a single process.
To my point of view, the most challenging part is to reach consensus for every cluster sending step.

This paper proposed an intuitive solution to this: 
Randomly select one pair of replicas (R1, R2) that represents C1 and C2. Then instruct these two replicas to communicate globally via CS-Step protocol.
Once the inter-cluster message is received, all replicas within the receiver’s cluster must reach consensus again about this message. This step is important because if any of R1 and R2 is faulty, this local consensus step will prevent the protocol to halt.

So, this process can be viewed as Bernoulli trials, and the successful probability of choosing good representative is simply (⅔)^2 = 4/9 (when nC1 > 3fC1) and (½)^2 = ¼ (when nC1 > 2fC1).
Hence, the expected messages to send is 9/4 (and 4) as desired. Notice that we already assume that the success probability for a local consensus is 1.

In worst-case linear protocol CSpl, the authors proposed to randomly permute all nodes within a cluster, and use that order to establish the “Bernoulli trials”. The analysis is more intricate than expected (could be simplified further but it should be fine…). Both clusters must agree on the same random order, as the clusters should initially agree on the same random source via a distributed fault-tolerant random coin [3, 4].

### Some curious questions:
*  This paper does not mention the lower bound on the expected inter-cluster messages to this model. Why 4 and 9/4 is the best?
* Section 6 seems very vague in its descriptions. I know that the asynchronous setting and unreliable communication settings are not the main focus of this paper. But I am still curious about the inter-cluster message complexities in these settings.
* I wasn’t sure if Figure 8 is the best way to present the second experiment of message loss. It confirms about the expected values in various settings but there seems to be no discussions/ new insights from the number readings. Furthermore, Figure 8 occupies an entire page.
* There were some reviews concerning the scalability of CSp into multiple clusters. I wonder if these multi-cluster-sending problems can be briefly discussed or conjectured.

I believe this work naturally extends to adaptive full-information adversaries that corrupt replicas along the execution of the protocol. It would be great if the authors can discuss about this somewhere in the paper (e.g., section 5.3 and section 6.) However, this adaptivity may lead to a worst-case & expected linear number of intercluster-messages.

### Writing Suggestions:
* Figure 1 is ALMOST IDENTICAL to [19] (except for a “hyphen” in “Cluster-Sending”). Please cite the paper if you are reproducing the image that has already been published.
* Please avoid integer-fraction representation. Please use $9/4$ instead of 2¼. This occurs in Figure 2, Corollary 4.4
* Definition 2.1 (1), each non-faulty replica “in $R$ $\in$ $\textsf{nf}(\mathcal{C}_2)$” seems duplicated.
* Theorem 4.2 and its proof: the denominator nfC1 seems incorrect (typo?). The same typo also occurs in Corollary 4.5.
* The \textsc is still case sensitive. Some part of your CSp is written as Csp. This occurs in page 2 item 2 in the main contribution. 

review_title: A paper solved the synchronous cluster-sending problem against oblivious adversary in expected constant (and worst-case linear) inter-cluster messages.

final_score: rating: Strong accept: excellent paper that will help the community
review_content: The authors took careful consideration of the reviews provided for the previous version of the paper. The points in question in the paper were changed; otherwise, the authors explained why the change was not applied.

The paper quality is now improved, as well as the presentation. I can recommend the paper to be accepted.
review_title: Comment on the revised version of the paper

final_score: rating: Strong accept: excellent paper that will help the community
review_content: I thank the authors for doing this interesting and valuable work with almost direct applications in practical systems for clustered systems. Their contribution to the Byzantine cluster-sending problem is the improvement of the message complexity of the operation. They improve on the previous linear number of message complexity in terms of the message size to the expected constant time. This is undoubtedly an improvement; however, it is essential to know that this is possible because synchrony is assumed. 

The author also provides experimental results of their implementations and demonstrates that their protocols perform substantially better than applying the consensus protocols. The first three reviewers have raised some interesting questions, and the author's responses are satisfactory. 

I have just one comment on this work. This problem has real-life applications; therefore, deriving some more realistic bounds on the message complexity would help the system designers who are concerned with latency. The estimation of message complexity under synchrony is too idealistic a scenario; therefore, the author can consider a performance analysis on the expected message complexity if they assume some upper bound on the max latency T for the message delivery, but the algorithm should not use this parameter or should not be aware of it.
They can also make some assumptions on the actual consensus protocol, failure model (crash or recovery), and upper and lower bound time on message delivery [T1, T2] to derive the result.
review_title: A simple and elegant approach to the cluster-sending problem

final_score: rating: Strong reject: this paper has serious problems, fixing it would definitely take more than three months
review_content: This paper studies a new problem called Byzantine cluster sending, which is supposed to play a key role in consensus sharding. The paper aims to give more efficient protocols for the cluster sending problem, first in the synchronous model, and eventually extending it to more realistic network models. 

Unfortunately, the problem statement (Definition 2.1) is very unclear, making it impossible for me to follow the paper. I hence could not comment on the meat of the paper at all. I'd like to first see the authors crystalize the problem they are trying to solve. I have the following questions on the problem statement. 
- Variable (set) R shows up in the definition undefined. 
- It is unclear what it means to decide "RECEIVE / CONFIRM / AGREE".  
- Requirement (i) says that non-faulty replicas in C2 decide RECEIVE, no matter what. Requirement (iii) then says non-faulty replicas in C2 decide DECEIVE only if non-faulty replicas in C1 decided AGREE. That immediately implies that non-faulty replicas must decide AGREE, no matter what. This immediately collapses the three requirements to a very simple requirement: no matter what happens, C2 decide on RECEIVE, and C1 decide on CONFIRM and AGREE. I am not confident this is what the authors had in mind. (If this is what you have in mind, why over-complicate it?)
- If the above is indeed what you mean, what is the difference between CONFIRM and AGREE? We can simply treat them to be the same action since they must always happen together. 

What is more confusing is that the beginning of Figure 3 gives another set of "pre" and "post" conditions that seem very different from Definition 2.1.
- It seems that replicas in C1 already agreed on some action called "sending". Then, we can simply equate "sending" with CONFIRM and AGREE. The problem is solved trivially. 
- Post (i) introduces R1 and R2, whose purposes are again unclear. R2 is not used at all in that paragraph. R1, without any constraint, seems synonymous to "every replica in C1". 
- Post (ii) states "then C1 agrees on sending", but C1 already agrees on sending according to the "pre" part, making this bullet vacuous. 
- Post (iii) is situated on a condition "If one replica in C1 decides CONFIRM". If we go by Definition 2.1, this is bound to happen, making the bullet vacuous. If we ignore what is said in Definition 2.1, then it is unclear under what conditions CONFIRM needs to happen, allowing trivial solutions that never decide CONFIRM. 
- It is also problematic that the properties in Figure 3 rely on communication being reliable". It is not a good idea to conflate the problem statement with the model. 

I tried to read the protocol in Figure 3 but also have trouble. 
- Why are R1 and R2 part of the input to the protocol? Definition 2.1 did not specify these inputs. 
- Instruct R1 to ... Who is instructing R1 to do things? 
- Is local consensus guaranteed to succeed on any value? Or are there constraints are what values can be agreed upon? If there is no constraint, then all replicas can simply agree on all possible values, leading to a trivial solution. 

In summary, I regret to say that I have trouble understanding the problem the paper is trying to solve. I hence cannot evaluate the paper in a meaningful way.  

review_title: Unclear problem definition prevents understanding the paper

Meta-review: metareview: Dear Authors, thank you for submitting to JSys. After reading the reviews, we recommend a REVISE decision. We believe the concerns of reviewers can be addressed in the next three months (potentially sooner, but we wanted to give you enough time to handle the comments). After the submission of your revised version, reviewers will evaluate your modifications and a final decision will be made.

Two reviewers appreciate the contributions and are happy with the revision from the previous submission. The other two reviewers pointed out major concerns in the writing and formalism. In particular, unclear definitions made it difficult for one reviewer to evaluate the paper with confidence. In general, most reviewers are optimistic for a future acceptance of the paper; hence, we believe all concerns can be addressed during the paper revision. Reviewers have included suggestions for improving the paper, please consider them

Isolating some major concerns:
- One of the reviewers mentioned serious concerns about the formalization in the paper. Consider addressing the comments in your revision. 
- Consider discarding the asynchronous section, to make the contribution and discussion more crystal clear and focused. As the way it’s presented currently, it is difficult to evaluate the claims. 
- Improve the evaluation, particularly the ones for Figure 8.

We look forward to receiving your revised version. Thank you one more time for submitting,

Lewis Tseng and Roberto Palmieri Area chairs of JSys

confidence: 5: The area chair is absolutely certain
Decision: Strong reject: this paper has serious problems, fixing it would definitely take more than three months