Modify

Opened 16 years ago

Last modified 15 years ago

#180 reopened defect

Semantics of collective exchange operations

Reported by: Bernhard Haumacher (haui at haumacher dot de) Owned by:
Priority: normal Milestone: 2.0
Component: uka.karo Version: 1.08b
Severity: normal Keywords:
Cc:

Description (last modified by hauma)

The collective exchange (see ticket:177) was originally designed as pure data exchange (without touching the replicated state of the corresponding replicas). But two things might happen:

  • The exchanged data may reference parts of the replicated state (by incident).
  • The application might use the exchange operation to actively "migrate" parts of the replicated state from on rank to another by means of an exchange.

To deal with both cases, during the exchange, data that is unrelated to the replicated object is passed by value as in a regular remote method invocation, while data that was already part of the replicated object is passed by reference (by transmitting the corresponding object identifiers and resolving them on the target node to the already existing copy of the object).

This approach causes two semantic problems:

  • Exchanging references to replicated data may behave unexpected, because the exchanged data can differ on the sending and receiving side, if the replicated state is currently inconsistent (e.g. in the middle of a collective update operation). The effect is similar when passing a volatile reference from one thread to another, without ensuring that the receiver will see fresh values upon dereferencing.
  • Since an exchange operation is meant for exchanging data that is not directly related to the state of a replicated object, it is acceptable that the argument passing semantics depends on the fact, whether a referenced object is part of the replicated graph, or not. But within a temporarily inconsistent replicated object, it is not clear, which object currently belongs to the replicated state and which does not. E.g., an object that is just entered to the replicated graph in a running collective update is at the one hand already referenced form the graph, but not yet registered, because it was not yet detected by an update. Such object would be passed by value, instead of by reference. This will result in unexpected behavior.

Solution: Update before exchange

Both problems described above can be solved by preventing an exchange operation on a temporarily inconsistent replicated object. If the replicated object is in a consistent state, all ranks have a consistent view to all shared objects. Then, there does not exist a newly created object that is not yet registered at the replicated graph. The only way of preventing an exchange within an inconsistent replicated object is to perform an update before the exchange operation.

Evaluation: Non-shared objects are not registered

For performance reasons, objects that are not shared between ranks of a replicated object are not registered. If such object takes part in an exchange operation it will be passed by value regardless whether the replicated object is in a consistent state, or not. This limits the exchange operation to shared objects. An exchange may therefore not be used to share an otherwise unshared object. It depends on the application, whether this restricts the usability of the exchange operation. Ensuring that all referenced objects (shared and non-shared) are registered requires traversal of the whole replicated graph during each update and will result in prohibitive cost.

Attachments (0)

Change History (2)

comment:1 Changed 15 years ago by hauma

  • Milestone changed from 1.08b to 2.00
  • Version set to 1.08b

comment:2 Changed 15 years ago by hauma

  • Description modified (diff)
  • Resolution fixed deleted
  • Status changed from closed to reopened

It is not acceptable that an object, which is not shared but already part of the replicated state, is passed by value in an exchange operation. The result are two independent copies of the same object. These copies are no longer kept consistent.

Solution

Non-shared objects that take part in an exchange operation must be entered to the replicated state. The only way to do this without traversing the complete replicated state, is to enter all exchanged objects to the replicated state. If there are temporary objects among them, they will get garbage collected during subsequent updates.

In [2675], a test case for the behaviour of a CollectiveExchance operation was added. This test case exchanges objects that are in different relationships to the replicated state.

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as reopened The ticket will remain with no owner.
as The resolution will be set. Next status will be 'closed'.
to The owner will be changed from (none) to the specified user. Next status will be 'new'.
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.