Upload
denis-erfurt
View
150
Download
1
Embed Size (px)
Citation preview
Ein dezentrales Transitionssystem zur manipulation von geteilten
Wörtern einer regulären Sprache
Denis Erfurt 06. 08. 2015
1
1. Blochchain und BZ Generelle2. DAOs und ihre Selbstmodifikation3. Abgrenzung zu Context freien Grammatiken
2
Vorstellung der Arbeit Agenda
Byzantinische Generäle
https://openclipart.org/detail/217095/byzantine-generals-problem
proof of workpartial hash inversion
5
⇢
DAODAO
DAO
7
Problemstellung
8
• Akteure:• Besitzverteilung:• Kandidaten:• strickte Totalordnung:• Bewertung:
<⇢ K ⇥K
OG = (A,K,<, share, vote)
DAO - Definition
9
10
Konsens DAO - Definition
consens : DAOG ! L(G)
value(k) :=X
a2A
share(a) ⇤ vote(a, k)
consens(OG) := min<({k | value(k) = max
k02KG
(value(k0))})
11
Konsens DAO - Definition
consens : DAOG ! L(G)
value(k) :=X
a2A
share(a) ⇤ vote(a, k)
consens(OG) := min<({k | value(k) = max
k02KG
(value(k0))})
12
Konsens DAO - Definition
consens : DAOG ! L(G)
value(k) :=X
a2A
share(a) ⇤ vote(a, k)
consens(OG) := min<({k | value(k) = max
k02KG
(value(k0))})
13
Kodierung
14
KodierungDAO
Sei G regular, wir betrachten L(G)
15
KodierungDAO
Sei G regular, wir betrachten L(G)
S : REG ! CFG
Gesucht :
16
KodierungDAO
Sei G regular, wir betrachten L(G)
S : REG ! CFG
� : DAOG ! L(S(G))
��1 : L(S(G)) ! DAOG
��1 � � = idDAOG
Gesucht :
17
KodierungDAO
Sei G regular, wir betrachten L(G)
S : REG ! CFG
� : DAOG ! L(S(G))
��1 : L(S(G)) ! DAOG
��1 � � = idDAOG
Gesucht :
consens(OG) = w , consens0(w0) = w
Beispiel
18
����� ���
���� �����
���
� ��
��
��
��� � �
a a a a aa a ca a c ca a c c c
KodierungKandidaten
aa& [aaa& c& c& [ c& cc&]]
Beispiel
19
����� ���
���� �����
���
� ��
��
��
��� � �
a a a a aa a ca a c ca a c c c
KodierungKandidaten
aa& [aaa& c& c& [ c& cc&]]
Beispiel
20
����� ���
���� �����
���
� ��
��
��
��� � �
a a a a aa a ca a c ca a c c c
KodierungKandidaten
aa& [aaa& c& c& [ c& cc&]]
Beispiel
21
����� ���
���� �����
���
� ��
��
��
��� � �
a a a a aa a ca a c ca a c c c
KodierungStimmen
v2 v3
v5 v6
v4
v1aa&v1 [ aaa&v2 c&v3 ...
aa& [aaa& c& c& [ c& cc&]]
vi 2 A⇥ N
����� ���
���� �����
���
� ��
��
��
��� � �
v2 v3
v5 v6
v4
v1
Beispiel
22
a a a a aa a ca a c ca a c c c
KodierungDelegationen
D1
D2 aa&v1 [ aaa&v2 ...]D1
aa&v1 [ aaa&v2 c&v3 ...
aa& [aaa& c& c& [ c& cc&]]
Di 2 A⇥Avi 2 A⇥ N
Transitionssystem - Regeln
• Erzeugen von Optionsmengen
• Erweitern von Optionsmengen
• Hinzufügen der eigenen Stimme
• Löschen der eigenen Stimme
• Hinzufügen einer Delegation
• Löschen einer Delegation
23
Abgrenzung zu CFGAnhand eines Beispiels
24
G = (T,N, P, S)
T := {a, b, c}N := {S,B,C}P := {S ! BC,B ! a|b, C ! a|b|c}
Abgrenzung zu CFGBeispiel
L(G) = {aa, ab, ac, ba, bb, bc}
K1 := {ab, ac, ba}
25
Abgrenzung zu CFGBeispiel
L(G) = {aa, ab, ac, ba, bb, bc}
K1 := {ab, ac, ba}
[ a & b ][ a & b & c ]
26
Abgrenzung zu CFGBeispiel
L(G) = {aa, ab, ac, ba, bb, bc}
K1 := {ab, ac, ba}
[ a & b ][ a & b & c ]
27
Abgrenzung zu CFGBeispiel
L(G) = {aa, ab, ac, ba, bb, bc}
K1 := {ab, ac, ba}
[ a & b ][ a & b & c ]
28
Abgrenzung zu CFGBeispiel
L(G) = {aa, ab, ac, ba, bb, bc}
K1 := {ab, ac, ba}
[ a & b ][ a & b & c ]
29
K2 = L(G)
Ein dezentrales Transitionssystem zur manipulation von geteilten
Wörtern einer regulären Sprache
Denis Erfurt 06. 08. 2015
30