1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
;;; 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
|
