Skip to main content
more...
Source Link
Jukka Suomela
  • 11.6k
  • 2
  • 56
  • 117

I will answer this from the perspective of classical graph problems (or input/output problems): we have a network, each node gets something as input and each node must produce something as output. I guess this is closest to the world of traditional computational complexity.

I am certainly biased, but I think that in this setting, there is a simple and fairly commonly used model of distributed computing: synchronous distributed algorithms, with the definition that running time = number of synchronous rounds. In Peleg's terminology, this is the LOCAL model.

This model is nice as it has very few "moving parts", no parameters, etc. Nevertheless, it is very concrete: it makes sense to say that the running time of an algorithm is exactly 15 in this model. And you can prove unconditional, information-theoretic lower bounds: from this perspective, the distributed complexity of many graph problems (e.g., graph colouring) is fairly well-understood.

This model also provides a unified approach to many aspects of distributed computing:

  • Message-passing vs. shared memory, broadcast vs. unicast: Irrelevant in this model.
  • Your real-world system is asynchronous? No problem, just plug in the $\alpha$-synchroniser. The time complexity (with suitable definitions) is essentially unaffected.
  • You'd like to have an algorithm for dynamic networks, or you'd like to recover from failures? Well, if your synchronous algorithm is deterministic, then you can use it to construct a self-stabilising algorithm. Again, the time complexity is essentially unaffected.

Now all this is fine as long as you study problems that are "truly distributed" in the sense that the running time of your algorithm is smaller than the diameter of the graph, i.e., no node needs to have full information on the structure of the graph. However, there are also many problems that are inherently global: the fastest algorithm in this model has running time that is linear in the diameter of the graph. In the study of those problems, the above model no longer makes any sense, and then we need to resort to something else. Typically, one starts to pay attention to the total number of messages or bits communicated in the network. That's one reason why we get several different models.


Then of course we have the issue that the distributed computing community is actually two different communities, with surprisingly few things in common. If you lump together all models from two communities, it will certainly look a bit confusing... My answer above is related to only one half of the community; I trust others will fill in regarding the other half.

I will answer this from the perspective of classical graph problems (or input/output problems): we have a network, each node gets something as input and each node must produce something as output. I guess this is closest to the world of traditional computational complexity.

I am certainly biased, but I think that in this setting, there is a simple and fairly commonly used model of distributed computing: synchronous distributed algorithms, with the definition that running time = number of synchronous rounds. In Peleg's terminology, this is the LOCAL model.

This model is nice as it has very few "moving parts", no parameters, etc. Nevertheless, it is very concrete: it makes sense to say that the running time of an algorithm is exactly 15 in this model. And you can prove unconditional, information-theoretic lower bounds: from this perspective, the distributed complexity of many graph problems (e.g., graph colouring) is fairly well-understood.

This model also provides a unified approach to many aspects of distributed computing:

  • Message-passing vs. shared memory, broadcast vs. unicast: Irrelevant in this model.
  • Your real-world system is asynchronous? No problem, just plug in the $\alpha$-synchroniser. The time complexity (with suitable definitions) is essentially unaffected.
  • You'd like to have an algorithm for dynamic networks, or you'd like to recover from failures? Well, if your synchronous algorithm is deterministic, then you can use it to construct a self-stabilising algorithm. Again, the time complexity is essentially unaffected.

Now all this is fine as long as you study problems that are "truly distributed" in the sense that the running time of your algorithm is smaller than the diameter of the graph, i.e., no node needs to have full information on the structure of the graph. However, there are also many problems that are inherently global: the fastest algorithm in this model has running time that is linear in the diameter of the graph. In the study of those problems, the above model no longer makes any sense, and then we need to resort to something else. Typically, one starts to pay attention to the total number of messages or bits communicated in the network. That's one reason why we get several different models.

I will answer this from the perspective of classical graph problems (or input/output problems): we have a network, each node gets something as input and each node must produce something as output. I guess this is closest to the world of traditional computational complexity.

I am certainly biased, but I think that in this setting, there is a simple and fairly commonly used model of distributed computing: synchronous distributed algorithms, with the definition that running time = number of synchronous rounds. In Peleg's terminology, this is the LOCAL model.

This model is nice as it has very few "moving parts", no parameters, etc. Nevertheless, it is very concrete: it makes sense to say that the running time of an algorithm is exactly 15 in this model. And you can prove unconditional, information-theoretic lower bounds: from this perspective, the distributed complexity of many graph problems (e.g., graph colouring) is fairly well-understood.

This model also provides a unified approach to many aspects of distributed computing:

  • Message-passing vs. shared memory, broadcast vs. unicast: Irrelevant in this model.
  • Your real-world system is asynchronous? No problem, just plug in the $\alpha$-synchroniser. The time complexity (with suitable definitions) is essentially unaffected.
  • You'd like to have an algorithm for dynamic networks, or you'd like to recover from failures? Well, if your synchronous algorithm is deterministic, then you can use it to construct a self-stabilising algorithm. Again, the time complexity is essentially unaffected.

Now all this is fine as long as you study problems that are "truly distributed" in the sense that the running time of your algorithm is smaller than the diameter of the graph, i.e., no node needs to have full information on the structure of the graph. However, there are also many problems that are inherently global: the fastest algorithm in this model has running time that is linear in the diameter of the graph. In the study of those problems, the above model no longer makes any sense, and then we need to resort to something else. Typically, one starts to pay attention to the total number of messages or bits communicated in the network. That's one reason why we get several different models.


Then of course we have the issue that the distributed computing community is actually two different communities, with surprisingly few things in common. If you lump together all models from two communities, it will certainly look a bit confusing... My answer above is related to only one half of the community; I trust others will fill in regarding the other half.

Source Link
Jukka Suomela
  • 11.6k
  • 2
  • 56
  • 117

I will answer this from the perspective of classical graph problems (or input/output problems): we have a network, each node gets something as input and each node must produce something as output. I guess this is closest to the world of traditional computational complexity.

I am certainly biased, but I think that in this setting, there is a simple and fairly commonly used model of distributed computing: synchronous distributed algorithms, with the definition that running time = number of synchronous rounds. In Peleg's terminology, this is the LOCAL model.

This model is nice as it has very few "moving parts", no parameters, etc. Nevertheless, it is very concrete: it makes sense to say that the running time of an algorithm is exactly 15 in this model. And you can prove unconditional, information-theoretic lower bounds: from this perspective, the distributed complexity of many graph problems (e.g., graph colouring) is fairly well-understood.

This model also provides a unified approach to many aspects of distributed computing:

  • Message-passing vs. shared memory, broadcast vs. unicast: Irrelevant in this model.
  • Your real-world system is asynchronous? No problem, just plug in the $\alpha$-synchroniser. The time complexity (with suitable definitions) is essentially unaffected.
  • You'd like to have an algorithm for dynamic networks, or you'd like to recover from failures? Well, if your synchronous algorithm is deterministic, then you can use it to construct a self-stabilising algorithm. Again, the time complexity is essentially unaffected.

Now all this is fine as long as you study problems that are "truly distributed" in the sense that the running time of your algorithm is smaller than the diameter of the graph, i.e., no node needs to have full information on the structure of the graph. However, there are also many problems that are inherently global: the fastest algorithm in this model has running time that is linear in the diameter of the graph. In the study of those problems, the above model no longer makes any sense, and then we need to resort to something else. Typically, one starts to pay attention to the total number of messages or bits communicated in the network. That's one reason why we get several different models.