Submitted: 7 May 2021
Reject: 27 September 2021
Thank you for submitting to TDSC. While the topic addressed in this paper has been found interesting by the reviewers, there are serious concerns with respect to the proposal (see Reviewer 1 comments) and its novelty/contributions when compared to [5] (see Reviewer 2 comments).
Revise and resubmit as “new”
This paper tackles an interesting problem and even motivates it with mostly interesting (the microloans example did not seem so useful) use cases that are, as far as I could understand, proposed by the authors. However I have several problems with the current manuscript, which despite the good motivation and the mostly good writing make me believe that the document cannot be accepted.
The first problem that I have is that the title, abstract, introduction, and related work are highly misleading. The system is called WebLedger, all of the sections mentioned above discuss block chain technology at length, however the proposed system, as far as I can understand, not only is not based on block chain technology but it does not really have a ledger. If the system has no ledger, is not based on keeping any form of chain of proofs that justify the full evolution of the system, and that allows every participant to check the correctness of the state considering the whole (and detailed) story of the system, then why call it WebLedger? Why the emphasis on block chain solutions? The system, as far as I can understand, is based on Byzantine fault-tolerant consensus that is used to replicate state, not using a strict state machine approach but instead using some conflict resolution mechanisms (in this case the authors use CRDTs and Merkle trees) when replicas have their state diverge due to the fact that not all replicas learn every decided operation (but the state encodes all executed operations). Why not call it WebBFT? Why not discuss the limitations of Byzantine fault tolerance, byzantine tolerant consensus, byzantine tolerant state machine replication in the Introduction, why not give emphasis to those solutions in the related work (and also on decentralized systems and web-based frameworks which are already covered in the current manuscript). This on itself, would be grounds for me to state that I do not believe that the paper should be accepted as is, however, there are a set of outstanding technical questions and flaws that reinforce my opinion.
As I stated before, at the core of the system proposed by the authors, there is a leaderless BFT consensus protocol that has some interesting properties, namely it allows operations to be committed one at a time without requiring all replicas to know this and then it uses a gossip style mechanism to allow replicas to converge to the same state (although the barrier between the role of the consensus protocol and the whole system towards this goal is fuzz sometimes). My main issue with this new protocol is that it is never presented in light of other BFT consesnsus protocols. Looking at the description presented by the authors, there are lots of similarities, the protocol strives to gather two supermajorities (which is not defined in the text as should be), signatures are involved to allow nodes to confirm that a majority is indeed achieved, and to identify byzantine replicas (although what is exactly being signed is never precisely disclosed in the paper). This is all well, but it should be presented in light of the significant body of academic work in this topic, not in isolation.
Another issue that I have is that the authors state that the protocol is leaderless, this would imply that multiple participants can propose operations to be executed over the current state of the system. Since a supermajority is required to commit such an operation, I believe that a supermajority can also transition to a new state, and that implies that nodes outside of that majority (which are still in the previous state) can submit operations to that previous state, but those will be rejected. This for me would be what I can infer from the description of the protocol presented by the authors. However if my interpretation is correct than the Termination property stated by the authors (and proved) is trivially incorrect. This might be a misunderstanding on my part related with the use of Version in the property whereas I am thinking about state, but there should be a one-to-one mapping.
Going back to the properties of the proposed consensus protocol, it would be great if they were written using terminology that is more widely used in this context (for instance as the one employed in the textbook by Verissimo, Rodrigues, and Cachin). Also, in general, the Termination property stated by the authors seems to be at odds with the well known FLP result, that states that consensus is impossible to achieve in an assychronous distributed system where a node can crash. Considering that the crash-fault model is more reestrictive than the byzantine-fault model, such a property seems to be an impossibility. This has to be made more clear and this aspect does have to be addressed. If you are circunventing the FLP result, you should explain how. As it is my confidence in this property is basically nil, and also I could not understand the proof for the property, in particular why after f+1 rounds all replicas have voted in round zero. There are several aspects that did not contribute for me to understand this proof:
The authors also state that the state is distributed among several keys (so I assume that you have atomic registers across several keys) but they never discuss the data model in detail? Why are keys necessary? Is it the case that each replica only proposes operations (new values) for the key that they own? If so, then this is equivalent to running multiple leader-based (maybe more precisely distinguished proposer) instances of the BFT consensus protocol in parallel, where each replica is the leader of its key. There seems to be some details left out that might be important to fully understand the paper.
These point have to be clarified and addressed to make the manuscript acceptable.
Nitpicks:
Please rate the manuscript. Explain your choice: Poor
Reject
My main issue with this paper is that it is not clear what are the contribution from this manuscript over the already published paper (ref 5). This manuscript could also be more clear that this is the extension of a paper already published.
Editorial comments:
The mixing of code (for x in y do) and mathematical language (∀ v ∈ c)
in the pseudo code makes it hard to follow (especially when they are
redundant: “for ∀ round”).
Please rate the manuscript. Explain your choice: Fair