Derive a formula for worst-case message complexity of algo

Assignment Help Data Structure & Algorithms

Reference no: EM13912626

The aim of this exercise is to investigate the effect of selective delays in Archimedean networks. Let a network be given with Archimedean ratios.

Election is performed by applying extinction to a traversal algorithm with message complexity W. Each message of process p is delayed by f (p) - 1 clock ticks in each process. A separate wake-up procedure ensures that each process launches its traversal within Du time units after the start of the algorithm.

(1) Prove that the algorithm terminates within D.u + W.u.f (po ) time units, where Po is the process with the smallest identity.

(2) Prove that the token of process p is sent at most 1 + t/ (f (p) - 2) times during a time interval of length t.

(3) Derive a formula for the worst-case message complexity of the algo rithm.

(4) Show, by varying f, that a linear message complexity can be obtained.

Text Book: Introduction to Distributed Algorithms By Gerard Tel.

Reference no: EM13912626

Questions Cloud

Prove that a neighbor of a node of level f in the bfs tree : Prove that a neighbor of a node of level f in the BFS tree has level f - 1, f, or f + 1. Analyze the complexity of the breadth-first search algorithms in terms of N, lEI, and D (the network diameter).

What was the purpose of the research : Read the following empirical research article: Eskew Faley -- Some determinants of student performance in the first college-level financial accounting course What was the purpose of the research? Who were the subjects? What were the variables? Wha..

Resistance been absent : In 1948 he jumped from rest from the top of the Vegas World Hotel and Casino. He struck the airbag at a speed of 39 m/s (88 mi/h). To assess the effects of air resistance, determine how fast he would have been traveling on impact had air resistanc..

Four seasons industries has established direct labor : Four Seasons Industries has established direct labor performance standards for its maintenance and repair shop.

Derive a formula for worst-case message complexity of algo : Derive a formula for the worst-case message complexity of the algo rithm. Show, by varying f, that a linear message complexity can be obtained.

Program for the training lathes to produce a chess piece : Create a CNC program for the attached drawing use a 8.0 mm diameter tool - Use the cutter compensation and method of your choice - Create a listing of your program

Compute a 3-month moving average forecast : Compute a 3-month moving average forecast for months 4 through 9. Compute a weighted 3-month moving average forecast for months 4 through 9. Assign weights of 0.55, 0.35, and 0.10 to the months in sequence, starting with the most recent month

Direct material variances solving for price and usage : Direct material variances solving for price and usage variances.

Different methods of inventory accounting : Create a balance sheet from a trial balance-Create a comparison of net income based on different methods of inventory accounting.

User Account

All Pages