7 ms·

Is the Hypothetical Amnesia Machine algorithm backed by any scholarly research, or can you at least cite some papers with similar techniques? Blog posts and jav

by qqueue 12y ago

Is the Hypothetical Amnesia Machine algorithm backed by any scholarly research, or can you at least cite some papers with similar techniques? Blog posts and javascript are nice, but I have a certain fondness for LaTeX-generated PDFs whenever data integrity is involved, e.g. HyperDex's pretty excellent papers: http://hyperdex.org/papers/ http://hyperdex.org/papers/

marknadal 12y ago
No papers yet, but I've been working on building up connection with academics and hiring them. So hopefully expect to see something published, but the process takes a while. Meanwhile I'm actively working on building towards a simulation system and an actual high-scale deployable battle testing environment. Think of these as taking the theory from scholastic research, and actually implementing them in practical settings that anybody can run. I'd also like to get a TLA+ specification going. If you have any experience in this stuff, please please please contact me mark@gunDB.io because this is important to me.
- roeme 12y ago
  When I read your responses, I can‘t shake the feeling I'm talking to some snake oil salesman in a nice suit.¹ And to be honest, GUN‘s docs sound similar. Heavy on how to use, and how awesome everything is, but as soon as one tries to understand stuff, it‘s either WIP or “team up with me/us!”. eyebrow rises And the claim of “building up connection with academics and hiring them” falls perfectly in line with this. Why the hell can‘t you describe what you did by yourself? If it's so awesome, why don‘t you just die to explain it to everyone who asks? Or, $DEITY forbid, should the “academics” lend some credibility to GUN, even if it's with just their title? What's this HAM about? Maybe it's just me, but all this with a rather complex naming convention (souls...) and code... eh, I'll go with “show us teh algoz”. Or describe it. ¹) To illustrate: « I'm actively working [...]» – I'd like to see you passively working.
  - karlgrz 12y ago
    It's not just you.
  - marknadal 12y ago
    Have you looked at the Wiki? https://github.com/amark/gun/wiki/Conflict-Resolution-with-Guns https://github.com/amark/gun/wiki/Conflict-Resolution-with-G... https://github.com/amark/gun/wiki/How-to-Create-GUN https://github.com/amark/gun/wiki/How-to-Create-GUN https://docs.google.com/presentation/d/1VIOJc0bdzUNs7yXMLKCcgwU8ZZqMh-G4XDJt8JRtvSA/edit#slide=id.g6c37d5900_0378 https://docs.google.com/presentation/d/1VIOJc0bdzUNs7yXMLKCc... No snake oil. It is a state machine operating over a boundary function. However words like that sound super jargony which sounds vague, despite the fact that people spend their entire lives working on just these problems sets and their nuances. I'm happy to discuss the workings, and I'd encourage you to try and use GUN and see if it can withstand your concurrency attacks. Challenge accepted? Edit: This person (in the comments below, please upvote him), and my reply, best addresses the most important questions: https://news.ycombinator.com/item?id=9077969 https://news.ycombinator.com/item?id=9077969
    - sseveran 12y ago
      Its up to you to prove your algorithm is correct, not everyone else to prove that its wrong.
      - marknadal 12y ago
        If people aren't interested in reading the materials I've provided that go over the concepts and algorithms, there is nothing I can do to "prove" anything to them, they just remain agnostic. Did you read the link to the other comment and my reply? I'd really appreciate it if you could critique it.
    - zero_iq 12y ago
      You're happy to discuss the workings? How about writing them down somewhere...? All your documentation, such as it is, describes things using terms that you never actually define or explain. Your code is just as bad. Worse in fact, because it introduces yet further terms that are not in the documentation. Your Conflict-Resolution-with-Guns page simply says 'see gun.HAM' for the explanation. No indication where this can be found. It isn't in the source repository and it isn't in the wiki. A google search reveals nothing. The 'algorithm' presented on How-to-Create-GUN is meaningless because you don't define any of the return values. I can see how it maps some input values to some output values, but nowhere do you say what any of those return values actually mean, what I should do with them, or why they are useful. e.g. return {amnesiaQuarantine: true} ... what does this mean? What should be done with that return value? What is an amnesiaQuarantine? e.g. return {quarantineState: true} ... what does this mean? How does it differ from amnesiaQuarantine: true? What is a quarantineState? How should I react to receiving this return value? Your documentation says a lot, but doesn't actually define anything, and is ultimately meaningless. This is why people are giving you a hard time and asking so many questions. Most people reading will not know: what amnesiaQuarantine is, what amnesiState is, what the Hypothetical Amnesia Machine thought experiment is, what a boundary function is (there are multiple definitions - what are you using?), what 'converge: true means', what 'incoming: true' means, what state: true means (given that you say other 'state' variables are times* -- how the hell does a boolean represent a time, what 'you have not properly handled recursion through your data' means. What is a 'soul'? What happens to the data when particular values are stored? Where are things stored? What is the data flow? How are things shared? How does sync happen? Imagine you don't know what any of your terminology means - like everybody reading your documentation. Treat each term like an undefined variable. Now try to understand your document. You can't. Those undefine terms are never 'set' anywhere. It doesn't make any sense. As soon as it gets close to actually explaining anything it just handwaves, or leaves you with undefined terminology. You don't define what kind of persistence you implement or what consistency guarantees (worse: your explanations do not seem consistent). You don't define how your conflict resolution works (the 'explanation' given is tantamount to Star Trek technobabble). You don't define how data is transferred. Your slides are useless without any notes. In your code you say that ACID is vague. It really isn't. Your explanation of how you meet ACID is extremely vague however, using what appear to be truisms and contradictions, and yet more undefined terms that seem to have little to do with anything mentioned in the documentation. Your code is poorly structured, and badly commented. It uses 'cool' sounding gun-related terminology ('shot', 'roulette', etc.) without defining what the hell those things mean. There is nothing in the code that actually seems to do anything with consistency Your HAM algorithm - the very crux of your system as stated in your documentation, remains unexplained, and WORSE.. has a TODO: comment noting that it might not work and needs further investigation. This comment also mentions rollbacks.... yet nowhere else in the code or documentation says anything about rollbacks, and it's not clear why rollbacks would even be needed according to the (vague) explanation of HAM. Your further explanations in these comments STILL do not actually describe precisely what HAM is or how it works. If you cannot do this in a simple and elegant manner, then NOBODY will be able to use or trust your database system. If you want anybody to take you seriously, you must write a simple and concise explanation of HAM, including definitions of all your terms. Frankly, it is so vague, and so unclear how it works that I am starting to think this is the product of some kind of mental illness... Sorry to be so harsh, but nobody seems to be getting through to you. EDIT: I'm reminded of Einstein's quote: "If you can't explain it simply, you don't understand it well enough."
