-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTODO
202 lines (155 loc) · 14.8 KB
/
TODO
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
(1) probar el hiding de las actions (what should be the impact?)
(2) Mostrar solo drops cuando no se hizo el deliver ni el drop, y se hizo el send correspondiente
(3) Dibujar mejor las flechas a self
(4) No crear drops cuando from == to (porque no hay red, asi que no se podrian perder)
(5) [Triggers]: "Every event triggered by a component of the same process is eventually processed, if the process is correct.
Events from the same componet are processed in the order in which they were triggered. This FIFO order is
only enforced on events exchanged among local components in a given stack.
We assume that every process executes the code triggered by events in a mutually exclusive way. This means
that the same process doen not handle two events concurrently." (Pag 10)
Esto implica que no puedo hacer un bcast - send - (some other action) - send.
Sin embargo, a nivel teoria de IOAutomata no encontre nada similar a un trigger, asi que por el momento lo voy a implementar como una capa por sobre la teoria: instalacion
de tiggers en la execution).
(6) Deberia manerar dos conceptos de step
- Sched index: unico por action.
- Logical step: compartido por un grupo de acciones, por ejemplo los send de un bcast, o acciones concurrentes en distintos procesos.
Este seria util para mejorar los graficos.
Habria que ver cual es el impacto en los filtros que estoy usando para mostrar solo las acciones disponibles en ese step.
(7) Revisar MessageID
(8) Con la implementación actual no puedo insertar lamport timestamp o vector clocks a los mensajes porque el numero de combinaciones tiende a infinito.
Las acciones no solo van a depender de Sender + Receiver + Step + Payload, sino que dependen de la historia de mensajes enviados que es la que define el valor del vector clock.
Por ahi para lamport timestamp no es tan dificil porque es un unico numero, podria generar para un Msg, la combinacion los timestamp de 1 a 1000, pero los vector clocks son mucho mas complejos.
Alternativas
(a) No usar lamport timestamps ni vector clocks. (X) Descartada: estas son las cosas mas interesantes en sistemas distribuidos.
(b) No usar la teoria de IO. Me saca la base teorica.
(c) No usar el payload como parte de las action que forman la signature del automata.
(d) Agregar lamport timestamp como metadata de la action, de modo que no afecte la signature.
(9) Es muy complicado (y propenso a errores) reconocer que state corresponde a cual automata (tal vez para los que son de procesos no porque por ahora tengo 1 automata por proceso,
por ejemplo 1 process y 1 bcast) pero si para los de links.
(10) Tengo que implementar un caso (o al menos una parte) con mi herramienta.
Alternativas:
- Cassandra
- Kafka
- CRDTs (tal vez con llevar, esto que no esta implementado en el libro, alcanza)
#(11) Consultar a los autores del libro
(a) abstracciones de links
- UDP -> FairLossLink?
- TCP -> PerfectLink?
(b) cómo traducir los triggers?
(12) Shared memory.
- Capacidad de dibujar writes and reads
- "Remember that these events occur at a single indivisible point in time, using a fictional notion of global time that only serves to reason about specifitacions and algorithms" (pag 141)
¿Se refiere al par de ventos Read-ReadReturn y Write-WriteReturn?
- "An operation o is said to precede an operation o' if the completion event of o occurs BEFORE the invocation event of o'" (pag 141)
¿Before según qué? ¿Puedo usar el orden de la action en la execution para definir before?, el problema es que no podría considerar actions concurrentes.
La otra opción sería la de usar el step en lugar del índice de la action en la execution, es decir el step lógico que usaría para seleccionar un conjunto de acciones (1 por process).
Funcionaría como un reloj lógico. Aunque también debería incorporar el uso de un reloj físico porque me va a permitr usar drift y skew (el lógico no).
(X)(13) "The instances are differentiated by their identifiers, and all messages exchanged using the underlying communication primitives
implicitly carry an instance identifier to match the same instance at all processes" (pag 145)
(14) Deliver a un processo Down deberia estar habilitado, y que no haga nada.
(15) Incorporar interfaces = Name + Requests (aka input actions) + Indications (aka output actions) + Properties
Las properties no van a tener un impacto directo (a menos que sepa traducirlas a condiciones sobre la execution, lo que estaria muy bueno)
Investigar cual seria el impacto concreto
(16) Como dibujar stacks de componentes?
En la teoria de automatas no está, tal vez debería definirla paralelamente al automata (o implementar la lógica basada en las input y output actions, ejemplo
si un componente A tiene como output action la input action de un componente B, A esta en layer n y B en layer n + 1)
(17) Reemplazar pattern matching del estilo `id` por el chequeo de si esta en la input action (que va a ser universal para todos los automatons)
(18) Tengo que introducir algunas constraints definidas por el System Model.
Puntualmente cuando se trata de sync model "the transmission period of every message is bounded by some known constant" (pag 50)
Por lo tanto el usuario no puede elegir demorar el Deliver tod el tiempo que quiara, esto es fundamental para PerfectFailureDetector.
(19) Una instancia de FairLossLink,
hace send de A a B
y hace deliver de B a A?, o deliver de A a B?
(20) Estoy manejando dos tipos de estados en los automatas
(a) Visible: es propio de la abstraction implementada. Ejemplo alive and detected sets on PerfectFailureDetection.
(b) Interno: este es el que uso para implementar los triggers (enabled "actions" like deliver after a send). Este estado no se debería mostrar hacia afuera, y no es de interes para el usuario.
(21) Triggers is broken!!!
No puedo calcular las actions to trigger solo a partir de la input action en tods los casos (como BrkDeliver a partir de Deliver).
Ejemplo: PerfectFailureDetector, on Timeout trigger Crash solo para un subconjunto de procesos.
Alternativas
(a) type Triggers = PartialFunction[(Action,S), Set[Action]] (donde S es el State) (ver si es viable)
(b) trait Steps[S] extends PartialFunction[(S, Action), NextState[S]]
(22) Effect.precondition should return more information than a boolean, for debuggin purposes.
(25) Revisar el uso de Message, porque mandar un payload directamente? Esta relacionado con el punto 24 porque Message tmb incluye un MessageID.
El uso de MessageID era para identificar univocamente los mensajes y poder armar la signature en base a estos mensajes. También podria usar un UUID pero en ese caso, cuantos uuid armo?
(26) Internal Actions. Timeout (PerfectFailureDetector)
No puede estar siempre disponible.
(a) Creo acciones de tipo Timeout(step = 0), Timeout(step = 3), Timeout(step = 6) (Donde 3 seria el bounded delay del synchronous system).
(b) La habilito en base al estado. Este estado deberia tener algun Clock que identifique el step, que se actualice con una input action Tick.
(27) Como implementar el synchronous system, que a comparacion del partially synchronous tiene un bounded delay y me permite usar algoritmos como el de PerfectFailureDetector?
Alternativas
(a) Forzar el deliver on timeout. Ejemplo: si se hizo el send en 0 y el bounded delay es de 3, en 3 tengo que forzar el deliver si el usuario no lo hizo.
(b) Lo puedo poner como conditions para pasar el level.
En ambas opciones tengo que tener la logica para llevar este control de sends sin deliverear y por cuanto tiempo.
(28) Tests!!!!!
(29) Steps[S] extends PartialFunction[(S, Action), ActionResult[S]]
Donde ActionResult = NextState | NotDefined | UnsatisfiedPrecondition
Me da mayor legibilidad y hago explicto lo de que la action q no se matchee en el pattern matching es como q no esta definida en la action signature.
Ademas, deberia evitar esto en los automaton y directamente usar la signature del automaton para saber si esta definida o no la action.
(30) BRODCAST Y LAMPORT TIMESTAMPS
Incrementaria el timestampo por cada send? O una unica vez por el Brodcast?
Creo que al ser los tres send atomicos (o al menos deberian serlos gracias a los triggers) no habria problemas.
(31) Un lamport timestamp por abstraccion? Suponiendo que el proceso hace dos cosas por ejemplo.
#(32) Por que los algoritmos de consensus (e.g. Flooding Consensus) tienen que hacer un propose todos los nodos?
Cómo se traduciría a un uso práctico? Suponiendo un cluster que implementa consensus y funciona como un servicio de consensus.... puede ser que un solo cliente proponga un valor, o no?
(33) Flooding Consensus tiene
(a) Doble trigger (Bcast y Decide) Deberia ser Bcast, (triggered actions by bcast), Decide (triggerd actions by Decide?
(b) Internal action on condition. Special Action Internal que permita triggerear actions? o se triggere a partir de, en este caso, beb-Deliver(Proposal) y beb-Deliver(Decided)
(34) Message metadata => lamport timestamp y vector clocks. Rompen la ActionSignature
En realidad no es propio de la metadata sino de to.do el payload, al menos cuando no se reduce a un conjunto como HeartbeatRequest y HeartbeatReply con process ids.
Para los payloads lo habia resuelto delimitando el universo de payloads (ejemplo= 1, 2 y 3)
El problema es cuando los payloads empiezan a depender de la logica del automata, ejemplo Flooding Consensus arma el Proposal en base al round y el valor que tiene actualmente.
#(35) Porque es necesario hacer un halt de EpochConsensus e instanciar uno nuevo? (Pag 223 y 225)
No se puede modifcar el estado?
Entiendo que el halt es para lograr lo que se dice en (36) ("Different instances..."), pero no se puede hacer simplemente descartando los mensajes que tengan un timestamp != current valts
#(36) Multiple instances of epoch consensus may be executed at the same point in time by different processes, but when used in our "Leader Driven Consensus" algorithm, then every process only
runs at most one epoch consensus instance at a time.
Different instances never interfere with each other according to our assumption that every instance is identified by a unique epoch timestamp and because point to point messages and best
effort bcast messages are only received from and delivered to other instances with the same timestamp.
(Pag 222)
No entiendo a que hace referencia con la primer parte?
#(37) Obtain the leader l0 of the inital epoch whit timestamp 0 from epoch change instance
(Pag 223)
(38) Si ya no puedo pedir la lista de actions enabled (por 34), como puedo mostrar la lista de acciones al usuario para que elija?
Voy a tener que mostrar simplemente las action signatures (ej: Send(1,0)) y el usuario va a tener que "deducir" que mandar en base al estado.
Ok.... pero si deduce que tiene que mandar un HeartbeatRequest(1) como lo "ingresaria" en la UI para que se envie?
Es decir, tengo que mostrarle al input especial que permita elegir el "tipo" de payload a mandar, y este tipo de payload depende de las abstracciones elegidas.
Por ejemplo, si hay un PerfectFailureDetector el usuario puede elegir HeartbeatRequests o HeartbeatReply, pero si no estan no.
Con lo cual, los payloads "disponibles" van a depender de
(a) Los automatas que formen la composicion (ej: si esta pfd tengo HeartbeatRequest/Reply)
(b) El estado de los automatas (ej: si el usuario hizo un Send(payload = Value(4)), habilita el Deliver(payload = Value(4))
El punto (b) tal vez sea mas sencillo, porque en realidad esto ya esta determindo por las actions triggered, solo habria que "disponibilizarlas" al usuario.
El punto (a) es mas complicado, sobre tod si requerimos un UUID (el libro lo tiene como requerimiento y yo lo uso para matchear send con deliver y poder dibujarlos),
un lamport timestamp o un vector clock.
Incluso lamport y vector clock pueden no ser tan sencillos pero si deducibles por parte del usuario (que debera entenderlos para poder usarlos)
Pero el UUID?
Podria ponerlo yo por abajo cuando el usuario seleccione un Send. Luego le va a figurar el Deliver correspondiente con un UUID
(39) ¿Cómo hacer un automata process reutilizable en base a los stacks de automaton que se compongan? Ejemplo, si se usa bcast tiene que entender BcastDeliver, si se usa
FailureDetector tiene que entender timeout, etc.
(40) (a) Tick(instance) o (b) Tick(instance,process)?
Con (a) todos los PFD van a timeoutear en el mismo momento (lo cual tiene sentido para el sync model)
(41) Ya que me estoy alejando del modelo de automata, no seria conveniente que el state sea parte del automaton?
Con lo cual me ahorraria el tema de componer estado en tuplas.
(42) La logica para traducir el sched a GridProps (aka step donde se cayeron los procesos mas mensajes entregados) también depende del stack de componentes que conforman los automaton.
Por ejemplo, un automaton puede manejar la action Crashed y otro CrashedAll, necesito saber que actions "buscar" en el sched.
(43) Cuál es el step de una action?
Lo uso solo para dibujar? Si es asi deberia ir en ui y no en core.
Si es solo para dibujar, podria incrementar el tick:
(a) Despues de cada action
(b) Después de cada action seleccionada por el usuario (esto excluiria triggered actions), entonces un Bcast y los Send sucederian todos en el mismo Step. Pareceria estar bien porque
sucede dentro del mismo componente de manera local (no implica red).
Si tiene algún impacto en la lógica de los automaton, podria incrementarlo con cada Tick (esto tambien lo puedo usar para mover los relojes locales y mostrar el clock drift)
(44) En FLL, el Send habilita el Deliver y el Drop. Pero luego si hago un Deliver ya no deberia poder hacer el drop. El problema es que es input enabled.
(a) Hacer drop output action
(b) Tener otra funcion que elimine actions del set de enabled! En este caso un Deliver elimina el Drop.
(45) Quiero tener la posibilidad de hacer distintos tipos de procesos, por ejemplo para poder hacer un cluster de cassandra y un cluster de clientes.
(46) BCast no tiene el id de los procesos, tengo que tener cuidado con esto si quiero tener clusters de distinto tipo (ej kafka y cassandra). Supongo que lo puedo hacer
via instanceId, pero tambien lo estoy hardcodeando.
(47) Voy a poder disponiblizar los vector clocks via metadata? O voy a tener que incorporar un tipo de comunicación diferente para componetnes locales?
Y alguna noción de contexto en el cual vaya poniendo elementos como vector clocks. El objetivo es que pueda usar un beb bcast para mandar mensajes con o sin vector clock.
Prioridades
(35)(36)(37) => update state?
(34)
(27)
(32)
(33)