1
$\begingroup$

The main question is the following:
When designing a system supporting atomic broadcast, can it be proved theoretically that the performance & scalability dimensions (i.e. latency, throughput, dataset size) of the system are limited by the performance of a single node?

To give an example:
A system based on partitioned-logs, like Apache Kafka, can provide ordering guarantees in a single partition, but it can't provide any ordering guarantees between different partitions. However, this gives Kafka the capability to scale to extremely large datasets. I was contemplating whether it would be possible to create a system that could provide the ordering guarantee for the whole dataset, while also allowing the dataset's size to increase in the same quasi-linear way.

My speculative answer to this is no for the following reason:
It's been proved that the atomic broadcast problem is equivalent to the consensus problem [1]. Based on the fact that the consensus problem requires an elected leader, which drives the consensus process, I concluded that the scaling capabilities of such a system is limited by the resources of a single node.

Are there any flaws in my thinking ?

[1]: https://en.wikipedia.org/wiki/Atomic_broadcast#Equivalent_to_Consensus

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Your argument for "no" is flawed, for two reasons:

  • When we say that X reduces to Y, we mean that a solution to Y is one way to solve X. But there might be other ways to solve X that don't rely on solving Y.

  • Some protocols for consensus elect a leader, but that doesn't necessarily imply that all approaches to solve consensus require electing a leader. (For example: consider Bitcoin. No leader, but it arguably solves a consensus kind of problem.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer! Regarding the first point, if X and Y problems are equivalent (as is the case actually), would I still be able to do that jump in my inference ? Regarding the second point, that's a nice insight, I had never thought of distributed ledgers from this perspective, I'll definitely have a look into it. $\endgroup$
    – Dimos
    Mar 9, 2018 at 10:27
0
$\begingroup$

I've already accepted D.W.'s answer above, but posting some of my later findings for reference of people that end up reading this question:

  • As implied in the question, all consensus algorithms (e.g. Paxos, Raft, Chandra–Toueg) have an elected leader (even a temporary one) which is driving the convergence to the consensus result. This aspect creates a somewhat central bottleneck that would make a quasi-linear scaling extremely challenging. For instance, adding nodes to the system to increase performance would increase coordination, thus preventing big performance increases
  • With regards to Bitcoin and other similar (blockchain) approaches, it does not require an elected leader, but it solves a different version of the consensus problem. More specifically, Bitcoin achieves probabilistic (not deterministic) consensus.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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