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