Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

DA > content > Flashcards

content Flashcards

1
Q

Best-effort broadcast (beb)

A

Uses perfect link

  • Request : bebBroadcast, m
  • Indication : bebDelilver, src, m

• BEB1. Validity : If pi and pj are correct then every message broadcast by pi
is eventually delivered
by pj
• BEB2. No duplication : No message is delivered more than once
• BEB3. No creation : No messages is delivered unless it was broadcast

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Reliable broadcast (rb)

A

Uses BeB, perfect failure detector

Properties
RB1 = BEB1.
RB2 = BEB2.
RB3 = BEB3.
RB4. Agreement: For any message m, if
any correct process delivers m, then every
correct process delivers m
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Uniform broadcast (urb)

A

uses BEB, P

  • Request :
  • Indication :
Properties
URB1 = BEB1.
URB2 = BEB2.
URB3 = BEB3.
URB4. Uniform Agreement: For any
message m, if any process delivers m, then
every correct process delivers m
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Causality

Let m1 and m2 be any two messages: m1 -
> m2 (m1 causally precedes m2) iff

A

C1 (FIFO order). Some process pi
broadcasts m1 before broadcasting m2

C2 (Local order). Some process pi delivers
m1 and then broadcasts m2

C3 (Transitivity). There is a message m3
such that m1 -> m3 and m3 - > m2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Causal broadcast

A

Request :
• Indication :

• Property:

• CO: If any process pi delivers a message
m2, then pi must have delivered every
message m1 such that m1 -> m2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Reliable causal broadcast (rcb)

A

uses rb

Request :
• Indication :

• Properties:

  • RB1, RB2, RB3, RB4 +
  • CO
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Uniform causal broadcast (ucb)

A

Uses urb

Request :
• Indication :

• Properties:

  • URB1, URB2, URB3, URB4 +
  • CO
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Total order broadcast (tob)

A

uses rb, consensus

Request :
• Indication :

• Properties:
• RB1, RB2, RB3, RB4
• Total order property : Let m and m’ be any two messages.
Let pi be any (correct) process that delivers m
without having delivered m’
Then no (correct) process delivers m’ before m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Consensus properties

A 
C1. Validity: Any value decided is a value
proposed
C2. Agreement: No two correct processes
decide differently
C3. Termination: Every correct process
eventually decides
C4. Integrity: No process decides twice
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Uniform consensus - properties

A 
C1. Validity: Any value decided is a value
proposed
C2. Uniform Agreement: No two
processes decide differently
C3. Termination: Every correct process
eventually decides
C4. Integrity: No process decides twice
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Consensus - inteface

A
  • Request : Propose, v

* Indication : Decide, v’

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Beb interface

A
  • Request : bebBroadcast, m

* Indication :bebDelilver, src, m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

RB - interface

A
  • Request : rbBroadcast, m

* Indication : rbDeliver, src, m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

URB interface

A
  • Request : urbBroadcast, m

* Indication : urbDeliver, src, m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

rcb - interface

A
  • Request : rcoBroadcast, m

* Indication : rcoDeliver, src, m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

UCB - interface

A
  • Request : ucoBroadcast, m

* Indication : ucoDeliver, src, m

17
Q

TOB - interface

A
  • Request : toBroadcast, m

* Indication : toDeliver, src, m

18
Q

ACID properties

A

Atomicity: a transaction either performs entirely or none at all
Consistency: a transaction transforms a consistent state into
another consistent state
Isolation: a transaction appears to be executed in isolation
Durability: the effects of a transaction that commits are
permanent

19
Q

Nbac interface

A

Uses beb, P, uniCons

Request : Propose, v
Indication : Decide, v’

20
Q

nbac properties

A

NBAC1. Agreement : No two processes decide differently
• NC1C2. Termination : Every correct process eventually decides
• NBAC3. Commit-Validity : 1 can only be decided if all process propose 1
• NBAC4. Abort-Validity : 0 can only be decided if some process crashes of votes 0

21
Q

Group Membership - properties

A

Memb1. Local Monotonicity: If a process installs view
(j,M) after installing (k,N), then j > k and M < N

Memb2. Agreement: No two processes install views
(j,M) and (j,M’) such that M ≠ M’

Memb3. Completeness: If a process p crashes, then
there is an integer j such that every correct process
eventually installs view (j,M) such that p not in M

Memb4. Accuracy: If some process installs a view (i,M)
and p not in M, then p has crashed

22
Q

Group Membership - interface

A

Uses:
PerfectFailureDetector (P).
UniformConsensus(Ucons).

Events
Indication: membView, V

23
Q

View Synchrony broadcast - interface

A

Uses:
GroupMembership (gmp).
TerminatingReliableBroadcast(trb).
BestEffortBroadcast(beb).

Request:
vsBroadcast, m; vsBlock, ok
Indication:
vsDeliver, src, m; vsView, V; vsBlock

24
Q

TRB - interface

A

Uses:
BestEffortBroadcast (beb).
PerfectFailureDetector (P).
Consensus(cons).

Events
Request: trbBroadcast, m
Indication: trbDeliver, p, m

25
Q

TRB - properties

A

TRB1. Integrity: If a process delivers a message m, then
either m is j or m was broadcast by src
TRB2. Validity: If the sender src is correct and broadcasts a
message m, then src eventually delivers m
TRB3. (Uniform) Agreement: For any message m, if a
correct (any) process delivers m, then every correct process
delivers m
TRB4. Termination: Every correct process eventually delivers
exactly one message

26
Q

Fair-loss links - properties

A

FL1. Fair-loss: If a message is sent infinitely
often by pi to pj , and neither pi or pj crashes,
then m is delivered infinitely often by pj

FL2. Finite duplication: If a message m is sent
a finite number of times by pi to pj, m is delivered
a finite number of times by pj

FL3. No creation: No message is delivered unless
it was sen

27
Q

Stubborn links - properties

A

SL1. Stubborn delivery: if a process pi sends a
message m to a correct process pj, and pi does not
crash, then pj delivers m an infinite number of times
SL2. No creation: No message is delivered unless
it was sent

28
Q

Perfect Link - properties

A 
PL1. Validity: If pi and pj are correct,
then every message sent by pi to pj is
eventually delivered by pj
PL2. No duplication: No message is
delivered (to a process) more than once
PL3. No creation: No message is
delivered unless it was sent
29
Q

Failure Detection -interface

A

Events

Indication: crash, p

30
Q

perfect Failure detec - properties

A

Strong Completeness: Eventually, every process that
crashes is permanently suspected by every correct process

Strong Accuracy: No process is suspected before it crashes

31
Q

Eventually perfect Failure detec

A

Strong Completeness
Eventual Strong Accuracy: Eventually, no correct process is
ever suspected

DA (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions