Question

Show that with sufficiently many n-thread binary consensus objects and atomic registers one can implement n-thread...

Show that with sufficiently many n-thread binary consensus objects and atomic registers one can implement

n-thread consensus over n possible values. That is show that you can construct a an n-thread multivalue consensus object where there are only n possible values.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Solution:--------
We agree on the value one bit at a time.The threads share an n-element array of atomic registers, and an array of log2n consensus objects.
Each thread announces its input in a shared array of atomic registers. At any time each thread has a preference, the value it is trying to convince the others to decide. Initially, each thread’s preferences is its input.
At round i, each thread uses the ith bit of its preference as input to the i-th binary consensus object. If it wins, it continues to the i+1 consensus with the same preference. If it loses, it scans the announcement array for an input that agrees with all the binary values decided in prior consensus rounds, and uses that value for its preference.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Please answer in JAVA IDS 401 Assignment 4 Deadline In order to receive full credit, this...
Please answer in JAVA IDS 401 Assignment 4 Deadline In order to receive full credit, this assignment must be submitted by the deadline on Blackboard. Submitting your assignment early is recommended, in case problems arise with the submission process. Late submissions will be accepted (but penalized 10pts for each day late) up to one week after the submission deadline. After that, assignments will not be accepted. Assignment The object of this assignment is to construct a mini-banking system that helps...
Atomic interactions can be modeled using a variety of potential energy approximations. One very common potential...
Atomic interactions can be modeled using a variety of potential energy approximations. One very common potential form is the Lennard-Jones 6:12 potential: U(r)=4ε[(σ/r)12 − (σ/r)6]. Where ε and σ are constants specific to a given material (note: these terms are NOT equivalent to stress and strain, but this is the standard notation for the L-J parameters). Here, r is the interatomic spacing given in units of Angstroms, and U(r) is given in units of eV/atom. A molecular dynamics simulation was...
For this assignment, design and implement a class to represent a die (singular of "dice"). A...
For this assignment, design and implement a class to represent a die (singular of "dice"). A normal bag of dice for playing Dungeons and Dragons, for example, contains dice with the following numbers of sides: 4, 6, 8, 10, 12, 20, and 100. In this program, the sides (or faces) of the die are numbered, starting with one. The current face value of the die corresponds to the side that is currently facing upward. By default, the face value is...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally. 1. Theory. A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps. You can test if...
Hello, can you please be sure to show all work and I'll be sure to give...
Hello, can you please be sure to show all work and I'll be sure to give a thumbs up rating? Thanks!! <3 xxoo Ashley Mean of stock price = 1117.64 STDEV (Population) = 67.61 If a person bought 1 share of Google stock within the last year, what is the probability that the stock on that day closed within $50 of the mean for that year (round to two places)? (Hint: this means the probability of being between 50 below...
II(20pts). Short Problems a) The lowest energy of a particle in an infinite one-dimensional potential well...
II(20pts). Short Problems a) The lowest energy of a particle in an infinite one-dimensional potential well is 4.0 eV. If the width of the well is doubled, what is its lowest energy? b) Find the distance of closest approach of a 16.0-Mev alpha particle incident on a gold foil. c) The transition from the first excited state to the ground state in potassium results in the emission of a photon with  = 310 nm. If the potassium vapor is...
Here's the requirement. Write a client program Subset.java that takes a command-line integer k , reads...
Here's the requirement. Write a client program Subset.java that takes a command-line integer k , reads in a sequence of strings from standard input using StdIn.readString() , and prints out exactly k of them, uniformly at random. Each item from the sequence can be printed out at most once. You may assume that 0 k N , where N is the number of string on standard input. The running time of the program must be linear in the size of...
Create in JAVA Suppose you are designing a game called King of the Stacks. The rules...
Create in JAVA Suppose you are designing a game called King of the Stacks. The rules of the game are as follows:  The game is played with two (2) players.  There are three (3) different Stacks in the game.  Each turn, a player pushes a disk on top of exactly one of the three Stacks. Players alternate turns throughout the game. Each disk will include some marker to denote to whom it belongs.  At the end...
Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b,...
Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b, where a – b is equal to a given number. For example, consider the following array and suppose we want to find all pairs of integers a and b where a – b = 3 A = [10, 4, 6, 16, 1, 6, 12, 13] Then your method should return the following pairs: 4, 1 15, 12 13, 10 A poor solution: There are...
Design a FSM for a Vending Machine In this task, you will design a FSM for...
Design a FSM for a Vending Machine In this task, you will design a FSM for a simple (albeit strange) vending machine of office supplies. The vending machine sells three possible items, each at a different cost: Item Cost Pencil 10 cents Eraser 20 cents Pen 30 cents The vending machines accepts nickels (worth 5 cents), dimes (worth 10 cents), and quarters (worth 25 cents). Physically, it is only possible to insert a single coin at a time. The vending...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT