Does this question belong on cstheory or cs?

Suppose that one has a choice of two systems:

  1. A single, centralized system that can process $X$ requests per second
  2. A distributed system with $N$ servers, each of which can process $Y$ requests per second.
    • Each small server costs $Q$ dollars
    • $Y < X$, but $N * Y > X$. This models the common case where one can choose between one large server or many smaller servers, which together are more powerful than the large server.
    • The servers are connected by a network (or networks) with bandwidth $B$ and latency $T$. You can choose any reasonable topology for the network, but it must be realistic (as in used in practice).

Suppose also that:

  • Profit is proportional to the rate $R$ at which we can accept messages (so we want to maximize that).
  • Messages arrive (on average) uniformly at each server.
  • this is the key point: each message requires a database query. The data is stored on the servers. Storage for the servers (both small and large) costs $C$ per unit size up to a limit $S$ for the small servers and $L$ for the large one, with $S < L$. The data can all fit on the large server, but must be distributed among the small servers.

The question is: When is it better to use the single large server (vs. the larger server), in terms of throughput?


1 Answer 1


The way to figure out is to ask yourself: "Is this a research-level question about theoretical computer science?"

So, is this a research-level question? I'm not an expert in queueing theory, so you might be a better judge, but my first impression is: I don't think so. It sounds like you are just asking a question about a calculation using queueing theory.

Is it a question about theoretical computer science? Well, not so much. It's more a quantitative question about distributed systems and performance modelling. I don't see any theoretical/foundational issue here. It might be OK on cstheory if it were research-level, but it looks a bit marginal to me.

So, I'd recommend CS.stackexchange over CSTheory.

That said, one other bit of feedback before you post. I find the database stuff unclear. OK, so we have to use a database, but you haven't told us how the database affects throughput. What's the throughput of the database if you use a single centralized system? What's the throughput of the database if you use a distributed system? And does each serve do the database query in parallel with handling the request, or sequentially? Those will affect the answer. It's also not clear why you are telling about the costs of storage or the costs of small servers when that doesn't affect the final answer; as far as I can tell, all you are asking is how to maximize throughput, for which cost is irrelevant.

So, I find the question unclear and in need of clarification before it should be asked on any site.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .