131–140 of 154 posts
Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
> (But don't be alarmed if this looks confusing - we could probably fit everyone on the planet who understands this code today into a small meeting room.)
and the follow up reading confirm what I believed about this code
should I be worried about myself ?
Earlier quoted context omitted.
I must say that when it comes to discrete optimization, the genetic/ant/simulated annealing/etc. stuff is more popular in academia than in industry (at least the industry that doesn't heavily include academics). Works like Lin-Kernighan heuristic are extremely rare and a bunch of knowledge exists in industry only. Even the mentioned heuristic was for decades being implemented incorrectly until one individual came and…
Do you have any links for efficient ways to handle time window constraints etc ?
Earlier quoted context omitted.
> Even the mentioned heuristic was for decades being implemented incorrectly until one individual came and demonstrated its superiority (K. Helsgaun). Does this mean that the Linkern program in the Concorde TSP suite is also implemented incorrectly?
Concorde is fine. The LK heuristic was published in 1973. After that, until the mid 90s, no one could outperform the original published results with the same heuristic.
BTW, in your opinion, is there any readable text on the LK algorithm? I'm afraid that all I've read so far seems to be suffering from this problem. I have a very specific optimization need that doesn't seem be covered even by LKH-3 (it seems to be that my problem could be treated either as asymmetric TSP with time windows on a small number nodes and a non-metric distance matrix, or alternatively from the other side as VRP with asymmetric distances, unknown number of vehicles, and bounded trip duration for every vehicle, but either of the two needs an additional constraint that all vehicle trips should get close to the number of working hours within a day with the exception of one trip which can be shorter - basically I need an "ATSP with sleeping breaks") so I may need to roll out my own implementation of something and for an outsider, there doesn't seem to be a good text on implementing these things realistically without having some prior knowledge already.
Earlier quoted context omitted.
Hi josephg, I'm a CRDT researcher. This is great to see so much work around CRDT nowadays! Some optimizations whom you discuss are already proposed by some papers and implementations. For instance, LogootSplit [1] proposes an implementation based on an AVL tree with extra metadatas to get a range tree. LogootSplit proposes also a block-wise approach that stores strings instead of individual characters. Xray [2], an e…
Cool! It'd be interesting to see those CRDT implementations added to Kevin Jahns' CRDT Benchmarks page[1]. The LogootSplit paper looks interesting. It looks like xray is abandoned, and I'm not sure about teletype. Though teletype's CRDT looks to be entirely implemented in javascript[2]? If the authors are around I'd love to see some benchmarks so we can compare approaches and learn what actually works well. And I'm n…
I've followed your work for a longtime (since chipmunk-js days), and that is a very honest self assessment
Earlier quoted context omitted.
In computer science the first author does the work and is usually a PhD student. The last author is usually the professor that pushed and helped develop the idea, provided funding, and probably wrote or was heavily involved in writing the paper’s abstract, intro and conclusion sections — the bulk of “framing” the work. But there are exceptions. Some profs are less student-oriented or don’t like delegating so much, an…
In a lot of math disciplines, the papers follow the Hardy-Littlewood rule, so the author names are ordered alphabetically [1]. Maybe, that's what you've been noticing. In my area (programming languages, which may be sometimes theoretical but it's mostly a mixed bag), I noticed only one group follow that convention. Others follow the "first author is the main contributor, last author is the advisor" convention you des…
This is very interesting to me. CRDTs for databases sounds fantastic. Databases have much much richer data types and transactional semantics than collaborative text editing, and this makes applying CRDTs to databases harder.
Let's start with the basics. CRDTs are all about designing or picking monoids that fit the problem and allow one to get a very good approximation of the semantics one is after, if not even exactly.
What does that mean for databases? Well, for one, every data type in a database will have to have a monoid associated with it -- this is... limiting, but limiting is good if the benefit is that we don't need any more complex mechanisms to get convergence in a distributed database. For example, we can have a table of "likes" where they can only increase additively, so we'll make that BIGINT with the ADDITIVE monoid or whatever. But `BIGINT with the ADDITIVE monoid` is the easy stuff. The hard part is PRIMARY and UNIQUE KEYs.
So what about unique keys? Well, we can have monoids for those too. Like tiebreakers based on timestamps. Especially since we have delineated transactions (BEGIN; ..; COMMIT;) we know that if some INSERT fails eventually then the whole transaction containing it fails (unless that INSERT is of the OR IGNORE / ON CONFLICT DO NOTHING variety).
The real problem with CRDT and databases is that CRDT is incompatible with SQL transactional semantics. Similarly for CRDT and filesystems and POSIX semantics. You can't tell if some transaction will commit successfully until you've heard from all collaborators enough to know that it must have. Instead you can consider every local transaction that succeeds locally as committed, but then later every possible conflict has to be resolvable in some way. This gets tricky real fast. It might be easier to start with "trivial" transactions like POSIX file rename(2). If two applications decide to rename the same file to different names, and both observe success, and eventually only one of those renames succeeds, then it has to appear to the loser that the winner came along and renamed the file after the loser did. This sequence of events:
loser winner
----- ------
rename("/a/b", "/a/c") = 0
rename("/a/b", "/a/d") = 0
loser winner
----- ------
rename("/a/b", "/a/c") = 0
rename("/a/c", "/a/d") = 0
^
|
/
note the difference --+
Similarly for O_CREAT | O_EXCL: the loser can imagine that the winner unlinked the file created by the loser then created a replacement. Again, we've left the land of POSIX at that point, but again, it can be a pretty good compromise for some applications.
SQL transactions are infinitely more complex than POSIX ones, but I think the analysis of the POSIX case generalizes to SQL ACID transactional semantics: you can't quite have that with CRDT. You might find more of some successful-looking-to-you transaction undone or changed later by a collaborator's in ways that, if you were to look at the actual events, you'd be annoyed violate ACID. And again, for some applications this probably just won't work. Though, too, we might come up with monoids that help us reach acceptable semantics.
For example, in Active Directory each domain controller gets its own pool of RIDs (relative identifiers) for assignment to new users and groups and machine accounts, so there can be no conflicts about those, but there is no sub-namespacing of the names of those things, so the rule AD uses is that the loser's user/group/namespace gets renamed to something like "copy_of_{original_name}". Also, AD requires a strong primary role for the DC that hands out RID ranges for allocation, which again means we're leaving the land of CRDT for some things. So in AD one might find a user/group/machine unexpectedly renamed like that (but it rarely ever happens).
But if the application was using atomic transactions to decide whether to have destructive external side-effects, such as "sell!!!", "launch missiles", etc., then this kind of shifting sands transactional semantics may be... unsatisfying.
CRDT resembles eventual correctness in a way. It's not that local state is ever incorrect, but that a sequence of events is impossible in a system with traditional ACID transactional semantics.
All this said, just note that I've done zero work in this area, just lots of thinking. I've this idea that one could use PG logical replication publications and subscriptions, and monoid choices encoded in COMMENTs, and suitable functions, to implement a CRDT scheme on top of PG to explore this space. Basically, each collaborating server publishes its view of a log of local transactions and subscribes to all the others' (in separate schemas), then periodically it applies the others' logs to the local source of truth. For simple applications that might even suffice instead of a database that natively supports CRDT. I have done work on encoding useful schema metadata in COMMENTs using JSON, so I'm pretty confident that this is something worth exploring.
One thing that is clear is that some of this space has been explored already. For example, again, AD has done so for PRIMARY/UNIQUE KEYs! Indeed, AD even implements a hybrid approach to multi-mastering a distributed database, with an "infrastructure master" for some things, and CRDT for others. AD's metaschema is LDAP's, with some enhancements (especially an ObjectDN syntax for "relations" or "pointers") that make it a lot more like a relational database. And AD is a general purpose database that achieves these things. So it's not like this space is completely new -- there are a few giants' shoulders to stand on.
I think this data structure is usually called a Counted B-tree https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtr... instead of range tree
What's common to xi's approach and TFA's is monoids. Monoids are at the heart of CRDT.
Earlier quoted context omitted.
Do you want a centralized server to control the data? Then just use OT. Do you want users to control the data, and have your server essentially just be a forever-present user? Then use CRDT. CRDTs certainly do have a mathematical elegance to them.
Yep, this is the best practical advice at the moment. Well, for list CRDTs. State CRDTs (like a counter) are small and fast, and kinda better than OT in every way. List ("operation based") CRDTs and OT systems are "equivalent" in a very academic sense that nobody really talks about or understands. Its really not obvious unless you've been staring at this stuff for years but the equivalence is there: You can make a CR…
Could you clarify what you mean? Assuming your CRDT is defined in terms of "operations" that contain (at minimum) an identifier+sequence tuple, zero or more references to other operations, and a value (as they are in this article) then there's no reason why you couldn't just ship a batch of individual operations to other clients when something changes rather than the whole state, since each operation is defined in absolute terms.
In other words, if you start with [A4="a", B2="b", B3="c", B1="d", A5="e"] at site A, and it gets turned into [A4="a", B2="b", B4="f", B3="c", B1="d", A5="e"] following a change from B, you can ship something like B4="f"->B2 to C as long as C's CRDT has synced up to version vector A5|B3. (And if it hasn't synced up yet, and you're not using a transport with causal delivery guarantees, the change could be cached at C until its dependencies have arrived.)
I don't think there's any need to transition to an OT system or to add renames in order to get this delta-shipping benefit: all the data you need is already there, unless I'm missing something. (But maybe you're describing something else?)
Earlier quoted context omitted.
Thanks for ShareDB. It’s dope. I extended it to support collaborative voxel editing ( https://jel.app ) and works great.
Oh that’s cool!! Did you use json-ot for that? I haven’t touched that code in years and it’s delightful people are actively maintaining it and using it to make cool stuff.
Earlier quoted context omitted.
Problem is that academics are rarely experts at programming or have knowledge of computer architectures as much as someone in the industry. There are various tricks that are never taught at college, therefore academics have no idea some stuff even exists. Best example is discrete optimization research (traveling salesman, vehicle routing and its variants, schedule rostering etc.). Stuff you find in the papers there a…
You do realize there is a whole area of the research field dedicated for heuristic algorithms? They have a proper academic basis just as much as the “correct” solutions.