Chapter8
59 pág.

Chapter8


DisciplinaAlgorítimos Distribuídos28 materiais273 seguidores
Pré-visualização9 páginas
in all states the process considers possible.
Positive Introspection Axiom: Ki\u3c8 =\u21d2 KiKi\u3c8
Negative Introspection Axiom: ¬Ki\u3c8 =\u21d2 Ki¬Ki\u3c8
Knowledge Generalization Rule: For a valid formula or fact \u3c8, Ki\u3c8
If \u3c8 is true in all possible worlds, then \u3c8 must be true in all the possible
worlds with respect to any process and any given world.
Assumption: a process knows all valid formulas, which are necessarily true.
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 12 / 29
Distributed Computing: Principles, Algorithms, and Systems
Knowledge in Synchronous vs. Asynchronous Systems
Thus far, synchronous systems considered.
How to attain common knowledge in synchronous systems?
Initialize all with common knowledge of \u3c6
Broadcast \u3c6 in a round of communication, and let all know that \u3c6 is being broadcast.
Each process can begin supporting common knowledge from the next round.
Asynchronous system:
possible worlds: the consistent cuts of the set of possible executions.
Let (a, c) denote a cut c in asynchronous execution a.
(a, c) also denotes the system state after (a, c).
(a, c)i : projection (i.e., state) of c on process i .
Cuts c and c \u2032 are indistinguishable by process i , denoted (a, c) \u223ci (a\u2032, c \u2032), if and only if
(a, c)i = (a
\u2032, c \u2032)i .
The semantics of knowledge based on asynchronous executions, instead of timed
executions.
Ki (\u3c6): \u3c6 is true in all possible consistent global states that include i \u2019s local state.
Similarly for E k (\u3c6).
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 13 / 29
Distributed Computing: Principles, Algorithms, and Systems
Knowledge in Asynchronous Systems: Logic, Definitions
(1)
(a, c) |= \u3c6 if and only if \u3c6 is true in cut c of asynchronous execution a.
(a, c) |= Ki (\u3c6) if and only if \u2200(a\u2032, c \u2032), ((a\u2032, c \u2032) \u223ci (a, c) =\u21d2 (a\u2032, c \u2032) |= \u3c6)
(a, c) |= E 0(\u3c6) if and only if (a, c) |= \u3c6
(a, c) |= E 1(\u3c6) if and only if (a, c) |= \u2227i\u2208N Ki (\u3c6)
(a, c) |= E k+1(\u3c6) for k \u2265 1 if and only if (a, c) |= \u2227i\u2208N Ki (E k (\u3c6)), for k \u2265 1
(a, c) |= C (\u3c6) if and only if (a, c) |= the greatest fixed point knowledge X
satisfying X = E (X \u2227 \u3c6).
C (\u3c6) implies \u2227k\u2208Z\u2217E k (\u3c6).
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 14 / 29
Distributed Computing: Principles, Algorithms, and Systems
Knowledge in Asynchronous Systems: Logic, Definitions
(2)
\u201ci knows \u3c6 in state sxi \u201d, denoted s
x
i |= \u3c6, is shorthand for (\u2200(a, c))
((a, c)i = s
x
i =\u21d2 (a, c) |= \u3c6).
sxi |= Ki (\u3c6) is shorthand for (\u2200(a, c)) ((a, c)i = sxi =\u21d2 (a, c) |= Ki (\u3c6)).
Learning: Process i learns \u3c6 in state sxi of execution a if i knows \u3c6 in s
x
i and,
for all states syi in execution a such that y < x , i does not know \u3c6.
i attains \u3c6: process learns \u3c6 in the present or an earlier state.
\u3c6 is attained in an execution a: \u2203c , (a, c) |= \u3c6
Local fact: \u3c6 is local to process i in system A if A |= (\u3c6 =\u21d2 Ki\u3c6)
e.g., local state, clock value of a process, local component of vector clock
Global fact: A fact that is not local, e.g., global state, timestamp of a cut
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 15 / 29
Distributed Computing: Principles, Algorithms, and Systems
Common Knowledge in Asynchronous Systems
Reaching consensus over \u3c6 requires common knowledge of \u3c6
Impossibility Result
There does not exist any protocol for two processes to reach common knowledge
about a binary value in an asynchronous message-passing system with unreliable
communication.
Justify: Pi and Pj need to send each other ACKs . . . nonterminating
argument
or Let there be a minimal protocol that has k msgs. Then the kth msg is
redundant \u21d2 contradiction
Is common knowledge attainable in the async system with reliable
communication without an upper bound on message transmission times?
No. construct a similar argument
Is common knowledge attainable in the async system with reliable
communication with an upper bound on message transmission times?
No, for when does a process begin supporting that knowledge?
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 16 / 29
Distributed Computing: Principles, Algorithms, and Systems
Common Knowledge in Asynchronous Systems
Reaching consensus over \u3c6 requires common knowledge of \u3c6
Impossibility Result
There does not exist any protocol for two processes to reach common knowledge
about a binary value in an asynchronous message-passing system with unreliable
communication.
Justify: Pi and Pj need to send each other ACKs . . . nonterminating
argument
or Let there be a minimal protocol that has k msgs. Then the kth msg is
redundant \u21d2 contradiction
Is common knowledge attainable in the async system with reliable
communication without an upper bound on message transmission times?
No. construct a similar argument
Is common knowledge attainable in the async system with reliable
communication with an upper bound on message transmission times?
No, for when does a process begin supporting that knowledge?
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 16 / 29
Distributed Computing: Principles, Algorithms, and Systems
Common Knowledge in Asynchronous Systems
Reaching consensus over \u3c6 requires common knowledge of \u3c6
Impossibility Result
There does not exist any protocol for two processes to reach common knowledge
about a binary value in an asynchronous message-passing system with unreliable
communication.
Justify: Pi and Pj need to send each other ACKs . . . nonterminating
argument
or Let there be a minimal protocol that has k msgs. Then the kth msg is
redundant \u21d2 contradiction
Is common knowledge attainable in the async system with reliable
communication without an upper bound on message transmission times?
No. construct a similar argument
Is common knowledge attainable in the async system with reliable
communication with an upper bound on message transmission times?
No, for when does a process begin supporting that knowledge?
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 16 / 29
Distributed Computing: Principles, Algorithms, and Systems
Common Knowledge in Asynchronous Systems
Reaching consensus over \u3c6 requires common knowledge of \u3c6
Impossibility Result
There does not exist any protocol for two processes to reach common knowledge
about a binary value in an asynchronous message-passing system with unreliable
communication.
Justify: Pi and Pj need to send each other ACKs . . . nonterminating
argument
or Let there be a minimal protocol that has k msgs. Then the kth msg is
redundant \u21d2 contradiction
Is common knowledge attainable in the async system with reliable
communication without an upper bound on message transmission times?
No. construct a similar argument
Is common knowledge attainable in the async system with reliable
communication with an upper bound on message transmission times?
No, for when does a process begin supporting that knowledge?
A. Kshemkalyani and M. Singhal (Distributed Computing) Reasoning with Knowledge CUP 2008 16 / 29
Distributed Computing: Principles, Algorithms, and Systems
Common Knowledge in Asynchronous Systems
Reaching consensus over \u3c6 requires common knowledge of \u3c6
Impossibility Result
There does not exist any protocol for two processes to reach common knowledge
about a binary value in an asynchronous message-passing system with unreliable
communication.
Justify: Pi and Pj need to send each other ACKs . . . nonterminating
argument
or Let there be a minimal protocol that has k msgs. Then the kth msg is
redundant \u21d2 contradiction
Is common knowledge attainable in the async system with reliable
communication without an upper