Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
10
agreement tasks
why is it important?
way of classifying computational power
agreement when k = 1 (consensus) is universal
why is it hard?
failures
processes fail by crashing
(halt and fall silent)
cores & survivor sets are dual:
each can be reconstructed from the other
timing
communication
Intermediate states
Computation proceeds in rounds
Adversary chooses which processes fail,
which take steps
All possible choices define protocol complex
Reasoning about Connectivity
assume protocol complex so far is (k-1)-connected
adversary chooses set of processes to run
set of possible choices defines protocol complex
For how long can the adversary maintain connectivity?
Lower bounds and impossibility results
If always (k-1)-connected,
k-set agreement is impossible
If (k-1)-connected for r rounds,
k-set agreement requires more rounds
If (k-1)-connected for time t,
k-set agreement requires more time
Prior Work
Ad-hoc arguments for each model
Restricted kinds of adversaries
Current Work
Notion of shellable complexes yields unified proof framework
Arbitrary (crash-failure) adversaries
Main Lemma
Main Theorem
Applications
facet
not a facet
1-set agreement
(consensus)
Each triangle is possible set of inputs for 3 processes
Vertex labeled with process id (color) and input value
1-set agreement
(consensus)
they communicate
each process has local input
failures controlled by adversaries
at most k < n inputs chosen
processes can crash
all decide 0
all decide 1
0-connected,
solves 2-set agreement,
not 1-set agreement
1-connected, no 2-set agreement
disconnected,
solves 1-set agreement
combinatorial
topology
simplex representing
global state
complex representing
all possible successor
states
distributed
computing
action of round i
complex of possible round i+1 states
complex of possible round i states
ambiguous which was round's initial state
all process that can distinguish fail before taking a step
[HS99]
Theorem
No protocol can solve k-set agreement if ...
Implication:
We can replace reasoning about computation with reasoning about connectivity
its protocol complex is (k-1)-connected.
crash detection expensive
synchronous
???
crash detection easy
semi-synchonous
asynchronous
crash detection impossible
Shellable Complexes
new results