close

Вход

Забыли?

вход по аккаунту

?

The iterated shared memory model of computationand an

код для вставкиСкачать
The iterated shared memory model
of computation and an enrichment
with safe-consensus tasks
Rodolfo Conde
Joint work with Sergio Rajsbaum
Instituto de MatemГЎticas
Universidad Nacional AutГіnoma de MГ©xico
GETCO 2010
The Model
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The Iterated Snapshot Shared Memory
model
• We have n processes that communicate using
a memory SM[i][0…n] (i ≥ 0) of Read/Write
registers
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The Iterated Snapshot Shared Memory
model
• The computation proceeds in rounds
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The Iterated Snapshot Shared Memory
model
• In each round, a process P can atomically
write to SM[i][P]
0
15/01/2010
1
1
Rodolfo Conde and Sergio Rajsbaum
The Iterated Snapshot Shared Memory
model
• each process can atomically read all of SM[i]
0
15/01/2010
1
1
Rodolfo Conde and Sergio Rajsbaum
The Iterated Snapshot Shared Memory
model
• In each round, the processes use a new
memory array
0
1
0
15/01/2010
1
0
Rodolfo Conde and Sergio Rajsbaum
1
Asynchronous
• The n processes are asynchronous
– Arbitrary delays of any kind
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Wait-Free
• The protocols are wait-free
– All but one process can crash
– A process cannot wait to hear from another
process
?
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Generic Iterated Snapshot protocol
init r := 0; sm := input, dec := NULL;
loop forever
r := r + 1;
SM[r].write(sm);
sm := SM[r].snapshot();
/* Local computing */
end loop
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Generic Iterated Snapshot protocol
init r := 0; sm := input, dec := NULL;
P writes sm to SM[r][P]
loop forever
r := r + 1;
SM[r].write(sm);
sm := SM[r].snapshot();
/* Local computing */
end loop
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Generic Iterated Snapshot protocol
init r := 0; sm := input, dec := NULL;
loop forever
r := r + 1;
SM[r].write(sm);
sm := SM[r].snapshot();
P reads all the array
SM[r]
/* Local computing */
end loop
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Two processes protocol
• One possible execution is the following: the
two processes read and write concurrently
0
15/01/2010
WR 1 WR
RD
RD
Rodolfo Conde and Sergio Rajsbaum
Two processes protocol
• We can represent this execution as a 1simplex
0
15/01/2010
WR 1 WR
RD
RD
Rodolfo Conde and Sergio Rajsbaum
Two processes protocol
• Each vertex represents the process view of the
memory
0
01
15/01/2010
WR 1 WR
RD
RD
01
Rodolfo Conde and Sergio Rajsbaum
Two processes protocol
• Another possible execution: One process is
faster that the other
0
0
01
15/01/2010
WR 1 WR
RD
RD
WR
RD
1
01
Rodolfo Conde and Sergio Rajsbaum
WR
RD
Two processes protocol
• The red process only sees itself, but the green
can see both of them
0
0
01
15/01/2010
WR 1 WR
RD
RD
WR
RD
1
01
Rodolfo Conde and Sergio Rajsbaum
0
WR
RD
Two processes protocol
• And the last possibility
1
WR
0
RD
WR
RD
0
0
01
15/01/2010
WR 1 WR
RD
RD
WR
RD
1
01
Rodolfo Conde and Sergio Rajsbaum
0
WR
RD
Two processes protocol
• And the last possibility
1
WR
0
RD
1
15/01/2010
WR
RD
0
0
01
WR 1 WR
RD
RD
WR
RD
1
01
Rodolfo Conde and Sergio Rajsbaum
0
WR
RD
Protocol complex (1 round)
1
15/01/2010
01
Rodolfo Conde and Sergio Rajsbaum
01
0
The 2nd round
• The input for the 2nd round is any possible
state after the first round
0
WR 1 WR
RD
RD
01
15/01/2010
01
Rodolfo Conde and Sergio Rajsbaum
The 2nd round
• And the three possibilities repeat
0
WR 1 WR
RD
RD
0
WR 1 WR
RD
RD
01
15/01/2010
01
Rodolfo Conde and Sergio Rajsbaum
The 2nd round
• And the three possibilities repeat
0
0
WR
RD
1
WR
WR
1
RD
RD
WR
RD
01
15/01/2010
01
Rodolfo Conde and Sergio Rajsbaum
The 2nd round
• And the three possibilities repeat
0
WR
WR
1
RD
RD
1
0
01
15/01/2010
WR
RD
WR
RD
01
Rodolfo Conde and Sergio Rajsbaum
Two processes protocols in the
iterated model
• Given a possible input:
– Each execution of a round is represented as a 1simplex
– All possible executions are represented as a
simplicial complex (subdivision of a line)
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Three processes protocols
• The state after an execution can be described
by a triangle (2-simplex)
0
WR
WR
0
RD
RD
0
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
WR
RD
Three processes protocols
• The state after an execution can be described
by a triangle (2-simplex)
000
0
WR
WR
0
RD
RD
0
00
00
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
WR
RD
Protocol complex (1st round)
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Protocol complex (1st round)
0
WR
RD
0
0
15/01/2010
WR
RD
WR
RD
Rodolfo Conde and Sergio Rajsbaum
Protocol complex (1st round)
0
0
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
WR
RD
WR
RD
0
WR
RD
Protocol complex (1st round)
0
0
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
WR
RD
WR
WR
0
RD
RD
Protocol complex (1st round)
0
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
WR
WR
WR
0
0
RD
RD
RD
Protocol complex (3 processes)
• For the 2nd round
– Each triangle (state) of the 1st round subdivides in
the same way
– Because we work in an iterated model
– Recursive behaviour
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Rercursive behaviour (2nd round)
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Rercursive behaviour (2nd round)
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Rercursive behaviour (2nd round)
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Protocol complex (2nd round)
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
In general
• For n + 1 processes:
– Each state of a protocol is represented as a nsimplex
– The executions of a protocol are represented as a
n-dimensional complex
– A subdivision of the n-simplex !! [Gafni &
Borowsky]
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The (n,k)-set agreement task
[S. Chaudhuri, 90]
Set agreement
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The (n,k)-set agreement task
[S. Chaudhuri, 90]
2
7
9
Set agreement
15/01/2010
Processes start with
private input values
from a domain I (|I| ≥ n)
Rodolfo Conde and Sergio Rajsbaum
The (n,k)-set agreement task
[S. Chaudhuri, 90]
2
7
9
Their outputs must
agree on at most k < n
distinct values
Set agreement
7
15/01/2010
7
2
Rodolfo Conde and Sergio Rajsbaum
Impossibility of (3,2)-set agreement in
the Iterated model
• We can use the geometric view of distributed
protocols to show this remarkable result.
• The basic idea is as follows:
пѓ�Assume a protocol exists.
пѓ�Find an execution of this protocol (using the protocol
complex) where processes decide 3 values !!!
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Suppose a protocol exists
• Consider an input
where processes have
as input values their
own ids
• Run the protocol until
processes decide
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Suppose a protocol exists
• Because we work in the iterated model
– The protocol complex is a subdivision of the
triangle
– We can colour the vertices with the decision each
process takes
– This colouring satisfies the hypothesis of Sperner’s
Lemma
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
We apply Sperner’s lemma to the
subdivided complex
• By Sperner’s Lemma, at
least one simplex has all
three colours
• This simplex
corresponds to an
execution where
processes decide three
distinct values !!!
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
In summary
• The iterated model
• Executions are represented as simplicial
complexes
• Simple recursive structure
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
In summary
• The set agreement task is impossible to solve
[Borowsky & Gafni, Saks & Zaharoglou, Herlihy
& Shavit, 93]
• The iterated model is equivalent to the usual
read/write model [Borowsky & Gafni, 97]
• Set agreement result is valid in the usual
model (but easier to prove in the iterated
model)
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
We can enrich the Iterated
model with more powerful
objects
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
[Afek, Gafni & Lieber, 09]
Safe-consensus
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
[Afek, Gafni & Lieber, 09]
2
7
9
Safe-consensus
15/01/2010
Processes start with
private input values
from a domain I
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
[Afek, Gafni & Lieber, 09]
2
7
9
Their outputs values
must be the same
Safe-consensus
2
15/01/2010
2
2
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
[Afek, Gafni & Lieber, 09]
2
7
9
The safe-consensus
has two special rules
Safe-consensus
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
[Afek, Gafni & Lieber, 09]
2
7
9
Safe-consensus
(1) If a process starts
executing the task and
outputs before any other
process starts executing
the task
7
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
[Afek, Gafni & Lieber, 09]
2
7
9
the task’s output is that
process proposed input
value.
Safe-consensus
7
15/01/2010
7
7
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
[Afek, Gafni & Lieber, 09]
2
7
9
Safe-consensus
15/01/2010
(2) Otherwise, if two or
more processes initially
access the task
concurrently
Rodolfo Conde and Sergio Rajsbaum
The safe-consensus task
[Afek, Gafni & Lieber, 09]
2
7
9
it can return any value.
(even invalid values)
Safe-consensus
О±
15/01/2010
О±
О±
Rodolfo Conde and Sergio Rajsbaum
What happens if we enrich the
iterated model with safeconsensus tasks ?
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The enriched Model
init r := 0; sm, input, scret, dec := NULL;
loop forever
r := r + 1;
SM[r].write(sm, scret);
scret := safe-consensus[h(sm, scret)](id);
sm := SM[r].snapshot();
/* Local computing */
end loop
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
The enriched Model
init r := 0; sm, input, scret, dec := NULL;
Process access the object
indicated by h(sm, scret)
loop forever
r := r + 1;
SM[r].write(sm, scret);
scret := safe-consensus[h(sm, scret)](id);
sm := SM[r].snapshot();
/* Local computing */
end loop
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
What happens to the protocol
complex ?
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Protocol complex with safe-consensus
• 1 round
• 3 processes
• All processes invoke the
safe-consensus
• Input values: Ids
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Which executions are represented in this
complex ?
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Why do we have only these executions ?
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
WR
SC
RD
WR
SC
RD
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
WR
SC
RD
A closer look
WR
SC
RD
Safe-consensus =
WR
SC
RD
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
WR
SC
RD
A closer look
• Executions where the safe-consensus returns
green
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Why there cannot be more adjacent simplexes
?
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Why there cannot be more adjacent simplexes
?
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Why there cannot be more adjacent simplexes
?
WR
SC
RD
WR
SC
RD
WR
SC
RD
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Why there cannot be more adjacent simplexes
?
Safe-consensus =
WR
SC
RD
WR
SC
RD
WR
SC
RD
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Why there cannot be more adjacent simplexes
?
Safe-consensus =
Safe-consensus =
WR
SC
RD
WR
SC
RD
WR
SC
RD
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Because the safe-consensus does not allow it
Safe-consensus =
Safe-consensus =
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Similar argument for other executions
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Similary for other executions
WR
SC
RD
WR
SC
RD
15/01/2010
WR
SC
RD
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Similary for other executions
Safe-consensus =
WR
SC
RD
WR
SC
RD
15/01/2010
WR
SC
RD
Rodolfo Conde and Sergio Rajsbaum
A closer look
• Similary for other executions
Safe-consensus =
WR
SC
RD
WR
SC
RD
15/01/2010
WR
SC
RD
Rodolfo Conde and Sergio Rajsbaum
Safe-consensus =
A closer look
• Similary for other executions
Safe-consensus =
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Safe-consensus =
A closer look
Safe-consensus =
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
Safe-consensus =
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
Safe-consensus =
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
And the black complex
• It represents executions where the safeconsensus returns an invalid value
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
And the black complex
• At least two processes invoke the safeconsensus concurrently
WR
SC
RD
WR
SC
RD
WR
SC
RD
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
And the black complex
• At least two processes invoke the safeconsensus concurrently
WR
SC
RD
WR
SC
RD
WR
SC
RD
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
A closer look
Safe-consensus = a value
different from valid ids
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
And again…
• Because we work in the iterated model
• In the 2nd round
• This behaviour is going to repeat
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Remember, Iterated model
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Remember, Iterated model
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Remember, Iterated model
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Some results for set agreement
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
(k+1,k)-set agreement is solvable in
this model
proc (k+1,k)-set-agreement(val)
SM.write(val);
sc := safe-consensus(id);
sm := SM.snapshot();
if (sc is in {1, …, k+1} Λ sm[sc] ≠NULL) then
dec := sm[sc];
else
dec := sm[j] with j := min{ m | sm[m] в‰ NULL };
end if
decide dec;
end proc
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Notice
• We omit here the correctness proof of the
protocol
• Not difficult, but tedious
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
In particular
(3,2)-set agreement is solvable in the iterated
model with safe-consensus.
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
In particular
(3,2)-set agreement is solvable in the iterated
model with safe-consensus.
But we can prove that
(3,1)-set agreement (3-consensus) is not
solvable in the Iterated model with safeconsensus.
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Proof’s idea
• Suppose a protocol exists.
• Consider an input where
processes propose their ids
• Take the gray subcomplex
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
In the protocol’s 1st round
WR
SC
RD
WR
SC
RD
15/01/2010
WR
SC
RD
Rodolfo Conde and Sergio Rajsbaum
In the protocol’s 1st round
WR
SC
RD
15/01/2010
WR
SC
RD
Rodolfo Conde and Sergio Rajsbaum
WR
SC
RD
In the protocol’s 1st round
There exists a path here
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
In the protocol’s 2nd round
• And because we work in an iterated model
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
2nd round
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
2nd round
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
2nd round
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
2nd round
WR
SC
RD
WR
SC
RD
15/01/2010
WR
SC
RD
Rodolfo Conde and Sergio Rajsbaum
2nd round
WR
SC
RD
15/01/2010
WR
SC
RD
Rodolfo Conde and Sergio Rajsbaum
WR
SC
RD
2nd round
There’s also a path
…
And so on…
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Because of the iterated model
• In any r-round partial execution:
– a solo execution of
– is “conected” to a execution of
without
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
and
When the protocol finishes
must decide green
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
When the protocol finishes
must decide green
15/01/2010
must decide red or
yellow
Rodolfo Conde and Sergio Rajsbaum
Contradiction
This “connectivity” in all
rounds lead us to a
contradiction, so no such
protocol can exists
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
In general
There is no protocol in the Iterated
Snapshot model with safe-consensus
objects that can solve the (k, 1)-set
agreement problem (k ≥ 3).
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Summary
• There’s a deep conection between Distributed
computing and Topology
• Impossibility results arise from this conection
• We can derive algorithms by looking at the
geometric structure of protocol complexes
• Shared objects can affect the topology of the
protocol complex (safe-consensus)
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Thank you
15/01/2010
Rodolfo Conde and Sergio Rajsbaum
Документ
Категория
Презентации
Просмотров
2
Размер файла
7 055 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа