git ssb

6+

Dominic / epidemic-broadcast-trees



Tree: 61537ea49c1a1f22f2d8f0ef263fdbef5f2d5e7d

Files: 61537ea49c1a1f22f2d8f0ef263fdbef5f2d5e7d / simulate.js

9355 bytesRaw
1var states = require('./state')
2var RNG = require('rng')
3var deepEqual = require('deep-equal')
4var invariants = require('./invariants')
5//state is {source, sink, nodeState, log, old_length}
6
7var events = exports.events = function (pState) {
8  var ev = []
9  //database changing state, for the peer.
10  if(pState.emit)
11    ev.push({name: 'append', peer: pState.id})
12
13  //otherwise, normal states can change,
14  //except ORDERED states are blocked by the database op.
15  for(var k in pState.connections) {
16    var cState = pState.connections[k]
17    if(!pState.emit && (cState.source.length || isMessage(cState.nodeState.effect)))
18      ev.push({name: 'ordered', peer: pState.id, connection: k})
19    if(cState.nodeState.ready != null)
20      ev.push({name: 'send', peer: pState.id, connection: k})
21    if(isNote(cState.nodeState.effect))
22      ev.push({name: 'get', peer: pState.id, connection: k})
23  }
24  return ev
25}
26
27var model2 = exports.model2 = function (pState, cState, key) {
28  /*
29    we want to handle appends (and thus validation) before handling any receives.
30    we can handle get and send in parallel though.
31
32  */
33
34  invariants(cState)
35
36  if(key === 'send') {
37    var data = cState.nodeState.ready
38    cState.sink.push(data)
39    cState.nodeState = states.read(cState.nodeState)
40  }
41  else if(key === 'get') {
42    var msg = pState.log[cState.nodeState.effect - 1] //shared
43    cState.nodeState.effect = null
44    cState.nodeState = states.gotMessage(cState.nodeState, msg)
45  }
46  else if(key == 'ordered'){
47    //can only be processed if pstate.emit is null
48    if(isMessage(cState.nodeState.effect)) {
49      pState.emit = cState.nodeState.effect
50      //pState.log.push(pState.emit) //shared
51      cState.nodeState.effect = null
52    }
53    else if(cState.source.length) {
54      var data = cState.source.shift() //connection.
55      if(data == null) throw new Error('should never read null/undefined from network')
56      cState.nodeState = (isMessage(data) ? states.receiveMessage : states.receiveNote)(cState.nodeState, data)
57    }
58    else throw new Error('should not have ran out of options')
59  }
60
61  invariants(cState)
62
63  return [pState, cState]
64}
65
66function isMessage(data) { return data && 'object' === typeof data }
67function isNote(n) { return Number.isInteger(n) }
68
69exports.peer = function peer (network, id, log) {
70  if(!log) log = []
71
72  network[id] = {
73    id: id, log: log, emit: false,
74    connections: {}
75  }
76
77  return network
78}
79
80exports.connection = function connection (network, from, to) {
81  if(!network[from]) throw new Error('from peer:'+ from + ' does not exist')
82  if(!network[to]) throw new Error('from peer:'+ to + ' does not exist')
83  var ab = [], ba = []
84  network[from].connections[to] = {
85    source: ab, sink: ba, nodeState: states.init(network[from].log.length),
86    id: from, remote: to,
87  }
88  network[to].connections[from] = {
89    source: ba, sink: ab, nodeState: states.init(network[to].log.length),
90    id: to, remote: from,
91  }
92  return network
93}
94
95exports.countConnections = function countConnections (network) {
96  //count unidirectional connections then divide by 2 to get duplex connections
97  var uniplex = 0
98  for(var k in network) {
99    uniplex += Object.keys(network[k].connections).length
100  }
101  return uniplex / 2
102}
103
104exports.isConsistent = function isConsistent (network) {
105  //this is the "handshaking lemma" if I recall
106  var keys = Object.keys(network)
107  for(var i = 0; i < keys.length; i++) {
108    var k = keys[i]
109    for(var j = i+1; j < keys.length; j++) {
110      var l = keys[j]
111      if(!deepEqual(network[k].log, network[l].log, 'peer:'+k +' is consistent with :'+j))
112        return false
113    }
114  }
115  return true
116}
117
118function allEvents (network) {
119  var evs = []
120  for(var k in network)
121    evs = evs.concat(events(network[k]))
122  return evs
123}
124
125exports.evolveNetwork = function evolveNetwork (network, msglog, seed) {
126  var eventlog = []
127  var rng = new RNG.MT(seed)
128
129  function random () {
130    return rng.random()
131  }
132
133  function randomValue(obj) {
134    var k = Object.keys(obj)
135    var rk = k[~~(random()*k.length)]
136    return obj[rk]
137  }
138
139  var evs
140  var N = 1, choice = [], base = []
141  while((evs = allEvents(network)).length) {
142    base.push(evs.length)
143    var r = ~~(evs.length*random())
144    choice.push(r)
145    N = N*evs.length + r
146
147    var event = evs[r]
148    var pState = network[event.peer]
149    eventlog.push(event)
150    if(event.name == 'append') {
151      var msg = pState.emit
152      pState.emit = null
153
154      if(msg.sequence > pState.log.length) {
155        pState.log.push(msg)
156        for(var k in pState.connections) {
157          invariants(pState.connections[k])
158          pState.connections[k].nodeState = states.appendMessage(pState.connections[k].nodeState, msg)
159          invariants(pState.connections[k])
160        }
161
162      }
163
164    }
165    else {
166      var cState = pState.connections[event.connection]
167      invariants(cState)
168
169      var s = model2(pState, cState, event.name)
170      invariants(s[1])
171      pState = s[0]; cState = s[1]; 
172      if(cState.nodeState.error) {
173        console.log(JSON.stringify(pState, null, 2))
174        console.log('evs', evs, event)
175        console.log('msglog', msglog)
176        console.log('eventlog', eventlog)
177        throw new Error('error state')
178      }
179      if(isMessage(cState.effect)) {
180        if(pState.emit) throw new Error('something already appening')
181        pState.emit = cState.effect
182        cState.effect = null
183      }
184    }
185  }
186  return network
187}
188
189
190exports.runner = function (seed, run) {
191  var tape = require('tape')
192  var max = 1000
193
194  if(seed)
195    tape('run 3 message test with 2 peers, seed:'+ (+seed), function (t) {
196      run(t, +seed)
197      t.end()
198    })
199  else
200    //running each test is O(Number of tests!)
201    tape('run 3 message test with 3 peers, seeds'+0+'-'+max, function (t) {
202      for(var i = 0; i < max; i++) (function (i) {
203        if(!(i%100)) console.log('seed:'+i)
204        try {
205        run(t, i)
206        } catch(err) {
207          console.log('error on seed:'+i)
208          throw err
209        }
210      })(i)
211      t.end()
212    })
213
214}
215
216//test 3 peers fully connected, so that some messages get sent twice
217//these connections should get turned off.
218
219function createLogs(n) {
220  var log = []
221  for(var i = 0; i < n; i++)
222    log.push({author: 'a', sequence: i+1, content: 'hi:'+i.toString(36)})
223  return log
224}
225
226function createPeers(network, N) {
227  for(var i = 0; i < N; i++) {
228    var id = String.fromCharCode('A'.charCodeAt(0) + i)
229    network = exports.peer(network, id, [])
230  }
231  return network
232}
233
234function createConnections (network, list) {
235  list.split(',').map(function (ab) {
236    if(ab)
237      network = exports.connection(network, ab[0], ab[1])
238  })
239  return network
240}
241
242
243var letters = 'abcdefghijklmnopqrstuzwxyz'.toUpperCase()
244//create random network with N nodes and E edges
245exports.createRandomNetwork = function createRandomNetwork(N, E, seed) {
246
247  if(E < N -1) throw new Error(
248    'not enough edges:'+E+
249    ' to connect a network with:'+N +' nodes. '+
250    'At least '+N-1+' are required.'
251  )
252
253  var rng = new RNG.MT(seed)
254
255  function random() {
256    return rng.random()
257  }
258  var network = {}
259  network = exports.peer(network, 'A')
260
261  //create N-1 more peers
262  //connect them randomly (but gaurantee a connected graph)
263  for(var i = 1; i < N; i++) {
264    var me = letters[i]
265    network = exports.peer(network, me, [])
266    //at least one connection to a peer currently in the network, gaurantees a connected network.
267    network = exports.connection(network, me, letters[~~((i-1)*random())])
268  }
269
270  for(var i = 0; i < E-N; i++) {
271    var me = letters[i%N]
272    var other
273    while(me == (other = letters[~~(random()*N)]))
274      ;
275    network = exports.connection(network, me, other)
276  }
277
278  return network
279}
280
281exports.createSimulation = function (M, N, C) {
282  var network = {}
283  var a_log =  createLogs(M)
284  network = createPeers(network, N)
285  network.A.log = a_log //first peer is always alice
286  return createConnections(network, C)
287}
288
289//run a test with M messages over N peers, returning 
290exports.basic = function (createNetwork) {
291  return function (t, seed) {
292    var msglog = []
293
294    var network = createNetwork(seed)
295
296    network = exports.evolveNetwork(network, msglog, seed)
297
298    if(!exports.isConsistent(network))
299      throw new Error('network not consistent')
300
301    //add one more item to A's log
302
303    network.A.emit = {author: 'a', sequence: network.A.log.length+1, content: 'LIVE'}
304
305    network = exports.evolveNetwork(network, msglog, seed*2)
306    if(!exports.isConsistent(network))
307      throw new Error('network not consistent')
308    //todo: make this a processable event log thing
309    network.A.emit = {author: 'a', sequence: network.A.log.length+1, content: 'LIVE'}
310
311    network = exports.evolveNetwork(network, msglog, seed*2)
312    if(!exports.isConsistent(network))
313      throw new Error('network not consistent')
314
315    return msglog
316  }
317}
318
319function print_network (network) {
320  for(var k in network) {
321    var s = k + ': '
322    for(var j in network) {
323      s += k == j ? ' ' : network[k].connections[j] ? j : '.'
324    }
325    console.log(s)
326  }
327}
328
329function isConnected (network) {
330  var reach = {}
331  ;(function search (k) {
332    reach[k] = true
333    for(var j in network[k].connections)
334      if(!reach[j]) search(j)
335  }(Object.keys(network)[0]))
336
337  return Object.keys(network).length === Object.keys(reach).length
338}
339
340

Built with git-ssb-web