- sseveran 12y ago
  I am not quite sure where to begin. I read your wiki. The casual disregard for years of distributed computing research struck me as a bit scary. It would be fine if the website did not claim "Data integrity is now a breeze." but it does. It turns out data integrity in a distributed setting is actually quite a hard problem given the number of boundary cases that exist. For that reason experienced practitioners building distributed algorithms start with proofs, not try to come up with them later. From reading your page on conflict resolution, which is quite light on details, it seems like you want to have a transaction log but unless the data is purely commutative that is impossible in an AP environment. If you are going to reference a "Hypothetical Amnesia Machine" it would be helpful to at least define it. Looking at the code you hand someone two versions of their data and ask us to merge it. It's nice that you are enthusiastic but it might be nice to build some proofs (or use someone elses) before making claims that our distributed state problems are solved.
  - marknadal 12y ago
    This person (in the comments below, please upvote him), and my reply, best addresses the most important questions: https://news.ycombinator.com/item?id=9077969 https://news.ycombinator.com/item?id=9077969 But to address your other comments: Why can't a transaction log be commutative? You just have to make sure to be explicit about the ordering of events (like by using linked lists or progressively incremented hashes). This is the realm for CRDTs and stuff though, which GUN core doesn't touch. Yes the HAM deals with merging any two logs/streams/history, any two snapshot/states, but also merging any log/stream/history with any snapshot/state. This is important, because it allows you to merge more than just two, you just have to do it serially (in any order). That merge algorithm guarantees the deterministic resolution (see the comment link I posted above).
    - sseveran 12y ago
      It relies on the data being commutative. If the data is not commutative then we need, wait for it, drum roll please, some consistency, which by your own admission is not provided. The consistency is the hard part which is why there is an entire field of study on just this problem. I fail to see how your merge algorithm is deterministic in case of failures.
