2
$\begingroup$

I've recently learned about distributed computing and the synchronous model where, assuming a complete network and no crashes, in each round the following happens:

  1. every node can send a message to all other nodes,
  2. all of these messages are received by all nodes by the end of the current round, and
  3. at the start of the next round, every node performs some local computation (taking into account received messages).

It seems to me that this model is a more specific variant of the classic BSP model of Valiant where the cost of the barrier synchronization and the local computation is ignored.

Am I missing something else that distinguishes the distributed model from the BSP model?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I don't see much intrinsic differences between them. At the level of concept, they are similar. However, I want to argue that they are proposed for different settings: BSP for parallel computing where you may have a hardware facility that allows for the synchronisation of all or a subset of components while synchronous model for distributed computing where individual components are more loosely coupled. In the latter setting, how to simulate the synchronous model in some relatively realistic environment becomes a key issue. $\endgroup$
    – hengxin
    Jan 26, 2015 at 13:04

1 Answer 1

Reset to default
1
$\begingroup$

In the CONGEST model of distributed computing, the topology of the computer network is a graph $G$. In each round, each node can send a message to each of its neighbours in $G$. Typically, we assume that $G$ is unknown, we interpret the structure of $G$ as the input, and we are interested in solving graph problems related to the structure of $G$.

This is the key difference. In BSP there is no underlying graph topology that limits communication; in CONGEST there is a graph that determines who can talk directly with whom.

However, things get interesting if we set $G = K_n$ in the CONGEST model. That is, the network topology is a complete graph on $n$ nodes. This way we arrive at a model called the congested clique.

The congested clique is very closely related to the BSP model. The key difference is the following:

  • Congested clique: the bandwidth constraints are on the edges; for each pair of nodes $u$ and $v$, in each round $u$ can send at most $b$ bits to $v$.

  • BSP: the bandwidth constraints are on the nodes; for each node $u$, in each round $u$ can send at most $B$ bits in total to all other nodes, and receive at most $B$ bits in total from all other nodes.

Clearly, any congested clique algorithm is trivial to simulate in the BSP model if we have $B = nb$, with only a constant overhead. [I am ignoring some issues related to the local computation.]

Lenzen (2013) shows that the converse is also true: any BSP algorithm can be simulated in the congested clique model if we have $B = nb$, with only a constant overhead.

In summary, if we eliminate $G$ from the CONGEST model, we basically arrive at the BSP model. Hence the graph $G$ is the only difference between the models.

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.