5
$\begingroup$

In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote

Most computer scientists regard synchronization problems, such as the mutual exclusion problem, to be problems of mathematics. How can you use one class of mathematical objects, like atomic reads and writes, to implement some other mathematical object, like a mutual exclusion algorithm? I have always regarded synchronization problems to be problems of physics. How do you use physical objects, like registers, to achieve physical goals, like not having two processes active at the same time?

My question is on the mutual exclusion problem particularly.

What is the significance of regarding the mutual exclusion problem as a problem of physics? More specifically,

  1. What are the differences between the mathematical perspective and the physical one on the mutual exclusion problem?
  2. What inspirations and results have been gained directly from the physical perspective?
|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ What is the difference between physics and mathematics? $\endgroup$ – babou Aug 11 '14 at 17:23
  • 1
    $\begingroup$ I think the best we can do here is guess what Leslie meant. My guess is that the difference implied is that "Is this a good model of reality?" is a physical and not a mathematical question. Registers with atomic reads and writes may not be physically realizable, or may be expensive to realize, which motivates studying non-atomic registers. $\endgroup$ – Sasho Nikolov Aug 11 '14 at 21:38
  • $\begingroup$ @SashoNikolov I agree with you that the transition from atomic registers to non-atomic ones is essential. When I read Leslie's papers on mutual exclusion, I am often impressed by his references to wires and signals in the hardware level. $\endgroup$ – hengxin Aug 12 '14 at 3:12
  • $\begingroup$ @babou Hard to answer it (at least for me). I think the answer from Sasho Nikolov is useful. $\endgroup$ – hengxin Aug 12 '14 at 3:24
  • $\begingroup$ The immediate physical analogue that I could think of such an isolation in space and time is the [cluster decomposition principle][1] in quantum field theory (and thus all of physics). [1]: en.wikipedia.org/wiki/Cluster_decomposition_theorem $\endgroup$ – Kaveh Khodjasteh Aug 12 '14 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.