-
Notifications
You must be signed in to change notification settings - Fork 0
/
specification.proto
625 lines (544 loc) · 32.4 KB
/
specification.proto
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
syntax = "proto3";
package Proto; // You can change the package name to anything you like
/*
app Custom-made application
uc UniformConsensus Leader-Driven 5.7 225
ep EpochConsensus Read/Write Epoch 5.6 223
ec EpochChange Leader-Based 5.5 219
nnar (N,N) Atomic Register Read-Impose Write-Consult-Majority 4.10 168
4.11 169
beb BestEffortBroadcast Basic 3.1 76
eld EventualLeaderDetector Monarchical Eventual Leader Detector 2.8 57
epfd EventuallyPerfectFailureDetector Increasing Timeout 2.7 55
pl PerfectLink (use TCP)
AbstractionIds
+--+-------+------ app -------+ +--+-------+------ app -------+ = app
| | | | | | | |
| | | +- uc,uc -+ | | | +- uc,uc -+ = app.uc[topic]
| | nnar,nnar | | | | nnar,nnar | | = app.nnar[register]
| | | | +---- ec --+ | | | | | +---- ec --+ | = app.uc[topic].ec
| | | | | | | ep,ep,ep | | | | | | | ep,ep,ep = app.uc[topic].ep[0], app.uc[topic].ep[1],
| | | | | | | | | | | | | | | | | | app.uc[topic].ep[2], ...
| | | | eld | | | | | | | | eld | | | | = app.uc[topic].ec.eld
| | | | epfd | | | | | | | | epfd | | | | = app.uc[topic].ec.eld.epfd
| beb beb | | beb | beb | | beb beb | | beb | beb | = app.beb, app.nnar[register].beb, uc[topic].ec.beb
pl pl pl pl pl pl pl pl pl pl pl pl pl pl pl pl pl pl = app.pl, app.beb.pl, app.nnar[register].beb.pl, app.nnar[register].pl,
| | | | | | | | | | | | | | | | | | app.uc[topic].ec.eld.epfd.pl, app.uc[topic].ec.beb.pl,
| | | | | | | | | osproc osproc | | | | | | | | | app.uc[topic].ec.pl, app.uc[topic].ep[0].pl,
| | | | | | | | | | | | | | | | | | | | app.uc[topic].ep[1].pl, app.uc[topic].ep[2].pl, ...
+--+----- +-+------+-----+----+----+--+----- NETWORK ------+--+------+-+------+-----+----+----+--+
| |
| pl
| |
hub
1. The communication is done using the Google Protobuffer 3.x messages defined below, over TCP. The exchange will be
asynchronous. When sending a request/response, open the TCP connection, send the message, then close the connection.
When listening for requests, get the request, then close the socket.
2. The system consists of several processes and one hub. The processes are implementation of what the textbook refers
to as a process, with the extension that they can participate in multiple systems. They should be able to route
messages and events separately for each system that the process is involved into.
3. The hub is responsible of informing the processes of the system(s) they belong to, trigger algorithms, and receive
notifications that it can use to validate the functionality.
4. Your job is to implement a process that can run the algorithms shown in the evaluation flow below. Use the reference
binaries provided by your instructor to verify your implementation
5. Process referencing: Upon starting, a process will connect to the hub and register sending: owner alias, process
index, process host, process listening port (see ProcRegistration). The hub address and port will be configured manually.
6. The evaluation will be done as follows:
- Share your screen with the instructor
- Start the reference hub and processes along with 3 processes of your implementation
# HUB HOST + PORT PROCESSES HOST + PORTS
> dalgs.exe 127.0.0.1 5000 127.0.0.1 5001 5002 5003
May 18 12:17:01.474 INF Hub listening on 127.0.0.1:5000
May 18 12:17:01.475 INF ref-2: listening on 127.0.0.1:5002
May 18 12:17:01.475 INF ref-3: listening on 127.0.0.1:5003
May 18 12:17:01.475 INF ref-1: listening on 127.0.0.1:5001
May 18 12:17:11.475 INF abc-2: listening on 127.0.0.1:5005
May 18 12:17:11.475 INF abc-3: listening on 127.0.0.1:5006
May 18 12:17:11.475 INF abc-1: listening on 127.0.0.1:5004
- Process-level messages exchanged in this phase
- Every process sends Message(NetworkMessage(Message(ProcRegistration))) to the Hub
- Assuming your process owner is "abc", here is a walk-through what you can do at the command prompt
dalgs> help
Commands:
log [info|debug|trace] - set logging level
quit - quit the program
help - show usage
list - list the nodes (hub only)
init owner1 owner2 ... - initialize system with owners nodes (hub only)
consensus topic - test consensus on topic (hub only)
wait N - wait N seconds (hub only) dalgs> log info
dalgs> list
+---+-------+-----------+--------+--------+--------+
| # | OWNER | HOST | PORT 1 | PORT 2 | PORT 3 |
+---+-------+-----------+--------+--------+--------+
| 1 | ref | 127.0.0.1 | 5001 | 5002 | 5003 |
+---+-------+-----------+--------+--------+--------+
| 2 | abc | 127.0.0.1 | 5004 | 5005 | 5006 |
+---+-------+-----------+--------+--------+--------+
dalgs> log info
- Create a system
dalgs> system ref abc
09:40:39.910 INF Starting system sys-1 of process ref-1 ...
09:40:39.911 INF Starting system sys-1 of process ref-2 ...
09:40:39.913 INF Starting system sys-1 of process ref-3 ...
09:40:39.913 INF Starting system sys-1 of process ref-3 ...
09:40:39.913 INF Starting system sys-1 of process abc-1 ...
09:40:39.913 INF Starting system sys-1 of process abc-2 ...
09:40:39.913 INF Starting system sys-1 of process abc-3 ...
- Process-level messages exchanged in this phase
- Hub sends Message(NetworkMessage(Message(ProcDestroySystem))) to all the processes of the existing system (if there is an existing system)
- Hub sends Message(NetworkMessage(Message(ProcInitializeSystem))) to ref-1, ref-2, ref-3, abc-1, abc-2, abc-3
- Launch BEB
dalgs> broadcast abc-2 52
09:41:50.854 INF sys-1/abc-3 delivered 52
09:41:50.855 INF sys-1/abc-1 delivered 52
09:41:50.886 INF sys-1/ref-3 delivered 52
09:41:50.886 INF sys-1/abc-2 delivered 52
09:41:50.886 INF sys-1/ref-2 delivered 52
09:41:50.922 INF sys-1/ref-1 delivered 52
- App-level messages exchanged in this phase
- Hub sends Message(NetworkMessage(Message(AppBroadcast(52)))) to abc-2
- Hub expects Message(NetworkMessage(Message(AppValue(52)))) from all processes
- Register write read
dalgs> write x 89 abc-2
14:50:26.465 INF sys-1/ref-2: Registering unknown abstraction app.nnar[x].beb.pl
14:50:26.465 INF sys-1/ref-1: Registering unknown abstraction app.nnar[x].beb.pl
14:50:26.467 INF sys-1/ref-3: Registering unknown abstraction app.nnar[x].beb.pl
14:50:26.566 INF hub: sys-1/abc-2 finished writing x
- App-level messages exchanged in this phase
- Hub sends Message(NetworkMessage(Message(AppWrite(x, 89)))) to abc-2
- Hub expects Message(NetworkMessage(Message(AppWriteReturn(x)))) from all processes
dalgs> read x
INFO: No process name(s) provided. Triggering all processes
14:50:35.678 INF hub: sys-1/abc-2 read x=89
14:50:35.678 INF hub: sys-1/abc-1 read x=89
14:50:35.679 INF hub: sys-1/ref-1 read x=89
14:50:35.679 INF hub: sys-1/abc-3 read x=89
14:50:35.707 INF hub: sys-1/ref-2 read x=89
14:50:35.707 INF hub: sys-1/ref-3 read x=89
- App-level messages exchanged in this phase
- Hub sends Message(NetworkMessage(Message(AppRead(x)))) to all processes
- Hub expects Message(NetworkMessage(Message(AppReadReturn(x, 89)))) from all processes
- Register read/write storm
dalgs> storm w # a lot of reads and writes involving all processes
15:00:21.023 INF sys-1/ref-3: Registering unknown abstraction app.nnar[w].beb.pl
15:00:21.025 INF sys-1/ref-2: Registering unknown abstraction app.nnar[w].beb.pl
15:00:21.057 INF hub: sys-1/abc-1 finished writing w
15:00:21.062 INF hub: sys-1/abc-2 finished writing w
15:00:21.070 INF hub: sys-1/ref-1 finished writing w
15:00:21.073 INF hub: sys-1/abc-3 finished writing w
15:00:21.077 INF hub: sys-1/ref-2 finished writing w
15:00:21.080 INF hub: sys-1/ref-3 finished writing w
15:00:21.097 INF hub: sys-1/abc-1 read w=44
15:00:21.114 INF hub: sys-1/abc-2 read w=44
15:00:21.115 INF hub: sys-1/ref-1 finished writing w
15:00:21.123 INF hub: sys-1/abc-3 read w=44
15:00:21.125 INF hub: sys-1/ref-3 finished writing w
15:00:21.127 INF hub: sys-1/ref-2 finished writing w
15:00:21.154 INF hub: sys-1/abc-1 finished writing w
15:00:21.164 INF hub: sys-1/ref-1 read w=77
15:00:21.169 INF hub: sys-1/abc-2 finished writing w
15:00:21.174 INF hub: sys-1/ref-2 read w=85
15:00:21.174 INF hub: sys-1/abc-3 finished writing w
15:00:21.176 INF hub: sys-1/ref-3 read w=85
15:00:21.203 INF hub: sys-1/abc-1 read w=55
15:00:21.211 INF hub: sys-1/ref-1 read w=55
15:00:21.218 INF hub: sys-1/abc-2 read w=55
15:00:21.240 INF hub: sys-1/ref-2 read w=55
15:00:21.252 INF hub: sys-1/ref-3 read w=55
15:00:21.246 INF hub: sys-1/abc-3 read w=55
- Try to linearize the register operations. You will not be able to always do this due to the differences between
the actual operation start/end moments, and those recorded by the hub upon notification
dalgs> lin w
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
abc-1: wwwwww44wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwww85wwwwwwwwwwwwwwww rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrrrr
abc-2: wwwwwwww61wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwww42wwwwwwwwwwwwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
abc-3: wwwwwwwwwwww78wwwwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwww55wwwwwwwwwwwwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-1: wwwwwwwwwwww15wwwwwwwwww wwwwwwwwwwwwwwww77wwwwwwwwwwwwwwww rrrrrrrrrrrrrr77rrrrrrrrrrrr rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-2: wwwwwwwwwwwwwwww92wwwwwwwwwwwwww wwwwwwwwwwwwwwwwwwww28wwwwwwwwwwwwwwwwww rrrrrrrrrr85rrrrrrrrrr rrrrrrrrrrrrrr55rrrrrrrrrrrr
ref-3: wwwwwwwwwwwwwwww76wwwwwwwwwwwwwwww wwwwwwwwwwwwww72wwwwwwwwwwww rrrrrrrrrrrrrrrrrrrr85rrrrrrrrrrrrrrrrrr rrrrrrrrrr55rrrrrrrr
The execution is not atomic
dalgs.linearize> write 55 after 51 # Collapse all the reads with value 55 on or after moment 51
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
abc-1: wwwwww44wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwww85wwwwwwwwwwwwwwww rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrrrr
abc-2: wwwwwwww61wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwww42wwwwwwwwwwwwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
abc-3: wwwwwwwwwwww78wwwwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww55wwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-1: wwwwwwwwwwww15wwwwwwwwww wwwwwwwwwwwwwwww77wwwwwwwwwwwwwwww rrrrrrrrrrrrrr77rrrrrrrrrrrr rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-2: wwwwwwwwwwwwwwww92wwwwwwwwwwwwww wwwwwwwwwwwwwwwwwwww28wwwwwwwwwwwwwwwwww rrrrrrrrrr85rrrrrrrrrr rrrrrrrrrrrrrr55rrrrrrrrrrrr
ref-3: wwwwwwwwwwwwwwww76wwwwwwwwwwwwwwww wwwwwwwwwwwwww72wwwwwwwwwwww rrrrrrrrrrrrrrrrrrrr85rrrrrrrrrrrrrrrrrr rrrrrrrrrr55rrrrrrrr
The execution is not atomic
dalgs.linearize> write 85 after 42
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
abc-1: wwwwww44wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww85ww rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrrrr
abc-2: wwwwwwww61wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwww42wwwwwwwwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
abc-3: wwwwwwwwwwww78wwwwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww55wwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-1: wwwwwwwwwwww15wwwwwwwwww wwwwwwwwwwwwwwww77wwwwwwwwwwwwwwww rrrrrrrrrrrrrr77rrrrrrrrrrrr rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-2: wwwwwwwwwwwwwwww92wwwwwwwwwwwwww wwwwwwwwwwwwwwwwwwww28wwwwwwwwwwwwwwwwww rrrrrrrrrr85rrrrrrrrrr rrrrrrrrrrrrrr55rrrrrrrrrrrr
ref-3: wwwwwwwwwwwwwwww76wwwwwwwwwwwwwwww wwwwwwwwwwwwww72wwwwwwwwwwww rrrrrrrrrrrrrrrrrrrr85rrrrrrrrrrrrrrrrrr rrrrrrrrrr55rrrrrrrr
The execution is not atomic
dalgs.linearize> write 42 28 72 before 30
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
abc-1: wwwwww44wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww85ww rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrrrr
abc-2: wwwwwwww61wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr 42wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
abc-3: wwwwwwwwwwww78wwwwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww55wwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-1: wwwwwwwwwwww15wwwwwwwwww wwwwwwwwwwwwwwww77wwwwwwwwwwwwwwww rrrrrrrrrrrrrr77rrrrrrrrrrrr rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-2: wwwwwwwwwwwwwwww92wwwwwwwwwwwwww wwwwwwwwwwwwwwwwww28wwwwwwwwwwwwwwwwwwww rrrrrrrrrr85rrrrrrrrrr rrrrrrrrrrrrrr55rrrrrrrrrrrr
ref-3: wwwwwwwwwwwwwwww76wwwwwwwwwwwwwwww wwwwwwwwwwww72wwwwwwwwwwwwww rrrrrrrrrrrrrrrrrrrr85rrrrrrrrrrrrrrrrrr rrrrrrrrrr55rrrrrrrr
The execution is not atomic
dalgs.linearize> write 77 after 31
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
abc-1: wwwwww44wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww85ww rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrrrr
abc-2: wwwwwwww61wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr 42wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
abc-3: wwwwwwwwwwww78wwwwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww55wwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-1: wwwwwwwwwwww15wwwwwwwwww wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww77 rrrrrrrrrrrrrr77rrrrrrrrrrrr rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-2: wwwwwwwwwwwwwwww92wwwwwwwwwwwwww wwwwwwwwwwwwwwwwww28wwwwwwwwwwwwwwwwwwww rrrrrrrrrr85rrrrrrrrrr rrrrrrrrrrrrrr55rrrrrrrrrrrr
ref-3: wwwwwwwwwwwwwwww76wwwwwwwwwwwwwwww wwwwwwwwwwww72wwwwwwwwwwwwww rrrrrrrrrrrrrrrrrrrr85rrrrrrrrrrrrrrrrrr rrrrrrrrrr55rrrrrrrr
The execution is not atomic
dalgs.linearize> write 61 78 15 92 76 before 6
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
abc-1: wwwwww44wwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww85ww rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrrrr
abc-2: wwwwww61wwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr 42wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
abc-3: ww78wwwwwwwwwwwwwwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww55wwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-1: wwwwwwww15wwwwwwwwwwwwww wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww77 rrrrrrrrrrrrrr77rrrrrrrrrrrr rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-2: wwww92wwwwwwwwwwwwwwwwwwwwwwwwww wwwwwwwwwwwwwwwwww28wwwwwwwwwwwwwwwwwwww rrrrrrrrrr85rrrrrrrrrr rrrrrrrrrrrrrr55rrrrrrrrrrrr
ref-3: 76wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww wwwwwwwwwwww72wwwwwwwwwwwwww rrrrrrrrrrrrrrrrrrrr85rrrrrrrrrrrrrrrrrr rrrrrrrrrr55rrrrrrrr
The execution is not atomic
dalgs.linearize> write 44 after 7
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
abc-1: wwwwwwwwwwww44 rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww85ww rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrrrr
abc-2: wwwwww61wwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr 42wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
abc-3: ww78wwwwwwwwwwwwwwwwwwww rrrrrrrrrrrrrrrr44rrrrrrrrrrrrrrrr wwwwwwwwwwwwwwwwwwwwwwwwwwwwww55wwwwwwww rrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-1: wwwwwwww15wwwwwwwwwwwwww wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww77 rrrrrrrrrrrrrr77rrrrrrrrrrrr rrrrrrrrrrrrrrrr55rrrrrrrrrrrrrr
ref-2: wwww92wwwwwwwwwwwwwwwwwwwwwwwwww wwwwwwwwwwwwwwwwww28wwwwwwwwwwwwwwwwwwww rrrrrrrrrr85rrrrrrrrrr rrrrrrrrrrrrrr55rrrrrrrrrrrr
ref-3: 76wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww wwwwwwwwwwww72wwwwwwwwwwwwww rrrrrrrrrrrrrrrrrrrr85rrrrrrrrrrrrrrrrrr rrrrrrrrrr55rrrrrrrr
The execution is atomic
dalgs.linearize> done
- Launch consensus on a topic
dalgs> consensus mytopic
INFO: sys-1/abc-1 will propose 89
INFO: sys-1/ref-1 will propose 85
INFO: sys-1/abc-2 will propose 85
INFO: sys-1/ref-2 will propose 47
INFO: sys-1/abc-3 will propose 52
INFO: sys-1/ref-3 will propose 37
09:42:45.310 INF sys-1/abc-2 decided 37
09:42:45.342 INF sys-1/ref-2 decided 37
09:42:45.343 INF sys-1/ref-3 decided 37
09:42:45.344 INF sys-1/abc-3 decided 37
09:42:45.353 INF sys-1/ref-1 decided 37
09:42:45.356 INF sys-1/abc-1 decided 37
- App-level messages exchanged in this phase
- Hub sends Message(NetworkMessage(Message(AppPropose(mytopic, randomValue)))) to all processes
- Hub expects Message(NetworkMessage(Message(AppDecided(mytopic, decidedValue)))) from all processes
dalgs> quit
09:43:49.028 INF Stopping process ref-1 ...
09:43:49.030 WRN Unexpected message type EPFD_INTERNAL_HEARTBEAT_REQUEST for unknown system sys-1
09:43:49.031 INF Stopping process ref-2 ...
09:43:49.032 WRN Unexpected message type EPFD_INTERNAL_HEARTBEAT_REQUEST for unknown system sys-1
09:43:49.037 WRN Unexpected message type EPFD_INTERNAL_HEARTBEAT_REQUEST for unknown system sys-1
09:43:50.031 INF Stopping process ref-3 ...
09:43:50.042 INF Stopping hub ...
INFO: Stopped
- A few comments on how this works
- Log level debug shows all messages except for those related to heartbeat
- Log level trace will show everything
- The commands log messages are written over the command prompt, but you can always type "blindly" and
hit ENTER. This may become necessary if the trace logging is too much; just type "log debug" and hit ENTER.
- When the algorithm is over, it will seem stuck, but in fact is just waiting for another command. Hit ENTER
and you will see the prompt again.
- Look for INF log entries showing what each process has delivered/read/decided
- Everything you see in the console is also logged in file dalgs-ref.log
- The errors after quit are caused by the stopping heartbeat exchange, and can be ignored
*/
message ProcessId {
string host = 1; // String containing either domain name or IP (most likely)
int32 port = 2;
string owner = 3; // Short alias or acronym of the owner of the process
int32 index = 4; // Process index within the owner's processes. Must be 1, 2, or 3
int32 rank = 5; // Populated by the hub when initiating consensus with AppPropose. Do not calculate your own rank,
// just use this so that all nodes have the same values
}
message Value { // Needed to model the undefined value that appears in the textbook
bool defined = 1;
int32 v = 2; // Value; ignore if defined == false
}
// Messages and events
// Process
message ProcRegistration { // Send to hub upon process startup: Message(NetworkMessage(Message(ProcRegistration)))
string owner = 1; // Some short alias
int32 index = 2; // Process index: must be 1, 2, or 3
}
message ProcInitializeSystem { // Received from the HUB as Message(NetworkMessage(Message(AppInitializeSystem))). Should
// be handled by the process.
repeated ProcessId processes = 1; // List of processes involved in the consensus algorithm (PI set)
}
message ProcDestroySystem { // Received from the HUB as Message(NetworkMessage(Message(AppDestroySystem))). Unregister
// and deactivate all abstractions belonging to the systemId found in the wrapping Message
}
// APP
message AppBroadcast { // Received from the HUB as Message(NetworkMessage(Message(AppBroadcast)))
// Triggers a BEB broadcast containing AppValue populated with the value from AppBroadcast
Value value = 1;
}
message AppValue { // Broadcasted by the chosen source. Upon receiving it in a BebDeliver, send to HUB as
// Message(NetworkMessage(Message(AppValue)))
Value value = 1;
}
message AppPropose { // Received from the HUB as Message(NetworkMessage(Message(AppPropose)))
string topic = 1; // The topic on which to reach consensus. There will be a consensus instance for each topic
Value value = 2; // Random value chosen by the HUB
}
message AppDecide { // Upon receiving UcDecide, send to HUB as Message(NetworkMessage(Message(AppDecide)))
Value value = 1; // Decided value taken from UcDecide
}
message AppRead { // Received from the HUB as Message(NetworkMessage(Message(AppRead)))
string register = 1;
}
message AppWrite { // Upon receiving UcDecide, send to HUB as Message(NetworkMessage(Message(AppWrite)))
string register = 1;
Value value = 2; // Value to write in the register
}
message AppReadReturn { // Upon receiving NnarReadReturn, send to HUB as Message(NetworkMessage(Message(AppReadReturn)))
string register = 1;
Value value = 2; // Value read from the register
}
message AppWriteReturn { // Upon receiving NnarWriteReturn, send to HUB as Message(NetworkMessage(Message(AppWriteReturn)))
string register = 1;
}
// UC
// In the Init event or constructor, initialize l (leader) with the max-rank process in PI
message UcPropose {
Value value = 1;
}
message UcDecide {
Value value = 1;
}
// EP
message EpAbort {
}
message EpAborted {
int32 ets = 1; // Needed to know in UC the timestamp of the EP, where the algorithm says "such that ts = ets do"
int32 valueTimestamp = 2; // The timestamp part of the "state" mentioned in the algorithm
Value value = 3; // The value part of the "state" mentioned in the algorithm
}
message EpPropose {
Value value = 1;
}
message EpDecide {
int32 ets = 1; // Needed to know in UC the timestamp of the EP, where the algorithm says "such that ts = ets do"
Value value = 2;
}
message EpInternalRead {
}
message EpInternalState {
int32 valueTimestamp = 1;
Value value = 2;
}
message EpInternalWrite {
Value value = 1;
}
message EpInternalAccept {
}
message EpInternalDecided {
Value value = 1;
}
// EC
// In the Init event or constructor, initialize "trusted" with the max-rank process in PI
message EcInternalNack {
}
message EcStartEpoch {
int32 newTimestamp = 1;
ProcessId newLeader = 2;
}
message EcInternalNewEpoch {
int32 timestamp = 1;
}
// BEB
message BebBroadcast {
Message message = 1;
}
message BebDeliver {
Message message = 1;
ProcessId sender = 2;
}
// ELD
message EldTimeout {
}
message EldTrust {
ProcessId process = 1;
}
// NNAR
message NnarRead {
}
message NnarInternalRead {
int32 readId = 1;
}
message NnarInternalValue {
int32 readId = 1;
int32 timestamp = 2;
int32 writerRank = 3;
Value value = 4;
}
message NnarInternalWrite {
int32 readId = 1;
int32 timestamp = 2;
int32 writerRank = 3;
Value value = 4;
}
message NnarWrite {
Value value = 1;
}
message NnarInternalAck {
int32 readId = 1;
}
message NnarReadReturn {
Value value = 1;
}
message NnarWriteReturn {
}
// EPFD
// Use as timer delay "delta" 100 milliseconds
message EpfdTimeout {
}
message EpfdInternalHeartbeatRequest {
}
message EpfdInternalHeartbeatReply {
}
message EpfdSuspect {
ProcessId process = 1;
}
message EpfdRestore {
ProcessId process = 1;
}
// PL
message PlSend {
ProcessId destination = 1;
Message message = 2;
}
message PlDeliver {
ProcessId sender = 1;
Message message = 2;
}
// Network-traveling message
// When handling MessageA(PlSend(MessageB)) create MessageC(NetworkMessage(MessageB)), setting:
// MessageC.SystemId = MessageA.SystemId
// MessageC.ToAbstractionId = MessageA.ToAbstractionId
// NetworkMessage.senderHost = N/A (ignore)
// NetworkMessage.senderListeningPort = The your listening port
// Then marshal MessageC to byte buffer and send:
// bytes 0 - 3: buffer length
// bytes 4 - : buffer data
// When unmarshalling from a buffer received from the network create MessageD(PlDeliver(MessageB)), setting:
// MessageD.ToAbstractionId = MessageC.ToAbstractionId
message NetworkMessage {
string senderHost = 1;
int32 senderListeningPort = 2;
Message message = 3;
}
// Wrapper message
message Message {
enum Type {
NETWORK_MESSAGE = 0;
PROC_REGISTRATION = 1;
PROC_INITIALIZE_SYSTEM = 2;
PROC_DESTROY_SYSTEM = 3;
APP_BROADCAST = 4;
APP_VALUE = 5;
APP_DECIDE = 6;
APP_PROPOSE = 7;
APP_READ = 8;
APP_WRITE = 9;
APP_READ_RETURN = 10;
APP_WRITE_RETURN = 11;
UC_DECIDE = 20;
UC_PROPOSE = 21;
EP_ABORT = 30;
EP_ABORTED = 31;
EP_DECIDE = 32;
EP_INTERNAL_ACCEPT = 33;
EP_INTERNAL_DECIDED = 34;
EP_INTERNAL_READ = 35;
EP_INTERNAL_STATE = 36;
EP_INTERNAL_WRITE = 37;
EP_PROPOSE = 38;
EC_INTERNAL_NACK = 40;
EC_INTERNAL_NEW_EPOCH = 41;
EC_START_EPOCH = 42;
BEB_BROADCAST = 50;
BEB_DELIVER = 51;
ELD_TIMEOUT = 60;
ELD_TRUST = 61;
NNAR_INTERNAL_ACK = 70;
NNAR_INTERNAL_READ = 71;
NNAR_INTERNAL_VALUE = 72;
NNAR_INTERNAL_WRITE = 73;
NNAR_READ = 74;
NNAR_READ_RETURN = 75;
NNAR_WRITE = 76;
NNAR_WRITE_RETURN = 77;
EPFD_INTERNAL_HEARTBEAT_REPLY = 80;
EPFD_INTERNAL_HEARTBEAT_REQUEST = 81;
EPFD_RESTORE = 82;
EPFD_SUSPECT = 83;
EPFD_TIMEOUT = 84;
PL_DELIVER = 90;
PL_SEND = 91;
}
Type type = 1;
string messageUuid = 2;
string FromAbstractionId = 3; // Abstraction ID constructed as shown to the right of the system diagram
string ToAbstractionId = 4; // Abstraction ID constructed as shown to the right of the system diagram
string systemId = 5;
NetworkMessage networkMessage = 6;
ProcRegistration procRegistration = 7;
ProcInitializeSystem procInitializeSystem = 8;
ProcDestroySystem procDestroySystem = 9;
AppBroadcast appBroadcast = 10;
AppValue appValue = 11;
AppPropose appPropose = 12;
AppDecide appDecide = 13;
AppRead appRead = 14;
AppWrite appWrite = 15;
AppReadReturn appReadReturn = 16;
AppWriteReturn appWriteReturn = 17;
UcDecide ucDecide = 20;
UcPropose ucPropose = 21;
EpAbort epAbort = 30;
EpAborted epAborted = 31;
EpInternalAccept epInternalAccept = 32;
EpDecide epDecide = 33;
EpInternalDecided epInternalDecided = 34;
EpPropose epPropose = 35;
EpInternalRead epInternalRead = 36;
EpInternalState epInternalState = 37;
EpInternalWrite epInternalWrite = 38;
EcInternalNack ecInternalNack = 41;
EcInternalNewEpoch ecInternalNewEpoch = 42;
EcStartEpoch ecStartEpoch = 43;
BebBroadcast bebBroadcast = 50;
BebDeliver bebDeliver = 51;
EldTimeout eldTimeout = 60;
EldTrust eldTrust = 61;
NnarInternalAck nnarInternalAck = 70;
NnarInternalRead nnarInternalRead = 71;
NnarInternalValue nnarInternalValue = 72;
NnarInternalWrite nnarInternalWrite = 73;
NnarRead nnarRead = 74;
NnarReadReturn nnarReadReturn = 75;
NnarWrite nnarWrite = 76;
NnarWriteReturn nnarWriteReturn = 77;
EpfdTimeout epfdTimeout = 80;
EpfdInternalHeartbeatRequest epfdInternalHeartbeatRequest = 81;
EpfdInternalHeartbeatReply epfdInternalHeartbeatReply = 82;
EpfdSuspect epfdSuspect = 83;
EpfdRestore epfdRestore = 84;
PlDeliver plDeliver = 90;
PlSend plSend = 91;
}