15.2.8. An alternative way to pass on
In the chapter “A synchronisation principle: passing on” I describe in conceptual terms an algorithm to make sure a particular delta reaches all concerned peers (peers that have the modified structural element in one of their perspectives). Here I present an alternative algorithm that may be easier to implement.
15.2.8.1. Overview
Let’s start with the user who makes a change (the Initiator). He will send a transaction consisting of deltas. To implement the algorithm, these deltas must be augmented with two elements:
-
The user types with a perspective on the structural element that has been changed (AllUsersWithAPerspective)
-
The difference between that set and those types that the Initiator has a perspective on (ToBeInformed). These are types whose instances the Initiator cannot reach.
Now consider a peer receiving such a transaction. He will carry out the change described by each delta, so his database is in sync with that of the sender. Next, he’ll compute all user types he has a perspective on and
-
Compute its union with ToBeInformed and
-
Subtract it from ToBeInformed, to form RemainingToBeInformed.
For the first set, he computes the user instances known to him. For them he creates a personal transaction and adds this particular delta to it, after replacing the element ToBeInformed with RemainingToBeInformed.
When all incoming deltas have been handled in this way, he will send the personal transactions that have been built in the process to their respective recipients.
This algorithm will make sure that no user receives the same delta twice and it guarantees that all users receive the deltas they need.
15.2.8.2. Some implementation details
Computing the set of user types connected to a particular user type
This algorithm requires all users to compute the users they have a perspective on, quite often. It seems worthwhile to compute this graph once during the processing of the model source file and save it with the DomeinFile. We compute this graph for the entire model, rather than per context, because when we deal with a particular change, users outside the context may have an (implicit) perspective on it.
We start with the perspectives stated explicitly in the model source text. These form the base of the UserGraph.
Calculated User Rule. For the next step, realize that some user roles having a perspective may be calculated. We compute the extension (in terms of Enumerated Roles) for such a user role and add them to the graph. We then connect all these new roles to the same targets as the original Calculated User Role.
Inverted Calculated User Rule. The user role that a perspective is on, may be calculated, too. Like above, we add to the graph all Enumerated Roles that form the extension of the Calculated target and we connect the user having the perspective with all of them.
Filler Rule. An Enumerated User Role U1 that is filled with another User Role F1, gives rise to even more connections. If U1 has a perspective on U2, its filler F1 should be connected in the UserGraph, too. It’s not that the filler has the same perspective; but we know that F1 ‘can see’ U2.
Inverted Filler Rule. An Enumerated User Role F1 that has a perspective on another user role U2, will be connected in the UserGraph with an arrow. But then a user role U1 that is filled by F1 may be connected to U2 as well. After all, U1 and F1 represent the same user (or installation) and the UserGraph shows connections between users.
Computing user types for a delta
For any given delta, we have to compute all user types with a perspective on that type. Notice that because a user role may have a perspective on a calculated role, not only the end results of such calculations are in scope for him, but all intermediate steps are so, too. How to compute them?
This is where inverted queries come to the rescue. We have established, while processing a model source text, an inverted query on each element a user can ‘see’ by force of a perspective. So, starting with the type of a structural element, we can read off all user types that have it in scope.
These user types are contained in the newtype InvertedQuery. We use this type to compute users instances that should receive a particular delta. To implement this algorithm, we should add some code to collect the user type from all inverted queries at a particular role- or property type and then add them to the delta’s constructed for the modification.
Optimization by a refinement
What if there are more than one user instances for a particular type? All of them would carry out the above algorithm, duplicating work and moreover burdening peers with double work too, if they have something to pass on.
We can avoid that by having the Initiator select a single instance of each type at random and only send him a delta with a non-empty ToBeInformed. The others receive a delta with an empty ToBeInformed. Subsequently, each peer that receives the delta does the same. This guarantees that for each user type, just a single instance will pass the delta on to types that could not have been reached before.