roeme 12y ago
Seconded, I plowed through the “wiki” (not really one) and the code for a bit, but gave up after while. Doesn't have to be LaTeX for me, as long as it’s a comprehensive documentation. (When OriFS was introduced here, the papers really helped to grok).
- marknadal 12y ago
  Did you read https://github.com/amark/gun/wiki/How-to-Create-GUN https://github.com/amark/gun/wiki/How-to-Create-GUN ? It is only introductory though. The slides might be helpful. I've demonstrated GUN before handling conflict resolution across machines with significant drift. I need to get a video of this and more docs out on it.
  - roeme 12y ago
    I did, but as you said by yourself, it's short on info. The conflict resolution is where the meat is, isn't it? And https://github.com/amark/gun/wiki/Conflict-Resolution-with-Guns https://github.com/amark/gun/wiki/Conflict-Resolution-with-G... is incredibly hard to read and doesn't really answer questions.
    - marknadal 12y ago
      Yes, that is where the meat is. Do the slides from my tech talk help at all? https://docs.google.com/presentation/d/1VIOJc0bdzUNs7yXMLKCcgwU8ZZqMh-G4XDJt8JRtvSA/edit#slide=id.g6c37d5900_0378 https://docs.google.com/presentation/d/1VIOJc0bdzUNs7yXMLKCc... I'll be working on getting a recording of the tech talk up, more blogs/documentation on the algorithm specifically. And as others have mentioned, some actual academic papers (but that could be a while). Anything specific I can address? Edit: This person (in the comments below, please upvote him), and my reply, best addresses the most important questions: https://news.ycombinator.com/item?id=9077969 https://news.ycombinator.com/item?id=9077969

by qqueue 12y ago

marknadal 12y ago

No papers yet, but I've been working on building up connection with academics and hiring them. So hopefully expect to see something published, but the process takes a while. Meanwhile I'm actively working on building towards a simulation system and an actual high-scale deployable battle testing environment. Think of these as taking the theory from scholastic research, and actually implementing them in practical settings that anybody can run. I'd also like to get a TLA+ specification going. If you have any experience in this stuff, please please please contact me mark@gunDB.io because this is important to me.

roeme 12y ago
When I read your responses, I can‘t shake the feeling I'm talking to some snake oil salesman in a nice suit.¹ And to be honest, GUN‘s docs sound similar. Heavy on how to use, and how awesome everything is, but as soon as one tries to understand stuff, it‘s either WIP or “team up with me/us!”. eyebrow rises And the claim of “building up connection with academics and hiring them” falls perfectly in line with this. Why the hell can‘t you describe what you did by yourself? If it's so awesome, why don‘t you just die to explain it to everyone who asks? Or, $DEITY forbid, should the “academics” lend some credibility to GUN, even if it's with just their title? What's this HAM about? Maybe it's just me, but all this with a rather complex naming convention (souls...) and code... eh, I'll go with “show us teh algoz”. Or describe it. ¹) To illustrate: « I'm actively working [...]» – I'd like to see you passively working.
- karlgrz 12y ago
  It's not just you.
