Без темы
<<  Barbarian to Carolingian Art Battery Charger Design (1S): Key considerations and system design limitations  >>
Chapter 15 Basic Asynchronous Network Algorithms
Chapter 15 Basic Asynchronous Network Algorithms
Outline (15
Outline (15
Leader Election in a Ring
Leader Election in a Ring
AsynchLCR
AsynchLCR
AsynchLCRi automation
AsynchLCRi automation
AsynchLCR Properties
AsynchLCR Properties
AsynchLCRi properties
AsynchLCRi properties
AsynchLCR Complexity
AsynchLCR Complexity
AsynchLCR Complexity
AsynchLCR Complexity
HS Algorithm
HS Algorithm
Peterson Leader-Election Algorithm
Peterson Leader-Election Algorithm
PetersonLeaderi Automation
PetersonLeaderi Automation
PetersonLeaderi Automation
PetersonLeaderi Automation
Peterson Leader Election Example
Peterson Leader Election Example
PetersonLeader Complexity
PetersonLeader Complexity
Peterson Leader-Election Example
Peterson Leader-Election Example
Lower Bound on Communication Complexity
Lower Bound on Communication Complexity
line and ring basics
line and ring basics
Lower Bound on Communication Complexity
Lower Bound on Communication Complexity
Lower Bound on Communication Complexity
Lower Bound on Communication Complexity
Lower Bound on Communication Complexity
Lower Bound on Communication Complexity
Lower Bound on Communication Complexity
Lower Bound on Communication Complexity
Leader Election in an Arbitrary Network
Leader Election in an Arbitrary Network
Leader Election in an Arbitrary Network
Leader Election in an Arbitrary Network
AsynchSpanningTreei automation
AsynchSpanningTreei automation
AsynchSpanningTree
AsynchSpanningTree
AsynchSpanningTree Properties
AsynchSpanningTree Properties
Child Pointers
Child Pointers
AsynchBcastAck
AsynchBcastAck
AsynchBcastAcki automation
AsynchBcastAcki automation
Application to Leader Election
Application to Leader Election

Презентация: «Basic Asynchronous Network Algorithms». Автор: melanie agnew. Файл: «Basic Asynchronous Network Algorithms.ppt». Размер zip-архива: 866 КБ.

Basic Asynchronous Network Algorithms

содержание презентации «Basic Asynchronous Network Algorithms.ppt»
СлайдТекст
1 Chapter 15 Basic Asynchronous Network Algorithms

Chapter 15 Basic Asynchronous Network Algorithms

“Distributed Algorithms” by Nancy A. Lynch

by Melanie Agnew

2 Outline (15

Outline (15

1-15.3)

Leader-Election in a ring LCR Algorithm HS Algorithm Peterson Leader-Election Algorithm general lower bound on communication complexity Leader-Election in an arbitrary network Spanning Tree Construction, Broadcast, Convergecast AsynchSpanningTree Algorithm AsynchBcastAck Algorithm STtoLeader Algorithm

3 Leader Election in a Ring

Leader Election in a Ring

Start: ring of n processes (with UID’s), numbered 1 to n in a clockwise direction processes do not know their indices, nor those of their neighbors processes actions: send, receive, leaderi reliable FIFO send/receive channels between processes Goal: exactly one process eventually produces the leader output

4 AsynchLCR

AsynchLCR

Each process begins by sending its UID to its clockwise neighbor. Each process checks its UID (u) against the one it just received (v), if v > u the process sends v on to the next process If v = u the process is chosen and sends out a leader message

i1 UID=4

I5 UID=1

i2 UID=2

i4 UID=5

i3 UID=3

5 AsynchLCRi automation

AsynchLCRi automation

6 AsynchLCR Properties

AsynchLCR Properties

channels Ci, i+1 are universal reliable FIFO channels with states queuei, i+1 imax is the process with the maximum UID, and umax is its UID Safety ? Lemma 15.1 No process other than imax ever performs a leader output. Assertion 15.1.1 The following are true in any reachable state: If i ? imax and j Є [imax,i), then ui does not appear in sendj . If i ? imax and j Є [imax,i), then ui does not appear in queuej, j+1 . Assertion 15.1.2 The following is true in any reachable state: If i ? imax then statusi = unknown. Liveness ? Lemma 15.2 In any fair execution, process imax eventually performs a leader output. Theorem 15.3 AsynchLCR solves the leader-election problem.

7 AsynchLCRi properties

AsynchLCRi properties

i1 UID=4

I5 UID=1

i2 UID=2

i4 UID=5

i3 UID=3

Assertion 15.1.1: for any process other than i4, ui won’t make it past i4 Assertion 15.1.2: for any process other than i4, status will remain unknown

8 AsynchLCR Complexity

AsynchLCR Complexity

Recall: n = number of processes l = upper bound for each task of each process d = upper bound on delivery time of oldest message in each channel queue The number of messages is: O(n2) Time Complexity: Lemma 15.4 In any fair execution for any r, 0 ? r ? n – 1, and for any i, the following are true: 1. By time r(l+d), UID ui either reaches the sendi+r buffer or is deleted. 2. By time r(l+d)+l, UID ui either reaches queuei+r,i+r+1 or is deleted.

9 AsynchLCR Complexity

AsynchLCR Complexity

r = 0

time to reach send4 = 0

time to reach queue4,5 = l

r = 1

… send5 = l + d

… queue5,1 = l + d + l

r = 2

… send1 = l+d+l+ d

… queue1,2 = l+d+l+d+l

r = 3

… send2 = 3(l+d)

… queue2,3 = 3(l+d)+l

r = n-1

…sendn-1 = (n-1)(l+d)

… queuen-1,n = (n-1)(l+d)+l

…sendn = (n)(l+d)

Theorem 15.6 The time until a leader even occurs in any fair execution is at most n(l+d)+l or O(n(l+d)).

10 HS Algorithm

HS Algorithm

Each process sends exploratory messages in both directions, for successively doubled distances. Communication complexity is O(n log n) In phase 0 there are 4n messages sent. After that a process only sends a message in phase l if it has not been defeated by a message within a distace of 2l-1. So, the max number of processes that initiate messages at phase l is n/(2l-1+1) and the max total number of messages at phase l is 4(2l(n/(2l-1+1)) ? 8n. The total number of phases needed to elect a leader is log n +1 So the total number of messages needed to elect a leader is at most 8n (log n +1) which is O(n log n).

phase

msgs.

0

4

1

8

2

16

l-1

2l-1

l

2l

11 Peterson Leader-Election Algorithm

Peterson Leader-Election Algorithm

Arbitrary election of leader using comparison of UID’s using unidirectional communication Algorithm runs in phases in which each process is assigned to active or relay mode (all processes start as active) The number of active processes is reduced by a factor of two during each phase Summary: At the beginning of each phase each active process i sends its UID two steps clockwise. Then process i compares its own UID to the two UIDs it received. If ui-1 > ui-2 and ui-1 > ui, process i remains active adopting the UID of its counterclockwise neighbor Otherwise process i becomes a relay

12 PetersonLeaderi Automation

PetersonLeaderi Automation

13 PetersonLeaderi Automation

PetersonLeaderi Automation

14 Peterson Leader Election Example

Peterson Leader Election Example

i1 UID=8

i12 UID=7

i2 UID=10

i3 UID=1

i11 UID=9

i10 UID=4

i4 UID=6

i9 UID=5

i5 UID=2

i8 UID=11

i6 UID=3

i7 UID=12

15 PetersonLeader Complexity

PetersonLeader Complexity

Theorem 15.8 The time until a leader even occurs in any fair execution of PetersonLeader is O(n(l+d)). Claim 15.9 If processes i and j are distinct processes that are both active at phase p, then there must be some process k that is strictly after i and strictly before j in the clockwise direction, and such that process k is active at phase p – 1.

16 Peterson Leader-Election Example

Peterson Leader-Election Example

n

Phase 1

Phase 1

Phase 2

Phase 2

Phase 3

Phase 3

Phase 4

Phase 4

1

8

7,9

-

-

-

2

10

8,7

-

-

-

3

1

10,8

10

9,12

-

-

4

6

1,10

-

-

-

5

2

6,1

6

10,9

10

12,10

12

12,12

6

3

2,6

-

-

-

7

12

3,2

-

-

-

8

11

12,3

12

6,10

-

-

9

5

11,12

-

-

-

10

4

5,11

-

-

-

11

9

4,5

-

-

-

12

7

9,4

9

12,6

12

10,12

-

17 Lower Bound on Communication Complexity

Lower Bound on Communication Complexity

Theorem 15.12 Let A be any (not necessarily comparison-based) algorithm that elects a leader in rings of arbitrary size, where the space of UIDs is infinite, communication is bidirectional, and the ring size is unknown to the processes. Then there is a fair execution of A in which ? (n log n) messages are sent.

18 line and ring basics

line and ring basics

P is a universal infinite set of identical process automata (with unique UIDs)

Lines: join(L,M)

Rings: ring(L)

C(?) – number of messages sent in ?. C(L)=sup{C(?): ? is an input free execution of L}

C(R)= sup{C(?):? is an execution of R}

state s of a line is silent if there is no input-free execution fragment starting from s in which any new message is sent

state s of a ring is silent if there is no execution fragment starting with s in which any new message is sent.

19 Lower Bound on Communication Complexity

Lower Bound on Communication Complexity

Lemma 15.13 There is an infinite set of process automata in P, each of which can send at least one message without first receiving any message.

20 Lower Bound on Communication Complexity

Lower Bound on Communication Complexity

Lemma 15.14 For every r ? 0, there is an infinite collection of pairwise-disjoint lines, Lr , such that for every L Є Lr it is the case that |L| = 2r and C(L) ? r2r-2. r = 0, L0 is the set of single node lines, C(L0) = 0 r = 1, L1 is the set of two node lines, C(L1) ? 1 because at least one of the messages must be able to send without first receiving. Assume for r – 1, r ? 2 |L| = 2r-1 and C(L) ? (r – 1)2r-3. let n = 2r. let L, M, and N be any three lines from Lr-1. We consider the six possible joins of these three lines: join (L,M), join(M,L), join(L,N)… Claim 15.15 At least one of these six lines has an input-free execution in which at least n/4 log n = r2r-2 messages are sent.

21 Lower Bound on Communication Complexity

Lower Bound on Communication Complexity

L

M

Claim 15.15 At least one of these six lines has an input-free execution in which at least n/4 log n = r2r-2 messages are sent. Let r = 4 |L| and |M| = 2r-1 = 8 C(?L) and C(?M) ? (r – 1) 2r-3 = (n/8)log(n/2)= 6 Total messages sent so far = 2(n/8)log(n/2) = n/4(log n -1) In order to not contradict our assumption only the first n/4 processes closest to the junction are allowed to take steps, so C(?L,M) < n/4 = 4.

22 Lower Bound on Communication Complexity

Lower Bound on Communication Complexity

23 Leader Election in an Arbitrary Network

Leader Election in an Arbitrary Network

Assume: the underlying graph G = (V, E) is undirected (there is bidirectional communication on all edges) the underlying graph is connected processes are identical except for UID’s How do we know when the algorithm should terminate? Each process that sends a round r message, must tag it with its round number. The recipient waits to receive round r messages from each neighbor before performing its round r transition. So, by simulating diam rounds, the algorithm can terminate correctly. this would require us to send dummy messages between processes that would not otherwise communicate so that a process would know when to enter the next round, but this is inefficient.

24 Leader Election in an Arbitrary Network

Leader Election in an Arbitrary Network

Techniques for optimizing leader election Asynchronous broadcast and convergecast, based on breadth-first search Convergecast using a spanning tree Using a synchronizer to simulate a synchronous algorithm Using a consistent global snapshot to detect termination of an asynchronous algorithm

25 AsynchSpanningTreei automation

AsynchSpanningTreei automation

Page 496

26 AsynchSpanningTree

AsynchSpanningTree

Start with a source node i0, processes do not know the size or diameter of the network, UID’s are not needed. Goal: each process in the network should eventually report via a parent action, the name of its parent in a spanning tree of the graph G. Summary: each non-source process i starts with send = null. When i receives its first search message from a neighbor it sets that neighbor as its parent and sets send = search for all its other neighbors causing search messages to be sent.

27 AsynchSpanningTree Properties

AsynchSpanningTree Properties

Theorem 15.6 The AsynchSpanningTree algorithm constructs a spanning tree. Assertion 15.3.1 In any reachable state, the edges defined by all the parent variables form a spanning tree of a subgraph of G, containing i0; moreover, if there is a message in any channel Ci,j then i is in this spanning tree. Liveness: ? Assertion 15.3.2 In any reachable state, if i = i0 or parenti ? null, and if j Є nbrsi – {i0}, then either parentj or Ci,j contains a search message or sent(j)i contains a search message. Then for any i = i0, parenti ? null within time distance (i0, i) * (l + d) which implies the liveness condition. Complexity: The total number of messages is O(|E|), and all processes except i0 produce parent output within diam(l + d) +l.

28 Child Pointers

Child Pointers

broadcast: each message is sent by i0 to its children, then forwarded from parents to children until it reaches the leaves of the tree The total number of messages is O(n) per broadcast. The time complexity is O(h(l+d)) where h is the height. If the tree is produced with AsynchSpanningTree the time complexity of the broadcast is O(n(l+d)). convergecast: each leaf process sends its information to its parent, each internal process other than i0 waits until it receives its children’s messages and sends all the information to the parent, when i0 receives all its children’s messages it produces the final result. The total number of messages is O(n). The time complexity is O(h(l+d)).

29 AsynchBcastAck

AsynchBcastAck

AsynchSpanningTree can also be extended using broadcast and convergecast messages to allow parents to learn who their children are. AsynchBcastAck summary: i0 initiates a broadcast to all other processes and receives confirmation messages via convergecast Total communication: O(|E|) Time complexity: O(n(l+d))

30 AsynchBcastAcki automation

AsynchBcastAcki automation

31 Application to Leader Election

Application to Leader Election

Asynchronous broadcast and convergecast can be used for leader-election: every node initiates a broadcast-convergecast in order to discover the max UID on the network using O(n|E|) messages. STtoLeader Each leaf node sends an elect message to its unique neighbor If a node receives elect messages from all but one neighbor it sends an elect message to that neighbor If a node receives elect messages from all its neighbors it is the leader If elect messages are sent in both directions on the same edge the one with the greater UID is the leader At most n messages are used in O(n(l+d)) time.

«Basic Asynchronous Network Algorithms»
http://900igr.net/prezentacija/anglijskij-jazyk/basic-asynchronous-network-algorithms-105945.html
cсылка на страницу

Без темы

661 презентация
Урок

Английский язык

29 тем
Слайды