GlobalPredicateEvaluation

Question 1

What is Global Predicate Evaluation (GPE)?

Answer 1

A problem in DAI systems where the goal is to determine the truth of a Boolean expression referring to the global state of the system.

Question 2

What are the key challenges in GPE?

Answer 2

1) Variables are local to processes. 2) Processes interact only via message passing. 3) The system is asynchronous with no global clock. 4) The global state observed may not be consistent. 5) Communication channels may deliver messages out of order.

Question 3

What are the two approaches for GPE?

Answer 3

1) Reactive Architecture: Processes notify an observer of events as they occur. 2) Proactive Architecture: The observer requests state information from processes when needed.

Question 4

What is a distributed system?

Answer 4

A distributed system consists of sequential processes connected by unidirectional communication channels.

Question 5

What is an event in a distributed system?

Answer 5

An event is an activity of a sequential process, which can be internal events or communications (send(m) or receive(m)).

Question 6

What is the happened-before relation?

Answer 6

A partial order of events where: 1) If e happens before e’ in the same process, then e → e’. 2) If e is a send event and e’ is the corresponding receive event, then e → e’. 3) If e → e’ and e’ → e’’, then e → e’’.

Question 7

What is a global state?

Answer 7

A global state Σ = (σ₁, …, σₙ) is a collection of local states of all processes, where σᵢ is the local state of process pᵢ after executing event eᵢᵏ.

Question 8

What is a cut in a distributed system?

Answer 8

A cut C = (c₁, …, cₙ) is a subset of global history H containing an initial prefix of each local history, representing a ‘freezing’ of the observation of a global state.

Question 9

What is a consistent cut?

Answer 9

A consistent cut is a cut where if an event e belongs to the cut and e’ → e, then e’ also belongs to the cut. A consistent global state corresponds to a consistent cut.

Question 10

What is a consistent run?

Answer 10

A consistent run ensures that if e → e’, then e appears before e’ in the run. Observing consistent runs is essential for evaluating global predicates.

Question 11

What is a reactive architecture?

Answer 11

A reactive architecture involves processes notifying an observer of events as they occur, allowing the observer to construct a view of the distributed computation.

Question 12

What is the problem with reactive architectures?

Answer 12

Due to variable message delays, the observer’s observation may not correspond to the actual computation, leading to inconsistencies.

Question 13

What is the FIFO delivery policy?

Answer 13

A policy where if send(m) → send(m’), then deliver(m) → deliver(m’). It ensures messages are delivered in the order they were sent.

Question 14

Why is FIFO delivery not sufficient for consistent computation?

Answer 14

1) No bound on message delays means it’s unclear how long to wait before delivering. 2) It doesn’t know how to order messages from different processes.

Question 15

What is causal delivery?

Answer 15

Causal delivery ensures messages are delivered in an order consistent with the happened-before relation. Logical clocks and vector clocks are used to implement it.

Question 16

What are logical clocks?

Answer 16

Logical clocks ensure that if e → e’, then LC(e) < LC(e’). Each process maintains a local clock, which is updated based on internal, send, or receive events.

Question 17

What is the causal gap problem?

Answer 17

A problem where logical clocks cannot detect all causal relationships, making it impossible to determine when to deliver messages.

Question 18

What are vector clocks?

Answer 18

Vector clocks provide a strong clock condition: e → e’ if and only if VC(e) < VC(e’). They represent the causal history of an event as a fixed-dimensional vector.

Question 19

How do vector clocks work?

Answer 19

Each process maintains a local vector clock. When a process sends a message, it includes its current vector clock. Upon receiving a message, the process updates its vector clock to reflect the causal history.

Question 20

What is a proactive architecture?

Answer 20

A proactive architecture involves the observer requesting state information from processes to construct a global state, using snapshot protocols to ensure consistency.

Question 21

What is a snapshot protocol?

Answer 21

A protocol that ensures a consistent global state by recording the state of processes and channels at a specific point in time.

Question 22

What is the Chandy & Lamport protocol?

Answer 22

A snapshot protocol where processes record their local state and send snapshot messages to other processes, ensuring a consistent global state without the need for clocks.

Question 23

What are stable predicates?

Answer 23

Stable predicates remain true once they become true, such as deadlock and termination. If a stable predicate is true in a snapshot, it is true in the final state.

Question 24

What are nonstable predicates?

Answer 24

Nonstable predicates may not persist long enough to be detected, such as transient conditions. The observer may not know if the predicate was ever true during the actual run.

Question 25

What are the open issues in GPE?

Answer 25

1) Network structure affects GPE algorithms. 2) Proactive approaches may induce intolerable overhead in large-scale systems. 3) Deciding which process acts as the monitor and replacing it if it fails.