.. highlight:: python :linenothreshold: 50 .. |geq| unicode:: U+2265 .. GREATER-THAN-OR-EQUAL-TO A distributed object-transfer service ============================================================== We define an object-transfer service spanning N locations, identified by addresses 0, 1, ..., N-1. The service allows the users to share a **mutable object** (eg, integer, list, etc). A user can *acquire* the object, modify it, and *release* it when asked by the service (typically because another user wants the object). The service ensures the following: - At most one user holds the object at any time. - When a user acquires the object, its value is equal to the value it had when it was last released. - A user asking for the object eventually acquires the object provided no user holds the object indefinitely. The service differs from a distributed lock service in that the object is mutable and acquire should return the value in the last release. Also, the object ordinarily resides with a user and is in the service only when moving from one user to another. At each address ``j``, four functions are provided to the user: - ``acq()``: acquire the object. - Return ``(False,)`` only if the service is ending. Otherwise return ``(True,oval)``, indicating that the caller has acquired the object, where ``oval`` is the object's value. - Call only if the user at ``j`` does not hold the object, no ``acq()`` call is ongoing at address ``j``, and a previous ``acq()`` call at ``j`` has not returned ``(False,)``. - ``rel(oval)``: release the object with value ``oval``. - Return ``None``. - Call only if the user at ``j`` holds the object and has not called ``end()`` - ``recvreq()``: receive a request from the service to release the object. - Return ``False`` only if the service is ending. Return ``True`` only if the user at ``j`` holds the object or has an ongoing ``acq()`` call. - Call only if no ``recvreq()`` call is ongoing at address ``j`` and no previous ``recvreq()`` call at ``j`` has returned ``False``. - For every address ``k``, **messages??** received from ``k`` are in the order in which they were sent at address ``k``. Subject to this constraint, **messages??** sent to ``j`` from different addresses can be received with any interleaving. - ``end()``: Close the service. - Return ``None``. - Call only if ``end()`` has not been called at any address. Service program (abstract version) ----------------------------------------------------------------- The above service is formally defined by the *pseudo-Python* class ``DistMsgpasserService`` below (with the standard conventions applying to parameter ``j``). .. code-block:: python class DistObjtransferService(): def __init__(self, nids, initial_owner): """nids (int): number of nodes. initial_owner: node whose owner initially holds the object. objstatus: (True,oval) if obj in transit with value oval, else (False,). hasobj[j]: True iff node j's owner holds object. hasreq[j]: True iff node j's owner has a pending request. ender: id of node whose owner called end. ending: True iff end has been called. ongoing_acq[j]: True iff acq(j) call is ongoing. closed_acq[j]: True iff acq(j) call has returned (False,). ongoing_recvreq[j]: True iff recvreq(j) call is ongoing. closed_recvreq[j]: True iff recvreq(j) call has returned False. """ self.nids = nids self.initial_owner = initial_owner self.objstatus = (False,) self.hasobj = [k == initial_owner for k in range(nids)] self.hasreq = [False for k in range(nids)] self.ender = None self.ending = False self.ongoing_acq = [False for k in range(nids)] self.closed_acq = [False for k in range(nids)] self.ongoing_recvreq = [False for k in range(nids)] self.closed_recvreq = [False for k in range(nids)] input acq(self, j): # return (False,) | (True, oval) CC: 0 <= j < self.nids and not self.hasobj[j] and not self.ongoing_acq[j] and not self.closed_acq[j] CU: self.ongoing_acq[j] = True RETURN(rval): # rval is (False,) or (True, oval) RC: rval == self.objstatus and (rval != (False,) or self.ending) RU: self.ongoing_acq[j] = False self.objstatus = (False,) if rval != (False,): self.hasobj[j] = True else: self.hasobj[j] = False self.closed_acq[j] = True input rel(self, j, oval): # return None CC: 0 <= j < self.nids and self.hasobj[j] and self.hasreq[j] and self.ender != j CU: self.hasobj[j] = False self.hasreq[j] = False self.objstatus = (True, oval) RETURN(): RC: True RU: return None input recvreq(self, j): # return True | False CC: 0 <= j < self.nids and not self.ongoing_recvreq[j] and not self.closed_recvreq[j] CU: self.ongoing_recvreq[j] = True RETURN(rval): RC: (rval == False and self.ending) or # note: can return True even if no one else is asking for obj (rval == True and (self.hasobj[j] or self.ongoing_acq[j])) RU: self.hasreq[j] = rval self.ongoing_recvreq[j] = False if not rval: self.closed_recvreq[j] = True return rval input end(self, j): # return None CC: 0 <= j < self.nids and not self.ending CU: self.ending = True self.ender = j RETURN(): RC: True RU: return None Service program (concrete version) ------------------------------------------------------ TODO .. .. automodule:: sesf.objtransfer.service .. autoclass:: Service Servicetester (abstract version) -------------------------------------------- TODO Servicetester (concrete version) -------------------------------------------- .. py:module:: sesf.objtransfer.servicetester .. autoclass:: ServiceTester The tester includes an instance of class ``DistPathreversalChecker``, which checks some some assertions of the particular implementation given below. When running the tester against another implementation, comment out or replace the checker. Each node of the implementation has to be run with the following testing wrapper: .. py:module:: sesf.objtransfer.test_node .. autoclass:: TestNode Implementation ``imp_dpr`` (distributed pathreversal,uses msgtransfer service ---------------------------------------------------------------------------------------------- .. automodule:: sesf.objtransfer.imp_dpr.node .. autoclass:: Node **Checker for this implementation** The following checks some internal invariants of this distributed implementation and displays some dynamic graphs (for which it uses ``matplotlib``). It can be used in the tester when testing this implementation. .. py:module:: sesf.objtransfer.imp_dpr.checker .. autoclass:: Checker