Transcript Set 14

CPSC 668
Distributed Algorithms and
Systems
Fall 2006
Prof. Jennifer Welch
CPSC 668
Set 14: Simulations
1
Motivation
• Next section of the course focuses on
tools and abstractions for simplifying the
design of distributed algorithms.
• To approach this rigorously, we need to
treat specifications and implementations
(a.k.a. simulations) more generally.
CPSC 668
Set 14: Simulations
2
Problem Specifications So Far
• Approach so far has been problemspecific:
– put conditions on processor states as they
relate to each other and to initial states
– for example: consensus, leader election,
etc.
• Not so convenient when we want to
study simulations from one system
model to another, with respect to
arbitrary problems
CPSC 668
Set 14: Simulations
3
New Way to Specify Problems
A problem specification  consists of
• an interface
– set of inputs and
– set of outputs
• and a set of allowable sequences of
inputs and outputs
This is how users of a solution to the
problem communicate with the solution.
CPSC 668
Set 14: Simulations
4
Mutual Exclusion Example
To specify the mutual exclusion problem:
• inputs are T0, …, Tn-1 (Ti indicates pi
wants to try to enter the critical section)
and E0,…, En-1 (Ei indicates pi wants to
exit the critical section).
• outputs are C0,…,Cn-1 (Ci indicates pi
may now enter the critical section) and
Ri,…,Rn-1 (Ri indicates pi may now enter
the remainder section)
CPSC 668
Set 14: Simulations
5
Mutual Exclusion Example (cont'd)
• a sequence  of inputs and outputs is
allowable iff, for each i,
– |i cycles through Ti, Ci, Ei, Ri (syntactically
well-formed)
– whenever Ci occurs, most recent preceding
input or output for any j ≠ i is not Cj (only
one process is in the critical section at a
time)
CPSC 668
Set 14: Simulations
6
Mutual Exclusion Example (cont'd)
• T1 T2 C1 T3 E1 C3 R1 E3 R3
– allowable
• T1 T2 C1 T3 C3 E1 R1 E3 R3
– not allowable
CPSC 668
Set 14: Simulations
7
Communication Systems So Far
• So far, we have explicitly modeled the
communication system
– inbuf and outbuf state components and
deliver events for message passing,
– explicit shared variables as part of
configurations for shared memory
• Not so convenient when we want to
study how to provide one kind of
communication in software, given
another kind.
CPSC 668
Set 14: Simulations
8
Different Kinds of Communication
Systems
• Message passing vs. shared memory
– different interfaces (sends/receives vs.
invocations/responses)
• Within message passing:
– different levels of reliability, ordering
– different guarantees on content (when
malicious failures are possible)
• Within shared memory:
– different shared variable semantics
CPSC 668
Set 14: Simulations
9
What Kinds of Simulations?
• How to provide broadcast (with different
reliability and ordering guarantees) on top of
point-to-point message passing
• How to provide shared objects on top of
message passing
• How to provide one kind of shared objects on
top of another kind
• How to provide stronger synchrony on top of
an asynchronous system
• How to provide better-behaved faulty
processors on top of worse-behaved ones
CPSC 668
Set 14: Simulations
10
New Way to Model
Communication Systems
• Interpose a communication system
between the processors
• A particular type of communication
system is specified using the approach
just described
– focus on the desired behavior of the
communication system, as observed at its
interface, instead of the details of how that
behavior is provided
CPSC 668
Set 14: Simulations
11
Asynchronous Point-to-Point
Message Passing Example
Interface is:
• inputs: sendi(M)
– models pi sending set of msgs M
– each msg indicates sender and recipient
(must be consistent with assumed
topology)
• outputs: recvi(M)
– models pi receiving set of msgs M
– each msg in M must have pi as its recipient
CPSC 668
Set 14: Simulations
12
Asynch MP Example (cont'd)
• For a sequence of inputs and outputs (sends
and receives) to be allowable, there must
exist a mapping  from the msgs in recv
events to msgs in send events s.t.
– each msg in a recv event is mapped to a msg in a
preceding send event
–  is well-defined: every msg received was
previously sent (no corruption or spurious msgs)
–  is one-to-one: no duplicates
–  is onto: every msg sent is received
CPSC 668
Set 14: Simulations
13
Asynchronous Broadcast Example
• Inputs: bc-sendi(m)
– an input to the broadcast service
– pi wants to use the broadcast service to
send m to all the procs
• Outputs: bc-recvi(m,j)
– an output of the broadcast service
– broadcast service is delivering msg m, sent
by pj, to pi
CPSC 668
Set 14: Simulations
14
Asynch Bcast Example (cont'd)
• A sequence of inputs and outputs (bc-sends
and bc-recvs) is allowable iff there exists a
mapping  from each bc-recvi(m,j) event to an
earlier bc-sendj(m) event s.t.
–  is well-defined: every msg bc-recv'ed was
previously bc-sent
–  restricted to bc-recvi events, for each i, is one-toone: no msg is bc-recv'ed more than once at any
single proc.
–  restricted to bc-recvi events, for each i, is onto:
every msg bc-sent is received at every proc.
CPSC 668
Set 14: Simulations
15
Processes
• Running on each processor will be a piece of
code (process) to simulate the desired
communication system.
• No longer accurate to identify "the algorithm"
with the processor, because there may be
several algorithms (processes) running on the
same processor. For example:
– one process (algorithm) that uses the broadcast
service
– another process (algorithm) that implements the
broadcast service on top of a point-to-point MP
system
CPSC 668
Set 14: Simulations
16
Modeling Process Stack at a Node
environment
modeled as a problem
spec (interface &
allowable sequences)
layer 1
modeled
as state
machines
communicate via
appropriate primitives:
shared events
layer 2
layer 3
communication system
CPSC 668
Set 14: Simulations
modeled as a problem
spec (interface &
allowable sequences)
17
Intra-Node Communication Pattern
• Activity is initiated by a node input (input
coming in from environment on top or
communication system at bottom)
• Triggers some activity at the top (or bottom)
layer, which in turn can trigger some activity
at the layer above or below
• Chain reaction can continue for some time
but must eventually die out
• All activity at one node, in response to a
single node input, is assumed to execute
atomically (w.r.t. other nodes)
CPSC 668
Set 14: Simulations
18
Definition of Execution
Sequence C0 e1 C1 e2 C2 … of alternating configurations
and events s.t.
• C0 is an initial configuration
• event ei is enabled in Ci-1 (there is a transition from the
state(s) of the relevant process(es) in Ci-1 labeled ei)
• state components of processes change according to
the transition functions for ei
• can chop the exec. into pieces so that
– each piece starts with a node input
– all events in each piece occur at the same node
– a node input does not occur unless no events (other than node
inputs) are enabled
CPSC 668
Set 14: Simulations
19
Definition of Admissible Execution
• We only require an algorithm to be
correct if
– each process is given enough
opportunities to take steps (called
fairness)
– the communication system behaves
"properly" and
– the environment behaves "properly"
• Executions satisfying these conditions
are admissible.
CPSC 668
Set 14: Simulations
20
Proper Behavior of
Communication System
• The restriction of the execution to the
events of the interface at the "bottom of
the stack" is an allowable sequence for
the problem specification corresponding
to the underlying communication system
• Example: message passing, every
message sent is eventually received
CPSC 668
Set 14: Simulations
21
Proper Behavior of Environment
• The environment (user) interacts
"properly" with the top layer of the stack
(through the interface events) as long
as the top layer is also behaving
properly.
• Mutex example: the user only requests
to leave the critical section if it is
currently in the critical section.
CPSC 668
Set 14: Simulations
22
Simulations
System C1 simulates system C2 if there is a set
of processes, one per node, called Sim s.t.
1. top interface of Sim is the interface of C2
2. bottom interface of Sim is the interface of C1
3. For every admissible execution  of Sim,
the restriction of  to the interface of C2 is
allowable for C2 (according to its problem
spec).
CPSC 668
Set 14: Simulations
23
Simulations
C2 inputs
C2 outputs
…
Sim0
C1 inputs
C2 inputs
C1 outputs
C2
C2 outputs
Simn-1
C1 inputs
C1 outputs
C1
CPSC 668
Set 14: Simulations
24