Git does use diffs extensively its algorithms, just not in its representation of history. Git's "domain model" is blobs, trees, commits, branches and tags.
At a lower layer than that (the pack files) it does use binary diffs to store similar objects as deltas to save on disk space.
TL;DR diffs play an important part in git's machinery at different levels of abstraction. They just aren't part of how it represents its domain model.
As others have said, often you don't want to free the node, you want to do something else with it. E.g., put it in a free list. However, usually if you're not freeing it, you'd null out the next field so that you don't accidentally access it when it's not part of the list (at least I would).
Can anyone recommend some good cryptography books/links for someone that would like get up to speed on best practices for building secure systems? Ideally the full gamut of beginner to advanced.
What are the classic/authoritative texts in this space?
If you don't have a stage then you don't get to edit/stage/edit/stage/fix/commit, right? I use that workflow a lot. I generally like incrementally building and refining my next commit. The stage/index is one of Git's most innovative features IMHO.
The same workflow can be accomplished by amending commits in git, without a whole new set of semantics needed for managing the staging area (or needing to stash changes when switching branches).
If the Planck length is Lorentz-invariant but macro-scale objects are not then does that not imply there is a special universal reference frame against which to measure velocity?
If I have understood the article correctly one would be able to measure the length of a spaceship relative to the Planck length and deduce velocity, entirely locally (i.e. onboard the spaceship).
This is a fundamental departure from general relativity which says there is no special frame of reference.
I guess this is simply one of the many incompatibilities between quantum theory and general relativity.
There are many attempts to combine these theories into a universal theory (pun intended), but it is hard to check the corner cases where those theories differ. That's one of the reasons we build better and better particle accelerators.
Either way, it doesn't make sense to apply (pure) general relativity to the small scale, nor to apply (pure) quantum theory to the large scale. The physicists know for decades about of that issue and are already taking care of that.
Quantum Gravity is pretty coherent it can explain the universe we see today, it can explain why an apple drops, and it can explain why galaxies form, it cannot explain the big bang and some periods after it but neither can general relativity.
For the most part particle accelerators are not needed to explain quantum gravity, we do use them to find "new physics" but this new physics is more in the lines of the known unknowns.
We also do apply relativity to small scales every day, without relativity muons could not be discovered and without relativity to some extent even large particle accelerators would not "work" because the effects of spatial contractions are pretty important for how we predict and analyse the data coming from particle accelerators especially the "messy kind" like the LHC.
As for the large scale stuff as mentioned earlier quantum gravity is pretty compatible with general relativity in terms of explaining how the universe that we see today looks and works, you can easily explain why and how the moon rotates around the earth, it does rely on a massless spin-2 particle called a graviton which is yet to be "discovered" and it does break if the graviton would have a different spin (for example spin-0 graviton).
So I don't really understand the notion of why people still think that quantum gravity and general relativity aren't compatible to the extent of "what the fuck is going on", which is odd since afterall GR isn't 100% compatible with the Standard Model either, since GR is background independent and does not care about the particular state or shape of space-time while SM does.
From your long statement I read that you agree with my criticism that one should not use the plain quantum theory, mix it with the plain general relativity, and wonder why this leads to contradictions. Of course it does! If one wants a coherent model, one should use the Standard Model instead (or one if its variants).
Not sure at which point you disagree with my statement, though.
Depends on what you define as GR, there are classical and relativistic versions of Quantom Mechanics.
Each theory is useful for various things because each theory provides you with certain tools and perspectives that are useful for performing specific tasks.
At the end every theory is a set of laws and abstractions you use theories to change the perspective of how you look at things but these are often abstracts.
You can look at particles as particles, waves or fields it doesn't change reality but every one of these viewpoints comes with its unique benefits and you can chose between them depending on what benefits you most to for a specific task or a situation.
A bit of a quibble but Lorentz transforms are a consequence of Special Relatively, and therefore predate General Relativity. That is, the objection you are raising would apply to frames of reference without referring to General Relativity, just Special relativity.
To the extent that CRDTs are conflict-free it only means that two edits can commute (be applied in any order) and every party that has applied the same set of edits will produce the same result.
At the low-level that the CRDT is operating on there will be no conflicts.
But that does not mean that the user never perceives there to be conflicts. No matter what the consensus system used be it CRDTs or OT at some point the converge operation has to impose a total ordering to pick a "winner" in the case of conflicting user edits.
If editing a block of text and two users try to replace the same word with another word there are a number of possible outcomes
1) One of the edits "wins"
2) The word is replaced by the concatenation of each user's replacement.
3) Nobody wins and the edit is reverted.
In all cases at least one party perceives to themselves to have "lost". But it generally doesn't matter because humans doing the editing will make repairs to nonsensical edits in real time.
There has to be a tie-breaker when multiple users try to make different edits to the same region of text. At least that's my current understanding.
There are several CRDT algorithms (LSEQ, Logoot, WOOT, Treedoc) that try to properly solve the merging solution (your outcome #2) while still retaining the intent of the edits of each user. Their implementations differ, but the general idea is that each character (or chunk of characters) is assigned a key that can be ordered. When new text is added, it's given a key that is derived from the key of some adjacent text. As a result, the merge is the best-possible approximation of the intent of the edits.
Yes, I think we are in agreement. The algorithm can use heuristics to produce a best-effort pleasing result that captures user intent but if two users want opposite things to happen it has to fall back to a tie breaker.
In an extreme example, if the CRDT state-space was 1-bit and user A wants to make it a 0 and user B wants to make it a 1 a choice must be made by the algorithm.
Right, exactly. The key question is whether the algorithm's resolution heuristic takes into account the intent of the edit, and I'm not sure the algorithm in the article makes an effort to do that. (Not saying it doesn't, I just don't understand how it does, if it does.)
It's main consideration appears to be to make changes in a way that makes sense for a tree consisting of maps and lists without ever losing user input. If you look at their diagram with examples you get the gist of their resulting heuristics, which basically boils down to "only delete if a user explicitly deleted, otherwise keep both values if users try to set the same value to two different things", "if two complex values (maps,list) have been updated, recursively merge them", pretty much.
It will cause stuff that users will perceive as conflicts, and that may even appear to be totally illogical (one of their examples leaves an object that appears to be in a broken state, because one side deleted it, and the other side updated a single attribute, leading the map to continue to exist, but with only the one updated attribute) so there's probably room for improvement, though the rules are simple enough that many of these could be resolved at application level by just carefully deciding what operation to provide.
There is no "extent" to which CRDTs are conflict free, CRDTs are by definition always 100% conflict free.
"No matter what the consensus system used be it CRDTs or OT"
CRDTs and OT are worlds apart. CRDTs are guaranteed to be conflict free, whereas OT is generally too complicated and unproven to offer that guarantee at all.
"If editing a block of text and two users try to replace the same word with another word there are a number of possible outcomes"
There are actually many more possible outcomes than those you listed, so that with CRDTs designed explicitly for collaborative string editing you can provide perfect intent-preserving merges to the user. There is an excellent paper on preserving intent, see "Replicated abstract data types: Building blocks for collaborative applications" (http://dl.acm.org/citation.cfm?id=1931272")
> whereas OT is generally too complicated and unproven to offer that guarantee at all.
Citation needed.
I've built several production-level OT-based systems on top of ShareJS's JSON OT[1] code. The set of operations supported is guaranteed to be conflict-free and correct. We don't have AGDA proofs but we've used fuzzers to ferret out correctness bugs and its been about 2 years since a bug was found in the transform code. All in all, I'm very happy with the implementation.
Meanwhile, I don't believe a more generic JSON OT / CRDT system can be made conflict-free. (Well it can be conflict-free, but you'll lose data if it is). If you support arbitrary tree-level moves, you have the User A moves x into y's children, user B moves y into x's children problem. There are simply no good ways to resolve these operations without user intervention, or a lot more knowledge of the data structures at play.
"Due to the need to consider complicated case coverage, formal proofs are very complicated and error-prone, even for OT algorithms that only treat two characterwise primitives (insert and delete)" - Du Li & Rui Li - "An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems"
There's also an interesting comment there from the author of ShareJS, I think that might be you?
The other critical difference between CRDTs and OT is that CRDTs work offline, in a distributed setting, whereas OT cannot. OT requires a central online server to coordinate, which as far as I understand is the cause of the classic UI freeze in Google Docs whenever the network goes.
Yes thats me! For what its worth, I no longer believe that wave would take 2 years to implement now - mostly because of advances in web frameworks and web browsers. When wave was written we didn't have websockets, IE9 was quite a new browser. We've come a really long way in the last few years.
Working offline and working in a distributed setting are two different properties.
OT can work very well offline - the client and server just buffer ops and you do reconciliation. Some OT algorithms experience O(n*m) performance when the client comes back online (n client ops, m server ops), though the constant is quite low, you can make the client do the work. But you can do better - a better designed text reconciliation system can do O(nlog(n) + mlog(m)) if I remember correctly - which is quite usable in real systems and very competitive with CRDTs.)
P2P is much harder. I've got a sketch for a system that would use OT in a P2P setting, but in many ways its a poor man's CRDT. That said, the downside of CRDTs is that they grow unbounded as you make more modifications. Which would work great for documents that are written then discarded (like a HN thread). But it would work much less well for long lived, frequently written documents (like a server status dashboard). You can fix that using fancy coordination algorithms, but if you're going down that path you're back to sketching out an overcomplicated OT system.
There's lots of fun space to explore there - but not enough actual useful systems being made for production use.
Designer & author of the JSON OT algorithm that underlies ShareJS/ShareDB here. I do not have a formal proof for any of the properties of the algorithm, but we have extensively fuzzed it and are confident in its correctness. I believe a proof of correctness is possible, merely tedious.
> There is no "extent" to which CRDTs are conflict free, CRDTs are by definition always 100% conflict free.
CRDTs are always conflict-free. I am not disagreeing with that. I was trying to draw attention to the fact that just because the CRDT always commutes does not mean that a user does not perceive there to have been a conflict - out of a multiple contradictory edits the commute operation will ensure only one succeeds. So yes, the CRDT itself is conflict free, but it wasn't my point.
They aren't magic. The deal with tie breakers when they have to. I've seen posts where suggestions of building a CRDT-based source control system are being bandied around with claims that there will be no conflicts - sure, there won't be. Will the code make sense or even compile - probably not.
A conflict to a CRDT is one thing and a conflict to a user is something else entirely.
> so that with CRDTs designed explicitly for collaborative string editing you can provide perfect intent-preserving merges to the user.
I don't for a second believe this is event theoretically possible, given that if two people write collaboratively, it is not uncommon for the intent to change "mid stream" as a result of seeing the other person edit.
You are paid only in food and accommodation. This initially stuck me as terrible, but then I noticed that the company only hooks you up with startups local to where you are travelling. This is not remote work so do not expect 'back home bucks'.
The requirement for a LinkedIn page is sub-optimal. Allow a Github login plus CV, maybe?
It seems to me like an accurate reflection of reality though. When governments and corporations propose legislation in secret it is never going to be in citizen's best interests. On the national and international scale democracy almost doesn't exist. We are being governed by the rich elite and being able to vote is just a sideshow.
Democracy as it is currently implemented is fundamentally flawed because it puts politicians and political parties in power. I mean, it fundamentally is about giving other's power. That is a freaking crude proxy to furthering citizen's interests. It's a blunt instrument. People in power can be influenced/corrupted/manipulated disproportionately by corporations and others with power. Citizens are disenfranchised and mostly powerless.
IMHO the ultimate expression of democracy would not to vote others into office, but to propose and collectively edit new legislation and vote on that. Skip the politician middlemen, go straight to the issues that matter. I imagine that citizens would be allocated a number of non-transferable expiring vote-credits that they can use to spend on pushing legislation.
In summary: until the very nature of democracy evolves we are destined to inhabit a dystopian world that serves only the interests of the elite.
The basic idea of how we do democracy is more-or-less sound. Democracy is pretty robust to different implementations e.g. federal democracy, parliamentary democracy, etc.
If democracy has an Achilles's heel it is probably concentration of power. Democracy works better when power is diffuse, and you even see this expressed in the American constitution somewhat. However, although the framers of the US constitution implemented diffusion of power pretty well within government itself, they did nothing to secure diffusion of power across society more broadly[1], and as it happens that is kicking the shit out of many Western democracies now as wealth inequality (and imbalance of power, by proxy) approaches levels that have not been seen in many generations.
[1] Possibly they even did this, by restricting the vote to land owners initially (although I don't think that was their motivation to do so). There is no question limited suffrage sucks of course, but I suspect participants in American democracy early on were on a much more level playing field than what we have now. It would have been a good idea to try to preserve that diffusion of power in society somewhat, along the way to universal suffrage. We didn't, and now may be paying the price.
"I helped make Mexico, especially Tampico, safe for American oil intersts in 1914. I helped make Haiti and Cuba a decent place for the National City Bank boys to collect revenues in. I helped in the raping of half a dozen Central American republics for the benefits of Wall Street. The record of racketeering is long. I helped purify Nicaragua for the international banking house of Brown Brothers in 1909-1912. I brought light to the Dominican Republic for American sugar interests in 1916. In China I helped to see to it that Standard Oil went its way unmolested."[p. 10]
"War is a racket. ...It is the only one in which the profits are reckoned in dollars and the losses in lives." [p. 23]
"The general public shoulders the bill [for war]. This bill renders a horrible accounting. Newly placed gravestones. Mangled bodies. Shattered minds. Broken hearts and homes. Economic instability. Depression and all its attendant miseries. Back-breaking taxation for generations and generations." [p. 24]
General Butler is especially trenchant when he looks at post-war casualties. He writes with great emotion about the thousands of tramautized soldiers, many of who lose their minds and are penned like animals until they die, and he notes that in his time, returning veterans are three times more likely to die prematurely than those who stayed home.
It seems to me like an accurate reflection of reality though.
The treaty hasn't passed yet; that reality doesn't exist. We don't yet know what the future will produce and who will have what effects on how it turns out. At any rate, pessimism is probably not the most helpful contribution to the process.
At a lower layer than that (the pack files) it does use binary diffs to store similar objects as deltas to save on disk space.
TL;DR diffs play an important part in git's machinery at different levels of abstraction. They just aren't part of how it represents its domain model.