blob: d285041f07bee9c5e4c414e4439b21ec1f64584d (
plain) (
tree)
|
|
;;; jupiter.el --- An implementation of the Jupiter algorithm
;;
;; Copyright (C) 2008, 2009 Jan Moringen
;;
;; Author: Jan Moringen <scymtym@users.sourceforge.net>
;; Keywords: rudel, jupiter, algorithm, distributed, integrity
;; X-RCS: $Id:$
;;
;; This file is part of Rudel.
;;
;; Rudel is free software: you can redistribute it and/or modify it
;; under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;;
;; Rudel is distributed in the hope that it will be useful, but
;; WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
;; General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with Rudel. If not, see <http://www.gnu.org/licenses>.
;;; Commentary:
;;
;; This file contains an implementation of the jupiter algorithm,
;; which ensures the synchronization of data shared between multiple
;; peers despite differences in network latency.
;;
;; This implementation is partly based on the implementation used in
;; the obby library <http://gobby.0x539.de/trac/>. Note, however, that
;; the details of the implementations differ.
;;; History:
;;
;; 0.1 - Initial revision.
;;; Code:
;;
(eval-when-compile
(require 'cl))
(require 'eieio)
(require 'jupiter-operation)
(require 'jupiter-insert)
(require 'jupiter-delete)
(require 'jupiter-compound)
(require 'jupiter-nop)
;;; Class jupiter-context
;;
(defclass jupiter-context ()
((local-revision :initarg :local-revision
:type (integer 0)
:initform 0
:documentation
"Revision number of the local data.")
(remote-revision :initarg :remote-revision
:type (integer 0)
:initform 0
:documentation
"Revision number of the remote data.")
(local-log :initarg :local-log
:type list
:initform nil
:documentation
"List of local operations, that have not been
acknowledged by the remote side."))
"Objects of this class store the state of one side of a
concurrent modification activity, which is synchronized using the
jupiter algorithm.")
(defmethod jupiter-local-operation ((this jupiter-context) operation)
"Store OPERATION in the operation log of THIS and increase local revision count."
(with-slots (local-revision local-log) this
(push (cons local-revision operation) local-log)
(incf local-revision)))
(defmethod jupiter-remote-operation ((this jupiter-context)
local-revision remote-revision
operation)
"Transform OPERATION with revisions LOCAL-REVISION and REMOTE-REVISION using the local operations stored in THIS.
LOCAL-REVISION is the local revision of THIS context, the remote
site is referring to."
(let ((transformed-operation operation))
(with-slots ((this-remote-revision :remote-revision)
local-log) this
;; Discard stored local operations which are older than the
;; local revision to which the remote site refers.
(setq local-log (delete-if
(lambda (revision) (< revision local-revision))
local-log
:key 'car))
;; Transform the operation
(mapc
(lambda (log-operation)
;; Transform the remote operation using the stored operation.
(setq transformed-operation
(jupiter-transform (cdr log-operation)
transformed-operation))
;; Transform the stored operation using the already
;; transformed remote operation.
(setf (cdr log-operation)
(jupiter-transform transformed-operation
(cdr log-operation))))
(reverse local-log))
;; Increase remote revision
(incf this-remote-revision))
;; The transformed operation is the result of the computation.
transformed-operation)
)
(defmethod object-print ((this jupiter-context) &rest strings)
"Add revisions and log length to string representation of THIS."
(with-slots (local-revision remote-revision local-log) this
(call-next-method
this
(format " local %d" local-revision)
(format " remote %d" remote-revision)
(format " log-items %d" (length local-log)))))
(provide 'jupiter)
;;; jupiter.el ends here
|
