7 ms·
Mathematical Reasoning and Distributed Systems by Erik Meijer and Leslie Lamport
- jzelinskie 10y agoInteresting to see a Channel9 video on YouTube. Erik Meijer's genuine interest in the subjects in his videos make them a pleasure to watch.
- js8 10y agoI really like his point(s) about mathematics and programming, as he talks about functional programming, especially at 47:20.
- pron 10y agoLamport has always been in favor of a rigorous mathematical reasoning about programs, but has always warned against looking for a "new math", the "right kind of math", or a "silver bullet math" (in other talks he calls it "weird computer-science math"), as he believes that ordinary math is all you need. So yeah, Lamport is not a big fan of FP (or any PL theory for that matter). He's been fighting the Robin Milner school of thought, or PL semantics in general since at least the early nineties. He says here that once you deal with all the incidental complexity, you're left with the essential complexity, and that is the hard part, and he's skeptical of the ability of "new math" to help solve the problem. See: http://research.microsoft.com/en-us/um/people/lamport/pubs/state-machine.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/s...
- nickpsecurity 10y ago"He's been fighting the Robin Milner school of thought, or PL semantics in general since at least the early nineties. " What does that mean for those of us that follow the formal methods at a high-level?
- throwaway729 10y agoOne major school of thought in formal methods is the type theory tradition. The one-sentence formal methods interpretation of this program is that types are theorems and programs are proofs. The idea, basically, is to choose a type system that is expressive enough to encode interesting properties. Then, if your program has that type, you know that your program is correct with respect to the specification that is encoded in the type. It turns out that there are type theories in which arbitrary mathematical properties can be encoded and proven, so this approach is very versatile. Systems such as Coq, NuPRL, Idris, and Lean are in this tradition.+ Obviously, there are also other approaches to formal methods that are not built upon type theory. However, my experience is that the type theorists have been incredibly productive, so if you spend enough time doing formal methods you'll probably find some work done in the type theory tradition that's useful or relevant to any particular approach. + I'm not a type theorist and have reason to believe that certain type theorists would perhaps disagree with this characterization for reason that would be rather difficult for a non-type-theorist to understand, but hopefully this gives you a rough idea. Also, it's worth noting that those in the Milner tradition see their agenda as being far more than just one approach toward formal methods, and also as not being principally about types. But thinking about that tradition in terms of Coq et al. and props-as-types is the best way to understand its place in Formal Methods.
- pron 10y ago> However, my experience is that the type theorists have been incredibly productive They have, but much less so than people in the "temporal logic tradition". Type theory-based formal methods are virtually nonexistent in the industry (and the word virtually could probably be replaced with literally if we don't count joint industry-academia projects), while temporal logic is used to verify thousands of applications every year. The reason you see fewer papers is precisely because the approach is less mature. On the other hand, you find that papers using more traditional approaches are more cited (e.g., Lamport's first TLA paper alone has many more citations than any paper on type theory ever). It is true, however, that PL theory is about much more than just formal methods (it is first and foremost about programming languages). The problem they're tackling is much harder and more ambitious, but so far they've had little success in the field.
- deleted 10y ago[deleted]
- zzzcpan 10y agoWell, his points about necessary hard math and proving correctness resemble those of many in academia, I can understand your bias. But it is a bias and there isn't even a good argument to support it. Proofs never actually cover absolutely every possible case and we also can have as reliable software without the hard math whatsoever. But going into psychology and thinking about making things easy for humans goes against what is generally accepted in CS research.
- KirinDave 10y ago> Proofs never actually cover absolutely every possible case That's precisely what you need to do in order to have a valid proof. I'm not sure why you'd say this?
- SomeStupidPoint 10y agoMost proofs have assumptions about the system which can be (occasionally/rarely) violated, but which make the proof tractable, or simply don't model features of the real system. I think the point is that you can have a proof of correctness in a crypto package that doesnt account for power-usage side-channel attacks, for example. This is true, but beside the point: a library with no proofs about it doesn't solve that problem, and the library with proofs tells me I don't have certain problems for sure. The question is then: is it worth the proof development effort to only get those partial guarantees? I would argue yes, for a lot of reasons (and high EAL levels tend to agree that it is for high-assurance stuff), but it's a matter of some debate.
- KirinDave 10y agoI am fairly sure, upon reading this thread, that this is not zzzcpan's point. His point is to denigrate the entire practice if providing proofs. I think he's referring to fields which, given their critical and highly difficult nature, should in fact start with the proofs and work to invalidate the system over increasingly more total domains of implemention. You're right that you can take a mathematical proof out of the realm of abstract math and it's new domain may not have all the guarantees we need, but this means we need to extend the system to account for the new domain (and within this domain, the proof is not valid). But the poster doubled down on this idea that "there are constraints proofs ignore" within the existing domain. Outside of convenient proofs that upper division students provide, this is not true. A good example of this process and the nature of "pure" CS interacting with the real world is the field of distributed databases. As the field has grown, proofs are expected to aggressively model real world conditions and in fact go further, modeling outright adversarial conditions unlikely to occur in the real world.
- chadcmulligan 10y agoThat's a very disappointing shirt Erik is wearing
- tomonl 10y agoIt's just his style, if you look him up on Google Images you'll see he always wears shirts like that.
- chadcmulligan 10y agothats what I meant - it's not as bright as his usual style
- jasode 10y agoFyi... the original video released in 2010 is at channel9 and that website also has download options for offline viewing: https://channel9.msdn.com/Shows/Going+Deep/E2E-Erik-Meijer-and-Leslie-Lamport-Mathematical-Reasoning-and-Distributed-Systems https://channel9.msdn.com/Shows/Going+Deep/E2E-Erik-Meijer-a...
- deleted 10y ago[deleted]
- nickpsecurity 10y agoIt was an interesting article. Neat how one scheme was inspired by a bakery. The concern with the red light happened to me. Its timing was odd where I wasn't sure if I'd make it or not but on a road with a high speed limit. I decided to brake at the last moment. Should've worked but tires were bald. I landed in the middle of the intersection with a police officer to my right. So, the "hypothetical" example of Lamport cost me money in the real world. ;) However, I reject his notion that computation is basically digital, step-by-step process. There's actually at least two models of computation where one is continuous. I gave a lot of detail in the link below: https://lobste.rs/c/zyj5e1 https://lobste.rs/c/zyj5e1
- senderista 10y agoRe: Lamport clocks and special relativity: I don't think Lamport makes it sufficiently clear that the SR analogy is just an analogy and is not physically relevant. It is perfectly valid to treat the computers in a datacenter as a single inertial reference frame, with a natural notion of simultaneity. (Geo-distributed clocks can still be synchronized, since the Schwarzschild solution defines spacelike hypersurfaces with constant time coordinate.) Logical clocks (which totally order events consistent with their causal relations) are useful (because synchronization is hard), but not physically necessary (because synchronization is possible).