- marknadal 12y ago
  Have you looked at the Wiki? https://github.com/amark/gun/wiki/Conflict-Resolution-with-Guns https://github.com/amark/gun/wiki/Conflict-Resolution-with-G... https://github.com/amark/gun/wiki/How-to-Create-GUN https://github.com/amark/gun/wiki/How-to-Create-GUN https://docs.google.com/presentation/d/1VIOJc0bdzUNs7yXMLKCcgwU8ZZqMh-G4XDJt8JRtvSA/edit#slide=id.g6c37d5900_0378 https://docs.google.com/presentation/d/1VIOJc0bdzUNs7yXMLKCc... No snake oil. It is a state machine operating over a boundary function. However words like that sound super jargony which sounds vague, despite the fact that people spend their entire lives working on just these problems sets and their nuances. I'm happy to discuss the workings, and I'd encourage you to try and use GUN and see if it can withstand your concurrency attacks. Challenge accepted? Edit: This person (in the comments below, please upvote him), and my reply, best addresses the most important questions: https://news.ycombinator.com/item?id=9077969 https://news.ycombinator.com/item?id=9077969
  - sseveran 12y ago
    Its up to you to prove your algorithm is correct, not everyone else to prove that its wrong.
    - marknadal 12y ago
      If people aren't interested in reading the materials I've provided that go over the concepts and algorithms, there is nothing I can do to "prove" anything to them, they just remain agnostic. Did you read the link to the other comment and my reply? I'd really appreciate it if you could critique it.
  - zero_iq 12y ago
    You're happy to discuss the workings? How about writing them down somewhere...? All your documentation, such as it is, describes things using terms that you never actually define or explain. Your code is just as bad. Worse in fact, because it introduces yet further terms that are not in the documentation. Your Conflict-Resolution-with-Guns page simply says 'see gun.HAM' for the explanation. No indication where this can be found. It isn't in the source repository and it isn't in the wiki. A google search reveals nothing. The 'algorithm' presented on How-to-Create-GUN is meaningless because you don't define any of the return values. I can see how it maps some input values to some output values, but nowhere do you say what any of those return values actually mean, what I should do with them, or why they are useful. e.g. return {amnesiaQuarantine: true} ... what does this mean? What should be done with that return value? What is an amnesiaQuarantine? e.g. return {quarantineState: true} ... what does this mean? How does it differ from amnesiaQuarantine: true? What is a quarantineState? How should I react to receiving this return value? Your documentation says a lot, but doesn't actually define anything, and is ultimately meaningless. This is why people are giving you a hard time and asking so many questions. Most people reading will not know: what amnesiaQuarantine is, what amnesiState is, what the Hypothetical Amnesia Machine thought experiment is, what a boundary function is (there are multiple definitions - what are you using?), what 'converge: true means', what 'incoming: true' means, what state: true means (given that you say other 'state' variables are times* -- how the hell does a boolean represent a time, what 'you have not properly handled recursion through your data' means. What is a 'soul'? What happens to the data when particular values are stored? Where are things stored? What is the data flow? How are things shared? How does sync happen? Imagine you don't know what any of your terminology means - like everybody reading your documentation. Treat each term like an undefined variable. Now try to understand your document. You can't. Those undefine terms are never 'set' anywhere. It doesn't make any sense. As soon as it gets close to actually explaining anything it just handwaves, or leaves you with undefined terminology. You don't define what kind of persistence you implement or what consistency guarantees (worse: your explanations do not seem consistent). You don't define how your conflict resolution works (the 'explanation' given is tantamount to Star Trek technobabble). You don't define how data is transferred. Your slides are useless without any notes. In your code you say that ACID is vague. It really isn't. Your explanation of how you meet ACID is extremely vague however, using what appear to be truisms and contradictions, and yet more undefined terms that seem to have little to do with anything mentioned in the documentation. Your code is poorly structured, and badly commented. It uses 'cool' sounding gun-related terminology ('shot', 'roulette', etc.) without defining what the hell those things mean. There is nothing in the code that actually seems to do anything with consistency Your HAM algorithm - the very crux of your system as stated in your documentation, remains unexplained, and WORSE.. has a TODO: comment noting that it might not work and needs further investigation. This comment also mentions rollbacks.... yet nowhere else in the code or documentation says anything about rollbacks, and it's not clear why rollbacks would even be needed according to the (vague) explanation of HAM. Your further explanations in these comments STILL do not actually describe precisely what HAM is or how it works. If you cannot do this in a simple and elegant manner, then NOBODY will be able to use or trust your database system. If you want anybody to take you seriously, you must write a simple and concise explanation of HAM, including definitions of all your terms. Frankly, it is so vague, and so unclear how it works that I am starting to think this is the product of some kind of mental illness... Sorry to be so harsh, but nobody seems to be getting through to you. EDIT: I'm reminded of Einstein's quote: "If you can't explain it simply, you don't understand it well enough."
