Behaviour of concurrently created objects under the same key

After some discussion around #1, I've been thinking about what the "minimally confusing" semantics for nested maps/objects should be.

Scenario: Several users have a shared Trellis document. The current version of Trellis does not have any configuration settings, it only stores cards and their positions. However, users have been demanding customisation, and so the developers of Trellis reluctantly release a new version that supports two configuration options for customising the theme of a project: a logo, and a background colour.

User Alice installs the new release, plays around with the configuration, and configures the app to have a custom logo. The code internally does the following:

// On Alice's device
if (!trellis.root.config) trellis.root.config = {};
trellis.root.config.logo_url = "https://example.com/logo.png";

Alice then goes offline. Later, Bob comes online, also installs the app update, and also plays around with the configuration. Since Alice is not online, he doesn't receive the config change made by Alice, so in his view of the data the configuration is still empty. He sets the background colour:

// On Bob's device
if (!trellis.root.config) trellis.root.config = {};
trellis.root.config.background = "blue";

Now Alice comes back online, and the two synchronise. What should happen? It seems like the two most reasonable outcomes are:

1. The app arbitrarily picks one of the two configurations, i.e. either config: {logo_url: "https://example.com/logo.png"} or config: {background: "blue"}, and stashes away the other configuration under conflicts (where it will probably be ignored).
2. The app merges together the two sets of configurations, which works fine in this case because Alice and Bob changed two different keys in the config object: config: {background: "blue", logo_url: "https://example.com/logo.png"}.

The current behaviour of Tesseract is (1), except that Tesseract chooses behaviour (2) for the root object. That is, if you used top-level keys rather than a nested config object, Tesseract would retain both:

// On Alice's device
trellis.root.config_logo_url = "https://example.com/logo.png";

// On Bob's device
trellis.root.config_background = "blue";

// Merged outcome:
trellis.root == {config_logo_url: "https://example.com/logo.png", config_background = "blue"}

To me, this merging behaviour seems more intuitive than the choose-one-or-the-other behaviour (1), and it seems strange to treat the root object differently from nested objects, as discussed in #1. Riak also chooses this merging behaviour. However, applying this merging behaviour systematically results in some weird edge-cases, as discussed in our paper:

I am now trying to figure out what a sensible middle ground might look like. Here is an idea, and I would love to hear what you think.

I suggest that within a map, when a key is assigned an object for the first time time (that key did not previously exist), we record the fact that it was a first-time assignment. If several such first-time assignments occur concurrently, we merge the assigned objects recursively:

// On Alice's device
if (!trellis.root.config) trellis.root.config = {logo_url: "https://example.com/logo.png"};

// Concurrently, on Bob's device
if (!trellis.root.config) trellis.root.config = {background: "blue"};

// Merged outcome:
trellis.root == {config: {logo_url: "https://example.com/logo.png", background: "blue"}, ...}

However, deletions of a higher tree node take precedence over edits within the deleted subtree:

// Initially:
trellis.root == {config: {logo_url: "https://example.com/logo.png", background: "blue"}, ...}

// Alice resets to factory settings
delete trellis.root['config'];

// Concurrently, Bob changes a setting:
trellis.root.config.background = "red";

// Merged outcome, Bob's change having been lost:
trellis.root.config === undefined

Also, insertions of new objects into arrays are always independent from each other:

// Alice:
trellis.root.cards.push({title: "Collect underpants"})

// Bob:
trellis.root.cards.push({title: "Profit!"})

// Merged outcome: either
trellis.root.cards == [{title: "Collect underpants"}, {title: "Profit!"}]
// or
trellis.root.cards == [{title: "Profit!"}, {title: "Collect underpants"}]
// but never merging the two insertions

Unfortunately, merging objects may not always make sense, because the fields of an object may not be independent of each other. For example:

// Alice:
trellis.root.billing_address = {
  org: "Ink & Switch",
  city: "San Francisco",
  state: "CA",
  country: "United States"}

// Bob:
trellis.root.billing_address = {
  org: "Computer Laboratory",
  road: "15 JJ Thomson Avenue",
  city: "Cambridge",
  country: "United Kingdom"}

// Merged outcome, with two addresses nonsensically spliced together:
trellis.root.billing_address == {
  org: "Ink & Switch",
  road: "15 JJ Thomson Avenue",
  city: "San Francisco",
  state: "CA",
  country: "United Kingdom"}

Moreover, it is possible that rather than assigning a value of a single field within an object, a user may update a copy of an object and assign the entire copy. Should this be treated as equivalent to single-field assignment?

// Bob changes a setting by assigning a single field in an object
trellis.root.config.background = "red";

// Is this equivalent to updating a copy of the object?
let config = Object.assign({}, trellis.root.config);
config.background = "red";
trellis.root.config = config;

In a single-user scenario, these two ways of updating the state would be almost equivalent, but in the current Tesseract implementation the second example would overwrite any concurrent configuration updates by other users. Should assigning an object maybe examine the differences between the old and the new object, and translate the change into the assignment of only those fields that have changed?

Sorry for the rambling — I don't really know how best to resolve this, just wanted to start a discussion with a few examples. We don't have to answer it right now, but it would be good to keep this question in the back of our minds while working on Trellis, and so I thought it would be useful to have it written up.