sseveran 12y ago
I am not quite sure where to begin. I read your wiki. The casual disregard for years of distributed computing research struck me as a bit scary. It would be fine if the website did not claim "Data integrity is now a breeze." but it does. It turns out data integrity in a distributed setting is actually quite a hard problem given the number of boundary cases that exist. For that reason experienced practitioners building distributed algorithms start with proofs, not try to come up with them later. From reading your page on conflict resolution, which is quite light on details, it seems like you want to have a transaction log but unless the data is purely commutative that is impossible in an AP environment. If you are going to reference a "Hypothetical Amnesia Machine" it would be helpful to at least define it. Looking at the code you hand someone two versions of their data and ask us to merge it. It's nice that you are enthusiastic but it might be nice to build some proofs (or use someone elses) before making claims that our distributed state problems are solved.
- marknadal 12y ago
  This person (in the comments below, please upvote him), and my reply, best addresses the most important questions: https://news.ycombinator.com/item?id=9077969 https://news.ycombinator.com/item?id=9077969 But to address your other comments: Why can't a transaction log be commutative? You just have to make sure to be explicit about the ordering of events (like by using linked lists or progressively incremented hashes). This is the realm for CRDTs and stuff though, which GUN core doesn't touch. Yes the HAM deals with merging any two logs/streams/history, any two snapshot/states, but also merging any log/stream/history with any snapshot/state. This is important, because it allows you to merge more than just two, you just have to do it serially (in any order). That merge algorithm guarantees the deterministic resolution (see the comment link I posted above).
  - sseveran 12y ago
    It relies on the data being commutative. If the data is not commutative then we need, wait for it, drum roll please, some consistency, which by your own admission is not provided. The consistency is the hard part which is why there is an entire field of study on just this problem. I fail to see how your merge algorithm is deterministic in case of failures.

roeme 12y ago

Seconded, I plowed through the “wiki” (not really one) and the code for a bit, but gave up after while. Doesn't have to be LaTeX for me, as long as it’s a comprehensive documentation. (When OriFS was introduced here, the papers really helped to grok).

marknadal 12y ago
Did you read https://github.com/amark/gun/wiki/How-to-Create-GUN https://github.com/amark/gun/wiki/How-to-Create-GUN ? It is only introductory though. The slides might be helpful. I've demonstrated GUN before handling conflict resolution across machines with significant drift. I need to get a video of this and more docs out on it.
- roeme 12y ago
  I did, but as you said by yourself, it's short on info. The conflict resolution is where the meat is, isn't it? And https://github.com/amark/gun/wiki/Conflict-Resolution-with-Guns https://github.com/amark/gun/wiki/Conflict-Resolution-with-G... is incredibly hard to read and doesn't really answer questions.
  - marknadal 12y ago
    Yes, that is where the meat is. Do the slides from my tech talk help at all? https://docs.google.com/presentation/d/1VIOJc0bdzUNs7yXMLKCcgwU8ZZqMh-G4XDJt8JRtvSA/edit#slide=id.g6c37d5900_0378 https://docs.google.com/presentation/d/1VIOJc0bdzUNs7yXMLKCc... I'll be working on getting a recording of the tech talk up, more blogs/documentation on the algorithm specifically. And as others have mentioned, some actual academic papers (but that could be a while). Anything specific I can address? Edit: This person (in the comments below, please upvote him), and my reply, best addresses the most important questions: https://news.ycombinator.com/item?id=9077969 https://news.ycombinator.com/item?id=9077969