text:
# Kirchhoff migration

Series Geophysical References Series Problems in Exploration Seismology and their Solutions Lloyd P. Geldart and Robert E. Sheriff 9 295 - 366 http://dx.doi.org/10.1190/1.9781560801733 ISBN 9781560801153 SEG Online Store

## Problem 9.27a

Prove that the equation of a diffraction curve (see Figure 9.27a) is

{\displaystyle {\begin{aligned}z^{2}-x^{2}=z_{0}^{2},\end{aligned}}}

where ${\displaystyle z_{0}}$ is the depth of the diffracting point (assuming constant velocity).

### Background

Migration is the process of repositioning reflection data so that reflection events are located where the reflector in the subsurface is, as shown in Figure 9.27a. ${\displaystyle S_{0}}$, ${\displaystyle S_{1}}$, ${\displaystyle S_{2}}$, ..., are a series of coincident sources and receivers and ${\displaystyle P}$ is a diffracting point on a plane reflector ${\displaystyle PQ}$. The data recorded at ${\displaystyle S_{0}}$ are ordinarily plotted directly below ${\displaystyle S_{0}}$ before migration is performed. If the velocity is constant, the reflection from ${\displaystyle P}$ that is observed at ${\displaystyle S_{0}}$ appears on the ${\displaystyle S_{0}}$ trace at ${\displaystyle M}$, and the reflection point must lie on a circle through ${\displaystyle M}$ centered at ${\displaystyle S_{0}}$. The circles such as ${\displaystyle PM}$ are wavefronts and radii such as ${\displaystyle S_{0}P}$ are raypaths which are orthogonal to the respective wavefronts.

### Solution

The locus of point M as the source and coincident receiver are moved is a diffraction curve (see Figure 6.5a). If O is the origin and the coordinates of ${\displaystyle M}$ are (${\displaystyle x,z}$), then, because ${\displaystyle S_{0}P=S_{0}M}$.

 {\displaystyle {\begin{aligned}z^{2}=x^{2}+z_{0}^{2},\quad \mathrm {so} \quad z^{2}-x^{2}=z_{0}^{2}.\end{aligned}}} (9.27a)

## Problem 9.27b

Show that an unmigrated reflection is tangent to the diffraction curve.

### Solution

We find the equation of an unmigrated reflection ${\displaystyle MN}$ (Figure 9.27a) and determine its slope, then find the slope of the diffraction curve and show that the point where the slope of the diffraction curve is the same as that of ${\displaystyle MN}$ is also on ${\displaystyle MN}$. To get the equation of ${\displaystyle MN}$, we need the equation of the reflector ${\displaystyle PQ}$ because it meets ${\displaystyle MN}$ at the outcrop on the ${\displaystyle x}$-axis.

The line ${\displaystyle PQ}$ passes through ${\displaystyle P(0,\;z_{0})}$ with slope ${\displaystyle {\rm {\;tan\;}}\xi }$, where ${\displaystyle \xi }$ is the dip, so its equation is

 {\displaystyle {\begin{aligned}z=x{\rm {\;tan\;}}\xi +z_{0}.\end{aligned}}} (9.27b)
Figure 9.27a.  Intersecting wavefronts.

This line outcrops (that is, at ${\displaystyle z=0}$) at ${\displaystyle x=-z_{0}{\rm {\;cot\;}}\xi }$ , and ${\displaystyle MN}$ passes through the point ${\displaystyle (-z_{0}{\rm {\;cot\;}}\xi ,\;0)}$ as well as the point ${\displaystyle M}$, whose coordinates are ${\displaystyle x=z_{0}{\rm {\;tan\;}}\xi }$, ${\displaystyle z=S_{0}M=S_{0}P=z_{0}/{\rm {\;cos\;}}\xi }$. The equation of ${\displaystyle MN}$ now becomes

 {\displaystyle {\begin{aligned}{\frac {z-z_{0}/\cos \xi }{x-z_{0}{\tan \xi }}}={\frac {z_{0}/\cos \xi }{z_{0}\tan \xi +z_{0}\cot \xi }}={\frac {1}{\sin \xi +\cos ^{2}\xi /\sin \xi }}=\sin \xi .\\{\mbox{Thus}}\qquad \qquad z&=z_{0}/\cos \xi +x\sin \xi -z_{0}\tan \xi \sin \xi \\&=x\sin \xi +z_{0}\cos \xi ,\end{aligned}}} (9.27c)

and the slope of ${\displaystyle MN}$ is ${\displaystyle {\hbox{d}}z/{\hbox{d}}x={\rm {\;sin\;}}\xi }$.

The slope of the diffraction curve in equation (9.27a) is ${\displaystyle {\hbox{d}}z/{\hbox{d}}x=x/z}$, so we need to find a point on the curve in equation (9.27a) where this slope equals that of ${\displaystyle MN}$, that is, where ${\displaystyle x/z=\sin \xi }$. Substituting this value of ${\displaystyle x}$ in equation (9.27a) gives

{\displaystyle {\begin{aligned}z^{2}-(z\sin \xi )^{2}=z_{0}^{2},\quad \mathrm {so} \quad z=z_{0}/\cos \xi ,x=z_{0}\tan \xi .\end{aligned}}}

We now substitute these coordinates in equation (9.27c) to show that they satisfy the equation of ${\displaystyle MN}$. Thus,

{\displaystyle {\begin{aligned}z_{0}/\cos \xi =(z_{0}\tan \xi )\sin \xi +z_{0}\cos \xi \;,\;1=\sin ^{2}\xi +\cos ^{2}\xi ;\end{aligned}}}

therefore, the diffraction curve and ${\displaystyle MN}$ both pass through this point and, since they have only one common point, ${\displaystyle MN}$ must be a tangent.

## Problem 9.27c

Show that the coordinates of ${\displaystyle P}$ and the slope of the wavefront at ${\displaystyle P}$ (hence also the dip ${\displaystyle \xi }$) can be obtained from the recorded data.

### Solution

Assuming that the seismic line is normal to strike, we obtain ${\displaystyle z_{0}}$ from the minimum value of the traveltime ${\displaystyle t_{0}}$, which occurs when the source is directly over ${\displaystyle P}$; this fixes the ${\displaystyle x}$-coordinate of ${\displaystyle P}$. If the velocity is constant, by swinging an arc with center at any source and radius ${\displaystyle {\frac {1}{2}}Vt_{0}}$ and then drawing the tangent from ${\displaystyle P}$ to the arc, we get the dip ${\displaystyle \xi }$.

## Problem 9.27d

How will parts (a), (b), and (c) change if the velocity changes in the vertical direction (e.g., if it increases with depth)?

### Solution

In this case the raypath will curve, a wavefront may not be the arc of a circle, the diffraction curve will no longer be a hyperbola, an unmigrated reflection will still be tangent to the diffraction curve, and locating the reflecting point will be more complicated. However, assuming that a diffraction curve is hyperbolic often results in solutions that are close enough to be useful and most data processing makes this assumption.

format: plain


text:
Not logged in [Login ]
 Sciencemadness Discussion Board » Fundamentals » Beginnings » How can I make niric acid? Select A Forum Fundamentals   » Chemistry in General   » Organic Chemistry   » Reagents and Apparatus Acquisition   » Beginnings   » Responsible Practices   » Miscellaneous   » The Wiki Special topics   » Technochemistry   » Energetic Materials   » Biochemistry   » Radiochemistry   » Computational Models and Techniques   » Prepublication Non-chemistry   » Forum Matters   » Legal and Societal Issues

Author: Subject: How can I make niric acid?
tinker Terry
Harmless

Posts: 3
Registered: 17-5-2013
Location: Marysville B.C. Canada
Member Is Offline

Mood: No Mood

How can I make niric acid?

I need nitric acid for a project I am working on and cannot find a local supplier. is there a reasonably simple way to make it at home with minimum expense and rudimentary equipment?

Curiosity may have killed the cat but it put mankind on the moon.
binaryclock
Hazard to Others

Posts: 121
Registered: 9-4-2013
Member Is Offline

Mood: Organic

You really want nitric acid? That is some of the nastiest stuff I've ever encountered.

Even with a proper distillery kit, it is still a real big PITA. Even if you successfully create nitric acid, even storing it is a big problem as well. You have to store it in an all glass container. Nitric will eat rubber and most things without any trouble.

BTW, you are in the same boat as I. Local suppliers will not give it to you because it is a chemical listed in the explosives act of Canada. What do you need it for? There are many good uses for nitric acid but sometimes you can use alternatives.

Anyways, see nurdrage's video regarding nitric acid if you really still want to make it: http://www.youtube.com/watch?v=2yE7v4wkuZU

If distillery is your choice of synthesis, another good video is this: http://www.youtube.com/watch?v=nRKAP7v3cv4

[Edited on 18-5-2013 by binaryclock]

[Edited on 18-5-2013 by binaryclock]

Current Project: Playing with my new Laboy advanced distillery kit!
weiming1998
International Hazard

Posts: 616
Registered: 13-1-2012
Location: Western Australia
Member Is Offline

Mood: Amphoteric

Here is a step-by step guide to find a simple way of making nitric acid:
1, Type www.google.com into the address bar.
2, Type "how to make nitric acid" into the search engine. Add "sciencemadness" at the end if you want to search this website.
3, ???
4, PROFIT

In other words, there is something called a search engine. Use it.

[Edited on 18-5-2013 by weiming1998]
plante1999
International Hazard

Posts: 1937
Registered: 27-12-2010
Member Is Offline

Mood: Mad as a hatter

If you lived nearer to me, I would have sold you some. Nitric is not that bad at 70% conc. Stored in a polypropylene lined/caped bottle, nothing is corroded/leak. He is better to fallow magpie procedure in the prepublication sub forum. Else he will get acid too concentrated and contaminated with NOx. And then, he still need to find KNO3.

I never asked for this.
vmelkon
International Hazard

Posts: 669
Registered: 25-11-2011
Member Is Offline

Mood: autoerotic asphyxiation

Nitric acid can be purchased in Canada from specialty shops dedicated for plant growing. Search for hydroponics. It was 24$for 500 mL or 1 L I think. It is very expensive. In some countries, it is 1 to 5$.
You can also buy a 25 Kg bag of Ca(NO)2 from such places.
I have produced some nitric acid acid using a high voltage circuit from a TV and air. The NO2 dissolves in water and makes HNO3 and NO. The NO reacts with O2 to make NO2 again. I made 0.93 M HNO3 this way, impure.
AJKOER

Posts: 3016
Registered: 7-5-2011
Member Is Offline

Mood: No Mood

I have not entirely performed this procedure myself, but you may consider and test it yourself for comparative purposes of cost and convenience for preparing Nitric acid if you do not have a nitrate or nitrite salt. Generally speaking, starting with a nitrate is a lower cost and more direct approach.

My suggested synthesis without a nitrate is as follows: first, add a copper source (copper plated pennies, etc.) in excess to a container along with an excess of aqueous ammonia (dilute or concentrated). Let stand for awhile and then add H2O2 (even dilute will work). Having performed this part, I can tell you that an obvious gas formation occurs on the surface of the copper and the solution temperature rises. A dark blue colored complex is formed and more gas (including N2) is evolved on standing, so do not seal your reaction vessel. A large sudden rapid spontaneous gas evolution is also possible (take precautions, see below).

Next step (untried by myself but confirmed) upon formation of the dark blue complex (this should occur relatively fast, but does vary depending on the concentration of your NH3 and H2O2) react with either H2SO4 and FeSO4 to produce NO (and NO2 in the presence of air). Let the NO2 dissolve in water or dilute H2O2 and further treat with air to form pure HNO3. One may be able to substitute NaI and Acetic acid with mild heating to 55 C for H2SO4 and FeSO4 to produce the Nitrous oxide (see "Effects of reducing reagents and temperature on conversion of nitrite and nitrate to nitric oxide and detection of NO by chemiluminescence", by Fan Yang, Eric Troncy, Martin Francœur, Bernard Vinet, Patrick Vinay, Guy Czaika and Gilbert Blaise, where the full paper is available free at http://www.clinchem.org/content/43/4/657.full although NaI/ Acetic acid is apparently not effective on liberating NO from any formed nitrates, only nitrites).

Chemistry source, see http://www.sciencemadness.org/talk/post.php?action=reply&... , to quote:

Apparent weaknesses of this synthesis is that the key reaction of nitrite formation is a side reaction and, depending on reactant concentrations and time to addition of the H2SO4/FeSO4, yield could vary significantly. In addition, any NH4NO2 created is prone with time (possibly hours) to decomposition to N2, which could occur slowly, or possibly very rapidly including explosively especially on acidification of a concentrated solution (see Wikipedia on NH4NO2 at http://en.wikipedia.org/wiki/NH4NO2 and other MSDSs as well). The latter should restrict this preparation to small (or dilute) quantities only of HNO3.

Strengths of the synthesis include no need for a starting nitrate or nitrite salt or sophisticated equipment. The reactants are relatively available and inexpensive, and the reaction speed, depending on starting concentrations, is relatively rapid. There is also the possibility for alterations of the procedure to increase safety (like focusing on nitrate, and not nitrite, formation) and yield (like monitoring pH, varying and monitoring the temperature, concentration and reaction times including, for example, when to add Acetic acid/NaI, or H2SO4/FeSO4, for NO/NO2 creation). Employing electrolysis may also be able to increase yield and safety by increasing the formation of nitrates from nitirites by avoiding the addition of strong bases like NaOH. Source, here is an old paper on the electrolysis of aqueous ammonia in the presence of NaOH and, separately, Cu(OH)2 from 1905 (see page 242 at http://books.google.com/books?pg=PA242&lpg=PA242&dq=... from Journal Chemical Society, London, Volume 88, Part 2), to quote:

"Electrolytic Oxidation of Ammonia to Nitrites. Erich Muller and Fritz Spitzer (Ber., 1905, 38, 778—782. Compare Traube and Biltz, Abstr., 1904, ii, 727).—In the presence of a small amount of sodium hydroxide, ammonia may be oxidised electrolytically to nitrite even in the absence of copper compounds.

In the presence of copper hydroxide and sufficient alkali, the oxidation of ammonia to nitrite does not cease suddenly when the nitrite concentration has reached a certain value, but appears to proceed quite independently of the nitrite concentration. In these experiments, the oxidation was allowed to proceed for a comparatively short time only, so that the amount of alkali present was not greatly reduced. The formation of nitrite is intimately connected with the amount of alkali present, and when no sodium 'hydroxide is present, but only ammonia, nitrite, and copper hydroxide, it is found that the nitrite is transformed into nitrate more rapidly than the ammonia into nitrite, and thus the concentration of the nitrite tends to decrease.

Nitrogen is also formed during the oxidation. J. J. S."

Bottomline, while this synthesis may be doable as is, it more likely requires some work to address safety and yield considerations.

[Edited on 31-5-2013 by AJKOER]
chemcam
National Hazard

Posts: 423
Registered: 18-2-2013
Location: Atlantis
Member Is Offline

Mood: I will be gone until mid-september, on a work contract.

AJ, holy cow man the OP asked for minimum expense. With your procedure he is going to have to buy quite a few reagents.. There may be some place for these off the wall synths but I am beginning to get frustrated because they are in just about every thread and most the time not even what the OP wants.

I am sure you take great pride in your untested procedures and take the time to write them happily but It doesn't seem like anybody ever agrees with what you say or even tests them out. I am not trying to be mean but maybe you should invest your time performing these experiments you design instead of preaching them.

I 99.98% guarantee that a nitrate salt and H2SO4 is the cheapest method other than a bulk purchase of HNO3.

IRC Channel: #sciencemadness @ irc.efnet.org
AJKOER

Posts: 3016
Registered: 7-5-2011
Member Is Offline

Mood: No Mood

Chemcam:

Thanks, I have revised my opening sentence as I do not make clear that my suggested synthesis chiefly addresses the issue of what to do with ones H2SO4 absent a nitrate or nitrite.

I also agree with your assessment that a nitrate salt and H2SO4 is the cheapest method assuming that one has the necessary equipment for the distillation. Those without such sophistications, adding Oxalic acid to NaNO3, IMHO, works much more easily and safely for a not too concentrated solutions (my recommendation based on working with H2C2O4 on acid salts to form various acids) for albeit a slightly greater expense.

Now, the availability and purity of the nitrate is, of course, still a possible issue for some.

As I completely disclosed with my thread extract, when I original peformed the first half of the reaction, the intent was not the formation of a nitrite or nitrate, but just a cupric salt. There is also a prior thread on Sciencemadness noting the formation of NH4NO2 (per the oxidation of aqueous ammonia) and testing it with H2SO4/FeSO4 that apparently forms some NO2 (yield is still an open question, please see http://www.sciencemadness.org/talk/post.php?action=reply&... to quote:

Quote: Originally posted by Formatik
...
 Quote: Under what conditions can ammonia be oxidized to NH4NO2 ?

The Ber. ref. from Hoppe-Seyler describes it. Namely, strong solutions of H2O2 with a few drops of NH4OH or solutions of ammonium carbonate (with or without NaOH or Na2CO3) can be let to stand 24 hours without any nitrite formation occurring. But upon longer standing, even with a small amount of hydroxide then nitrite forms. Nitrite also forms when a dilute solution of H2O2 is mixed with NH4OH and a little Na2CO3 and is evaporated over pure conc. H2SO4 with a bell jar.

H2O2 forms (even in very dilute solutions) nitrite very rapidly, if the H2O2 solution is mixed with a few drops of NH4OH and a little NaOH or Na2CO3, and this then boiled in a retort to a very small volume. They suggest this nitrite formation as a demonstration experiment because it is very quick to do, and then after acidification of the colorless liquid with H2SO4, the HNO2 can be nicely be proven to be present.

So your implication that this is some entirely untried theorical based reaction is not quite correct. What I am guilty of, I fully admit, is perhaps overdoing the theory of the chemistry, and I do so when scholars will be reluctant to do so for reactions where the mechanics are not completely understood (as was the case for the action of aqueous ammonia and air on copper where there was at least 3 theories on the reaction path as of 1962).

Those interesting in exploring the extended procedure to HNO3 because of availability issues of nitrates, or commenting per their experience on suggested modifications, or theoretically finding the reaction interesting, are all welcomed. Personally, I find the very possibility of making Nitric acid from copper, household ammonia, dilute hydrogen peroxide, acetic acid and sodium iodide (with the latter two reactant, the focus is on nitrite formation, so also add a little NaOH) as just cool, irrespective of cost or yield.

[Edited on 1-6-2013 by AJKOER]
Metacelsus
International Hazard

Posts: 2508
Registered: 26-12-2012
Location: Boston, MA
Member Is Offline

Mood: Double, double, toil and trouble

He could also make it in a Birkeland-Eyde reactor using just air, water, and electricity.

As below, so above.
chemcam
National Hazard

Posts: 423
Registered: 18-2-2013
Location: Atlantis
Member Is Offline

Mood: I will be gone until mid-september, on a work contract.

AJ, I was in a bad mood earlier from something else but I have since taken a chill pill. All I was meaning is that the OP asked for a simple and cheap way to make nitric acid. What you posted seemed much too complex and inefficient for someone who asks how to make HNO3 for the first time.

I have always had the impression that using copper metal as a reagent for making nitric acid is expensive and inefficient. Maybe when all nitrates have been banned your method will shine. And yes, someone who is looking for novel ways to HNO3 without a nitrate salt could benefit from what you said I just didn't think a beginner would go through all the trouble of acquiring the needed chemicals when easier ways exist.

Are you sure OTC 3% H2O2 and OTC 7% NH4OH w/ Cu will work? How fast is gas evolved? I would test it myself but I literally have no copper metal right now.

IRC Channel: #sciencemadness @ irc.efnet.org
AJKOER

Posts: 3016
Registered: 7-5-2011
Member Is Offline

Mood: No Mood

 Quote: Originally posted by chemcam .... Are you sure OTC 3% H2O2 and OTC 7% NH4OH w/ Cu will work? How fast is gas evolved? I would test it myself but I literally have no copper metal right now.

I used local US currency pennies which are actually Copper plated with a Zinc core. I am not worried about the Zn as I have read that a catalyst for the oxidation of ammonia by H2O2 one can use Zn powder, NaOH, Na2CO3,...

I could describe the reaction between Cu and dilute ammonia and H2O2, but best believed with ones own eyes. The nice feature of employing Cu is the reaction forms a colorful azure solution.

Note, for those wishing to comply with local laws (as I do), removing and changing coins avoids any Zinc contamination, preserves the coins and thoroughly cleans them.

Please read all the my caution warnings. Ammonium nitrite is also actually quite toxic on ingestion.

[Edited on 1-6-2013 by AJKOER]
plante1999
International Hazard

Posts: 1937
Registered: 27-12-2010
Member Is Offline

Mood: Mad as a hatter

Here is a flowchart showing all the reasonable way to make nitric acid I come up with. It may help people stop asking questions about "how to make nitric acid":

I never asked for this.
AJKOER

Posts: 3016
Registered: 7-5-2011
Member Is Offline

Mood: No Mood

Plante1999:

May I suggested you add the general combustion of nitrogen containing fuels, as these can (and unfortunately often) form NOx exhaust.

Obviously, no commerical value as a path to HNO3. However, if a home chemist already has a sunk cost in an old lawn mover engine, for example, adding a green fuel may be a source of NOx.
woelen

Posts: 7776
Registered: 20-8-2005
Location: Netherlands
Member Is Offline

Mood: interested

I do not think that is something to add to the diagram. Burning some fuel might indeed produce some NOx, but there will be sooo much other crap in the exhaust gases as well, that it is not economic and practical at all to isolate NOx and/or HNO3 from this. If that indeed were a viable route to HNO3 then many people would have done so, because of the general availability of the fuels.

The art of wondering makes life worth living...
Want to wonder? Look at https://woelen.homescience.net
AJKOER

Posts: 3016
Registered: 7-5-2011
Member Is Offline

Mood: No Mood

Woelen:

While I agree with your comments, my statement was quite non-specific, as my understanding is that NOx can be formed from the combustion of nitrogen containing fuels under certain conditions. Already cited above include the oxidation of urea and ammonia in the presence of catalysts. However, for example, when NH3 is combusted in a high pressure environment (like in an automotive engine), some NOx exhaust is formed without a catalyst.

The reason is, for example:

4 NH3 (g) + 5 O2 (g) ---> 4 NO (g) + 3 H2O (g)

so 9 moles are turned into 7, whereas:

4 NH3 (g) + 3 O2 (g) --> 2 N2 (g) + 6 H2O (g)

or 7 moles forms 8 moles. So in a high pressure environment, the first reaction may be favored.

Now, my suggestion implies that there could exist other simple nitrogen, hydrogen and other element compounds that when combusted at high pressure could similarly form NOx gas. No claim as to commercial significance, as this is not the topic. The current thread relates to restricted access to HNO3, and not a competitive cost effective, or even particularly safe, alternative route to Nitric acid.
The_Davster
A pnictogen

Posts: 2861
Registered: 18-11-2003
Member Is Offline

Mood: .

Can you get sulfuric acid (98%) and potassium, sodium, or ammonium nitrate?

If so...

Get a large beaker, 600 ml or so and place a fluted shot glass in the center. The stem on the shot glass should be several centimeters allowing the inside of the glass to be raised off the bottom of the beaker. Find some nitric acid proof plastic. I forget which plastic I used but I am pretty sure it was a ziploc baggie. Mix sulfuric and nitrate in the base of the 600 ml beaker and invert a corner of the baggie over the shot glass. Secure the baggie with a rubber band around the beaker, leaving a small hole over the beaker spout to allow for pressure release. Put ice and water in the baggie.

Put the contraption in a 60 C water bath for several hours, and when you come back, the shot glass will have filled with 100% fuming nitric acid, and if you keep the temperature low enough, it is generally mostly free of nitric oxides.
The_Davster
A pnictogen

Posts: 2861
Registered: 18-11-2003
Member Is Offline

Mood: .

 Quote: Originally posted by binaryclock You really want nitric acid? That is some of the nastiest stuff I've ever encountered. .... Anyways, see nurdrage's video regarding nitric acid if you really still want to make it: http://www.youtube.com/watch?v=2yE7v4wkuZU

You have not encountered too much then

Do not make nitric acid like nerdrage did. He used HCl which contaminated his NO2 with nitrosyl chloride giving an impure nitric acid.
binaryclock
Hazard to Others

Posts: 121
Registered: 9-4-2013
Member Is Offline

Mood: Organic

 Quote: Originally posted by The_Davster You have not encountered too much then

I have not .. pretty new to all of this. But nitric acid is vile stuff when it's fuming

Current Project: Playing with my new Laboy advanced distillery kit!

 Sciencemadness Discussion Board » Fundamentals » Beginnings » How can I make niric acid? Select A Forum Fundamentals   » Chemistry in General   » Organic Chemistry   » Reagents and Apparatus Acquisition   » Beginnings   » Responsible Practices   » Miscellaneous   » The Wiki Special topics   » Technochemistry   » Energetic Materials   » Biochemistry   » Radiochemistry   » Computational Models and Techniques   » Prepublication Non-chemistry   » Forum Matters   » Legal and Societal Issues


text:
# Burning down the house

Use the conservation equation to find $$\langle s\rangle$$ in terms of $$\rho_\textrm{tree},$$ $$f,$$ and $$r.$$

What is $$\langle s\rangle$$ when $$\rho_\textrm{tree} = 0.4,$$ $$f = 0.01,$$ and $$r = 0.05?$$

Hint: Recall that $$\rho_\textrm{empty} + \rho_\textrm{tree} + \rho_\textrm{burning} = 1.$$

Assume that $$\rho_\textrm{burning} \ll \{\rho_\textrm{empty}, \rho_\textrm{tree}\}.$$

×


text:
Minimizing Message Size in Stochastic Communication Patterns:Fast Self-Stabilizing Protocols with 3 bits1footnote 11footnote 1A preliminary version of this work appears as a 3-pages Brief Announcement in PODC 2016 [BKN16] and as an extended abstract at SODA 2017 [BKN17].

Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits111A preliminary version of this work appears as a 3-pages Brief Announcement in PODC 2016 [Bkn16] and as an extended abstract at SODA 2017 [Bkn17].

Lucas Boczkowski IRIF, CNRS and University Paris Diderot, Paris, 75013, France. E-mail: {Lucas.Boczkowski,Amos.Korman}@irif.fr.    Amos Korman 22footnotemark: 2    Emanuele Natale Max Planck Institute for Informatics, SaarbrÃ¼cken, 66123 , Germany. E-mail: emanuele.natale@mpi-inf.mpg.de. This work has been partly done while the author was visiting the Simons Institute for the Theory of Computing. This work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 648032).
Abstract

This paper considers the basic model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast (also termed Rumor Spreading). We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. In particular, the specification of who is a source and what is its initial input bit may be set by an adversary.

We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property (called “the bitwise-independence property”) that uses -bits messages to one that uses only -bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer , within rounds w.h.p., and using messages that contain bits only.

We then employ the new Clock Synchronization tool to obtain a self-stabilizing Majority Bit Dissemination protocol which converges in time, w.h.p., on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction.

Minimizing Message Size in Stochastic Communication Patterns:

Fast Self-Stabilizing Protocols with 3 bitsthanks: A preliminary version of this work appears as a 3-pages Brief Announcement in PODC 2016 [BKN16] and as an extended abstract at SODA 2017 [BKN17].

 Lucas Boczkowski ††thanks: IRIF, CNRS and University Paris Diderot, Paris, 75013, France. E-mail: {Lucas.Boczkowski,Amos.Korman}@irif.fr. and Amos Korman 22footnotemark: 2 and Emanuele Natale ††thanks: Max Planck Institute for Informatics, SaarbrÃ¼cken, 66123 , Germany. E-mail: emanuele.natale@mpi-inf.mpg.de. This work has been partly done while the author was visiting the Simons Institute for the Theory of Computing. This work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 648032).

1 Introduction

1.1 Background and motivation

Distributed systems composed of limited agents that interact in a stochastic fashion to jointly perform tasks are common in the natural world as well as in engineered systems. Examples include a wide range of insect populations [HM85], chemical reaction networks [CCDS14], and mobile sensor networks [Pop1]. Such systems have been studied in various disciplines, including biology, physics, computer science and chemistry, while employing different mathematical and experimental tools.

From an algorithmic perspective, such complex systems share a number of computational challenges. Indeed, they all perform collectively in dynamically changing environments despite being composed of limited individuals that communicate through seemingly unpredictable, unreliable, and restricted interactions. Recently, there has been significant interest in understanding the computational limitations that are inherent to such systems, by abstracting some of their characteristics as distributed computing models, and analyzing them algorithmically [Dan2, Pop1, AFJ06, BCN15, Doty, OHK14]. These models usually consider agents which are restricted in their memory and communication capacities, that interact independently and uniformly at random (u.a.r.). By now, our understanding of the computational power of such models is rather advanced. However, it is important to note that much of this progress has been made assuming non-faulty scenarios - a rather strong assumption when it comes to natural or sensor-based systems. For example, to synchronize actions between processors, many known distributed protocols rely on the assumption that processors know when the protocol is initiated. However, in systems composed of limited individuals that do not share a common time notion, and must react to a dynamically changing environment, it is often unclear how to achieve such conditions. To have a better understanding of such systems, it is desirable to identify the weakest computational models that still allow for both efficient as well as robust computations.

This paper concentrates on the basic model of communication [DGH88, DF11a, DGM11, KSSV00], in which in each round, each agent can extract (pull) information from few other agents, chosen u.a.r. In the computer science discipline, this model, as well as its companion model, gained their popularity due to their simplicity and inherent robustness to different kinds of faults. Here, focusing more on the context of natural systems, we view the model as an abstraction for communication in well-mixed scenarios, where agents can occasionally “observe” arbitrary other agents. We aim to identify the minimal model requirements with respect to achieving basic information dissemination tasks under conditions of increased uncertainty. As many natural systems appear to be more restricted by their communication abilities than by their memory capacities [Survey, beeping1, emek], our main focus is on understanding what can be computed while revealing as few bits per interaction as possible111We note that stochastic communication patterns such as or are inherently sensitive to congestion issues. Indeed, in such models it is unclear how to simulate a protocol that uses large messages while using only small size messages. For example, the straightforward strategy of breaking a large message into small pieces and sequentially sending them one after another does not work, since one typically cannot make sure that the small messages reach the same destination. Hence, reducing the message size may have a profound impact on the running time, and perhaps even on the solvability of the problem at hand..

Self-stabilizing Bit Dissemination.

Disseminating information from one or several sources to the rest of the population is one of the most fundamental building blocks in distributed computing [CHHKM12, CLP09, DGH88, DF11a, KSSV00], and an important primitive in natural systems [FishConsensus, Razin, ManyEyes]. Here, we focus on the Majority Bit Dissemination problem defined as follows. We consider a population of agents. The population may contain multiple source agents which are specified by a designated bit in the state of an agent indicating whether the agent is a source or not. Each source agent holds a binary input bit, however, sources may not necessarily agree on their input bits. In addition, each agent holds a binary output bit (also called opinion). The goal of all agents is to converge their opinion on the majority bit among the initial input bits of the sources, termed . This problem aims to capture scenarios in which some individuals view themselves as informed, but some of these agents could also be wrong, or not up-to-date. Such situations are common in nature [COU05, Razin] as well as in man-made systems. The number of sources is termed . We do not assume that agents know the value , or that sources know whether they are in the majority or minority (in terms of their input bit). For simplicity, to avoid dealing with the case that the fraction of the majority input bit among sources is arbitrarily close to that of the minority input bit, we shall guarantee convergence only when the fraction of source agents holding the majority input bit is bounded away from .

The particular case where we are promised to have is called Bit Dissemination, for short. In this case we have a single source agent that aims to disseminate its input bit to the rest of the population, and there are no other sources introducing a conflicting opinion. Note that this problem has been studied extensively in different models under different names (e.g., Broadcast or Rumor Spreading). A classical example of Bit Dissemination considers the synchronous / communication model, where can be propagated from the source to all other agents in rounds, by simply letting each uninformed agent copy it whenever it sees an informed agent [KSSV00]. The correctness of this protocol heavily relies on the absence of incorrect information held by agents. Such reliability however may be difficult to achieve in dynamic or unreliable conditions. For example, if the source is sensitive to an unstable environment, it may change its mind several times before stabilizing to its final opinion. Meanwhile, it may have already invoked several consecutive executions of the protocol with contradicting initial opinions, which may in turn “infect” other agents with the wrong opinion . If agents do not share a common time notion, it is unclear how to let infected agents distinguish their current wrong opinion from the more “fresh”, correct opinion. To address such difficulty, we consider the context of self-stabilization [dijkstra], where agents must converge to a correct configuration from any initial configuration of states.

1.2 Technical difficulties and intuition

Consider the Bit Dissemination problem (where we are guaranteed to have a single source agent). This particular case is already difficult in the self-stabilizing context if we are restricted to use bits per interaction. As hinted above, a main difficulty lies in the fact that agents do not necessarily share a common time notion. Indeed, it is easy to see that if all agents share the same clock, then convergence can be achieved in time with high probability (w.h.p.), i.e, with a probability of at least , and using two bits per interaction.

Self-stabilizing Bit Dissemination (k=1) with 2 bits per interaction, assuming synchronized clocks.

The source sets her output bit to be her input bit . In addition to communicate its output bit , each agent stores and communicates a certainty bit . Informally, having a certainty bit equal to 1 indicates that the agent is certain of the correctness of its output bit. The source’s certainty bit is always set to 1. Whenever a non-source agent observes and sees the tuple , where , it copies the output and certainty bits of (i.e., sets and ). In addition, all non-source agents count rounds, and reset their certainty bit to 0 simultaneously every rounds. The reset allows to get rid of “old” output bits that may result from applying the protocol before the source’s output bit has stabilized. This way, from the first time a reset is applied after the source’s output bit has stabilized, the correct source’s output bit will propagate to all agents within rounds, w.h.p. Note however, that if agents do not share a consistent notion of time they cannot reset their certainty bit to zero simultaneously. In such cases, it is unclear how to prevent agents that have just reset their certainty bit to 0 from being “infected” by “misleading” agents, namely, those that have the wrong output bit and certainty bit equal to 1.

Self-stabilizing Bit Dissemination (k=1) with a single bit per interaction, assuming synchronized clocks.

Under the assumption that all agents share the same clock, the following trick shows how to obtain convergence in time and using only a single bit per message, namely, the output bit. As before, the source sets her output bit to be her input bit . Essentially, agents divide time into phases of some prescribed length , each of them being further subdivided into subphases of length . In the first subphase of each phase, non-source agents are sensitive to opinion . This means that whenever they see a in the output bit of another agent, they turn their output bit to , but if they see 1 they ignore it. Then, in the second subphase of each phase, they do the opposite, namely they switch their output bit to as soon as they see a (see Figure 1). Consider the first phase starting after initialization. If then within one complete subphase , every output bit is w.h.p., and remains there forever. Otherwise, if , when all agents go over a subphase all output bits are set to w.h.p., and remain forever. Note that a common time notion is required to achieve correctness.

The previous protocol indicates that the self-stabilizing Bit Dissemination problem is highly related to the self-stabilizing Clock Synchronization problem, where each agent internally stores a clock modulo incremented at every round and, despite having arbitrary initial states, all agents should converge on sharing the same value of the clock. Indeed, given such a protocol, one can obtain a self-stabilizing Bit Dissemination protocol by running the Clock Synchronization protocol in parallel to the last example protocol. This parallel execution costs only an additional bit to the message size and a additive factor to the time complexity over the complexities of the Clock Synchronization protocol.

Intuition behind the self-stabilizing Clock Synchronization algorithm.

Our technique for obtaining the Clock Synchronization protocol is based on a compact recursive use of the stabilizing consensus protocol proposed by Doerr et al. [DGM11] through our Message Reduction Theorem (Theorem 3.1).

In the Preliminary section (Section 2.2) we describe a simple protocol called Syn-Simple that uses bits per message. In Syn-Simple, each agent maintains a clock . At each round, each agent displays the opinion of her clock, pulls  other such clock opinions, and updates her clock as the bitwise majority of the two clocks she pulled and her own. Then the clock is incremented. This protocol essentially amounts to running the protocol of Doerr et al. on each bit separately and in parallel, and self-stabilizes in rounds w.h.p. (Proposition 2.1).

We want to apply a strategy similar to Syn-Simple, while using only many bits per interaction. The core technical ingredient, made rigorous in the Message Reduction Theorem, is that a certain class of protocols using messages of bits, to which Syn-Simple belongs, can be emulated by another protocol which uses bits only. The idea is to build a clock modulo using Syn-Simple itself on bits and sequentially display one bit of the original -bit message according to such clock. Thus, by applying such strategy to Syn-Simple itself, we use a smaller clock modulo to synchronize a clock modulo . Iterating such process, in Section 4.2, we obtain a compact protocol which uses only bits.

1.3 The model

The communication model.

We adopt the the synchronous model [BCN16, DGH88]. Specifically, in the model, communication proceeds in discrete rounds. In each round, each agent “observes” arbitrary other agents, chosen u.a.r.222“u.a.r.” stands for “uniformly at random”, with replacement. among all agents, including herself. (We often omit the parameter when it is equal to 2). When an agent “observes” another agent , she can peek into a designated visible part of ’s memory. If several agents observe an agent at the same round then they all see the same visible part. The message size denotes the number of bits stored in the visible part of an agent. We denote with the model with message size . We are primarily interested in message size that is independent of , the number of agents.

Agents.

We assume that agents do not have unique identities, that is, the system is anonymous. We do not aim to minimize the (non-visible) memory requirement of the agent, yet, we note that our constructions can be implemented with relatively short memory, using bits. We assume that each agent internally stores a clock modulo some integer , which is incremented at every round.

Majority Bit Dissemination problem.

We assume a system of agents each having an internal state that contains an indicator bit which indicates whether or not the agent is a source. Each source holds a binary input bit333 Note that having the indicator bit equal to 1 is equivalent to possessing an input bit: both are exclusive properties of source nodes. However, we keep them distinct for a clearer presentation. and each agent (including sources) holds a binary opinion. The number of sources (i.e., agents whose indicator bit is ) is denoted by . We denote by and the number of sources whose input bit is initially set to and , respectively. Assuming , we define the majority bit, termed , as if and if . Source agents know that they are sources (using the indicator bit) but they do not know whether they hold the majority bit. The parameters , or are not known to the sources or to any other agent. It is required that the opinions of all agents eventually converge to the majority bit. We note that agents hold their output and indicator bits privately, and we do not require them to necessarily reveal these bits publicly (in their visible parts) unless they wish to. To avoid dealing with the cases where the number of sources holding the majority bit is arbitrarily close to , we shall guarantee correctness (w.h.p.) only if the fraction of sources holding the majority is bounded away from , i.e., only if , for some positive constant . When , the problem is called Bit Dissemination, for short. Note that in this case, the single source agent holds the bit to be disseminated and there is no other source agent introducing a conflicting opinion.

T-Clock Synchronization.

Let be an integer. In the -Clock Synchronization problem, each agent maintains a clock modulo that is incremented at each round. The goal of agents is to converge on having the same value in their clocks modulo . (We may omit the parameter when it is clear from the context.)

Probabilistic self-stabilization and convergence.

Self-stabilizing protocols are meant to guarantee that the system eventually converges to a legal configuration regardless of the initial states of the agents [dijkstra]. Here we use a slightly weaker notion, called probabilistic self-stabilization, where stability is guaranteed w.h.p. [BCN15b]. More formally, for the Clock Synchronization problem, we assume that all states are initially set by an adversary. For the Majority Bit Dissemination problem, we assume that all states are initially set by an adversary except that it is assumed that the agents know their total number , and that this information is not corrupted.

In the context of -Clock Synchronization, a legal configuration is reached when all clocks show the same time modulo , and in the Majority Bit Dissemination problem, a legal configuration is reached when all agents output the majority bit . Note that in the context of the Majority Bit Dissemination problem, the legality criteria depends on the initial configuration (that may be set by an adversary). That is, the agents must converge their opinion on the majority of input bits of sources, as evident in the initial configuration.

The system is said to stabilize in rounds if, from any initial configuration w.h.p., within rounds it reaches a legal configuration and remains legal for at least some polynomial time [BCN15b, BCN16, DGM11]. In fact, for the self-stabilizing Bit Dissemination problem, if there are no conflicting source agents holding a minority opinion (such as in the case of a single source agent), then our protocols guarantee that once a legal configuration is reached, it remains legal indefinitely. Note that, for any of the problems, we do not require that each agent irrevocably commits to a final opinion but that eventually agents arrive at a legal configuration without necessarily being aware of that.

1.4 Our Results

Our main results are the following.

Theorem 1.1

Fix an arbitrarily small constant . There exists a protocol, called Syn-Phase-Spread, which solves the Majority Bit Dissemination problem in a self-stabilizing manner in rounds444With a slight abuse of notation, with we refer to . All logarithms are in base . w.h.p using -bit messages, provided that the majority bit is supported by at least a fraction of the source agents.

Theorem 1.1 is proved in Section 5. The core ingredient of Syn-Phase-Spread is our construction of an efficient self-stabilizing -Clock Synchronization protocol, which is used as a black-box. For this purpose, the case that interests us is when . Note that in this case, the following theorem, proved in Section 4, states that the convergence time of the Clock Synchronization algorithm is .

Theorem 1.2

Let be an integer. There exists a self-stabilizing -Clock Synchronization protocol, called Syn-Clock, which employs only 3-bit messages, and synchronizes clocks modulo  within rounds w.h.p.

In addition to the self-stabilizing context our protocols can tolerate the presence of Byzantine agents, as long as their number is555Specifically, it is possible to show that, as a corollary of our analysis and the fault-tolerance property of the analysis in [DGM11], if then Syn-Clock can tolerate the presence of up to Byzantine agents for any . In addition, Syn-Phase-Spread can tolerate Byzantine agents, where and are the number of sources supporting the majority and minority opinions, respectively. Note that for the case of a single source (), no Byzantine agents are allowed; indeed, a single Byzantine agent pretending to be the source with the opposite opinion can clearly ruin any protocol. . However, in order to focus on the self-stabilizing aspect of our results, in this work we do not explicitly address the presence of Byzantine agents.

The proofs of both Theorem 1.2 and Theorem 1.1 rely on recursively applying a new general compiler which can essentially transform any self-stabilizing algorithm with a certain property (called “the bitwise-independence property”) that uses -bit messages to one that uses only -bit messages, while paying only a small penalty in the running time. This compiler is described in Section 3, in Theorem 3.1, which is also referred as “the Message Reduction Theorem”. The structure between our different lemmas and results is summarized in the picture below, Figure 2.

It remains an open problem, both for the self-stabilizing Bit Dissemination problem and for the self-stabilizing Clock Synchronization problem, whether the message size can be reduced to 2 bits or even to 1 bit, while keeping the running time poly-logarithmic.

1.5 Related work

The computational study of abstract systems composed of simple individuals that interact using highly restricted and stochastic interactions has recently been gaining considerable attention in the community of theoretical computer science. Popular models include population protocols [Pop1, Pop2, Pop-ss, Joffroy], which typically consider constant size individuals that interact in pairs (using constant size messages) in random communication patterns, and the beeping model [beeping1, emek], which assumes a fixed network with extremely restricted communication. Our model also falls in this framework as we consider the model [DGH88, KSSV00, KDG03] with constant size messages. So far, despite interesting works that consider different fault-tolerant contexts [Aspnes, Pop-ss, Joffroy], most of the progress in this framework considered non-faulty scenarios.

Information dissemination is one of the most well-studied topics in the community of distributed computing, see, e.g., [Aspnes, CHHKM12, DGH88, DF11a, DGM11, OHK14, KSSV00]. Classical examples include the Broadcast (also referred to in the literature as Rumor Spreading) problem, in which a piece of information residing at one source agent is to be disseminated to the rest of the population, and majority-consensus (here, called Majority Bit Dissemination) problems in which processors are required to agree on a common output value which is the majority initial input value among all agents [Aspnes, kutten] or among a set of designated source agents [OHK14]. An extensive amount of research has been dedicated to study such problems in based protocols (including the phone call model), due to the inherent simplicity and fault-tolerant resilience of such meeting patterns. Indeed, the robustness of based protocols to weak types of faults, such as crashes of messages and/or agents, or to the presence of relatively few Byzantine agents, has been known for quite a while [ES09, KSSV00]. Recently, it has been shown that under the model, there exist efficient Broadcast and Majority Bit Dissemination protocols that use a single bit per message and can overcome flips in messages (noise) [OHK14]. The protocols therein, however, heavily rely on the assumption that agents know when the protocol has started. Observe that in a self-stabilizing context, in which the adversary can corrupt the initial clocks setting them to arbitrary times, such an assumption would be difficult to remove while preserving the small message size.

In general, there are only few known self-stabilizing protocols that operate efficiently under stochastic and capacity restricted interactions. An example, which is also of high relevance to this paper, is the work of Doerr et al. on Stabilizing Consensus [DGM11] operating in the model. In that work, each agent initially has a state taken out of a set of opinions and the goal is to converge on one of the proposed states. The proposed algorithm which runs in logarithmic time is based on sampling the states of agents and updating the agent’s state to be the median of the sampled states and the current state of the agent ( opinions in total). Since the total number of possible states is , the number of bits that must be revealed in each interaction is . Another example is the plurality consensus protocol in [BCN16], in which each agent has initially an opinion and we want the system to converge to the most frequent one in the initial configuration of the system. In fact, the Majority Bit Dissemination problem can be viewed as a generalization of the majority-consensus problem (i.e. the plurality consensus problem with two opinions), to the case in which multiple agents may initially be unopinionated. In the previous sense, we also contribute to the line of research on the majority-consensus problem [BCN15, CER15, EFK16].

Another fundamental building block is Clock Synchronization [Attiya, Lamport, Lenzen3, Lenzen2]. We consider a synchronous system in which clocks tick at the same pace but may not share the same opinion. This version has earlier been studied in e.g., [Ben-Or, Dolev07, Dolev97, Dolev04, SIROCCO, Herman] under different names, including “digital Clock Synchronization” and “synchronization of phase-clocks”; We simply use the term “Clock Synchronization”. There is by now a substantial line of work on Clock Synchronization problems in a self-stabilizing context [DolevKLRS13, Dolev04, Lenzen4, Lenzen5]. We note that in these papers the main focus is on the resilience to Byzantine agents. The number of rounds and message lengths are also minimized, but typically as a function of the number of Byzantine processors. Our focus is instead on minimizing the time and message complexities as much as possible. The authors in [Lenzen4, Lenzen5] consider mostly a deterministic setting. The communication model is very different than ours, as every agent gets one message from every other agent on each round. Moreover, agents are assumed to have unique identifiers. In contrast, we work in a more restricted, yet randomized communication setting. In [DolevKLRS13, Lenzen4] randomized protocols are also investigated. We remark that the first protocol we discuss Syn-Simple (Proposition 2.1), which relies on a known simple connection between consensus and counting [DolevKLRS13], already improves exponentially on the randomized algorithms from [DolevKLRS13, Lenzen4] in terms of number of rounds, number of memory states, message length and total amount of communication, in the restricted regime where the resilience parameter satisfies . We further note that the works [Lenzen5, Lenzen4] also use a recursive construction for their clocks (although very different from the one we use in the proof of Theorem 1.2). The induction in [Lenzen4] is on the resilience parameter , the number of agents and the clock length together. This idea is improved in [Lenzen5] to achieve optimality in terms of resilience to Byzantine agents.

To the best of our knowledge there are no previous works on self-stabilizing Clock Synchronization or Majority Bit Dissemination that aim to minimize the message size beyond logarithmic.

2 Preliminaries

2.1 A majority based, self-stabilizing protocol for consensus on one bit

Let us recall666Our protocols will use this protocol as a black box. However, we note that the constructions we outline are in fact independent of the choice of consensus protocol, and this protocol could be replaced by other protocols that achieve similar guarantees. the stabilizing consensus protocol by Doerr et al. in [DGM11]. In this protocol, called maj-consensus, each agent holds an opinion. In each round each agent looks at the opinions of two other random agents and updates her opinion taking the majority among the bits of the observed agents and its own. Note that this protocol uses only a single bit per interaction, namely, the opinion. The usefulness of maj-consensus comes from its extremely fast and fault-tolerant convergence toward an agreement among agents, as given by the following result.

Theorem 2.1 (Doerr et al. [Dgm11])

From any initial configuration, maj-consensus converges to a state in which all agents agree on the same output bit in rounds, w.h.p. Moreover, if there are at most Byzantine agents, for any constant , then after rounds all non-Byzantine agents have converged and consensus is maintained for rounds w.h.p.777The original statement of [DGM11] says that if at most agents can be corrupted at any round, then convergence happens for all but at most agents. Let us explain how this implies the statement we gave, namely that we can replace by , if . Assume that we are in the regime . It follows from [DGM11] that all but a set of agents reach consensus after round. This set of size contains both Byzantine and non Byzantine agents. However, if the number of agents holding the minority opinion is , then the expected number of non Byzantine agents that disagree with the majority at the next round is in expectation . Thus, by Markov’s inequality, this implies, that at the next round consensus is reached among all non-Byzantine agents w.h.p. Note also that, for the same reasons, the Byzantine agents do not affect any other non-Byzantine agent for rounds w.h.p.

2.2 Protocol Syn-Simple: A simple protocol with many bits per interaction

We now present a simple self-stabilizing -Clock Synchronization protocol, called Syn-Simple, that uses relatively many bits per message, and relies on the assumption that is a power of 2. The protocol is based on iteratively applying a self-stabilizing consensus protocol on each bit of the clock separately, and in parallel.

Formally, each agent maintains a clock . At each round, displays the opinion of her clock , pulls  uniform other such clock opinions, and updates her clock as the bitwise majority of the two clocks it pulled, and her own. Subsequently, the clock is incremented. We present the pseudo code of Syn-Simple in Algorithm 1.

We prove the correctness of Syn-Simple in the next proposition.

Proposition 2.1

Let be a power of . The protocol Syn-Simple is a self-stabilizing protocol that uses bits per interaction and synchronizes clocks modulo in rounds w.h.p.

• Let us look at the least significant bit. One round of Syn-Simple is equivalent to one round of maj-consensus with an extra flipping of the opinion due to the increment of the clock. The crucial point is that all agents jointly flip their bit on every round. Because the function agents apply, maj, is symmetric, it commutes with the flipping operation. More formally, let be the vector of the first bits of the clocks of the agents at round under an execution of Syn-Simple. E.g. is the value of the less significant bit of node ’s clock at time . Similarly, we denote by the first bits of the clocks of the agents at round obtained by running a modified version of Syn-Simple in which time is not incremented (i.e. we skip line 1 in Algorithm 1). We couple and trivially, by running the two versions on the same interaction pattern (in other words, each agent starts with the same memory and pulls the same agents at each round in both executions). Then, is equal to when is even, while is equal to when is odd. Moreover, we know from Theorem 2.1 that converge to a stable opinion in a self-stabilizing manner. It follows that, from any initial configuration of states (i.e. clocks), w.h.p, after rounds of executing Syn-Simple, all agents share the same opinion for their first bit, and jointly flip it in each round. Once agents agree on the first bit, since is a power of , the increment of time makes them flip the second bit jointly once every rounds888To get the feeling of the kind of dependence more significant bits have on the less significant ones when is not a power of observe that, for example, if then the first bit takes cyclically the values , and again .. More generally, assuming agents agree on the first bits of their clocks, they jointly flip the ’st bit once every rounds, on top of doing the maj-consensus protocol on that bit. Hence, the same coupling argument shows that the flipping doesn’t affect the convergence on bit . Therefore, rounds after the first bits are synchronized, w.h.p. the ’st bit is synchronized as well. The result thus follows by induction.

2.3 The bitwise-independence property

Our general transformer described in Section 3 is useful for reducing the message size of protocols with a certain property called bitwise-independence. Before defining the property we need to define a variant of the model, which we refer to as the model. The reason we introduce such a variant is mainly technical, as it appears naturally in our proofs.

Recall that in the model, at any given round, each agent is reading an -bit message for each of the observed agents chosen u.a.r. (in our case ), and then, in turn, updates her state according to the instructions of a protocol P. Informally, in the model, each agent also receives messages, however, in contrast to the model where each such message corresponds to one observed agent, in the model, the ’th bit of each such message is received independently from a (typically new) agent, chosen u.a.r. from all agents.

Definition 1 (The BIT model)

In the model, at each round, each agent picks agents u.a.r., namely, ,…,, and reads , the -th bit of the visible part of agent , for every and . For each , let be the -bit string . By a slight abuse of language we call the strings the messages received by in the model.

Definition 2 (The bitwise−independence property)

Consider a protocol P designed to work in the model. We say that P has the bitwise-independence property if its correctness and running time guarantees remain the same, under the model (assuming that given the messages it receives at any round, each agent performs the same actions that it would have, had it received these messages in the model).

Let us first state a fact about protocols having the bitwise-independence property.

Lemma 2.1

Assume protocol Syn-Generic is a protocol synchronizing clocks modulo for some and protocol P is a protocol which works assuming agents share a clock modulo . Denote by Syn-P the parallel execution of Syn-Generic and P, with P using the clock synchronized by Syn-Generic. If Syn-Generic and P are self-stabilizing then so is Syn-P, and the convergence time of Syn-P is at most the sum of convergence times of Syn-Generic and P. Finally, if Syn-Generic and P have the bitwise-independence property, and P is also self-stabilizing, Syn-P has the bitwise-independence property too.

• The self-stabilizing property of Syn-P and its convergence time easily follows from those of Syn-Generic and P.

As for the bitwise-independence property, assume we run Syn-P in the model. The execution of Syn-Generic is carried independently of the execution of P. Since, by hypothesis, Syn-Generic has the independence property, eventually all agents have a synchronized clock modulo . Thus, once clocks are synchronized, we can disregard the part of the message corresponding to Syn-Generic, and view the execution of Syn-P as simply P. Therefore, since P is self-stabilizing and has the independence property, Syn-P still works in the model as in the original model.

We next show that the protocol Syn-Simple has the aforementioned bitwise-independence property.

Lemma 2.2

Syn-Simple has the bitwise-independence property.

• Let be the size of the clocks. Assume the first bits of the clocks have been synchronized. At this stage, the -st bit of each agent is flipped every rounds and updated as the majority of the -st bit of and the pulled messages on each round. Since the first bits are synchronized, the previous flipping is performed by all agents at the same round. The thesis follows from the observation that, in order for Syn-Simple to work, we do not need the bit at index to come from the same agent as those bits used to synchronize the other indices, as long as convergence on the first bits has been achieved.

3 A General Compiler that Reduces Message Size

In this section we present a general compiler that allows to implement a protocol P using -bit messages while using messages of order instead, as long as P enjoys the bitwise-independence property. The compiler is based on replacing a message by an index to a given bit of the message. This tool will repeatedly be used in the following sections to obtain our Clock Synchronization and Majority Bit Dissemination algorithms that use 3-bit messages.

Theorem 3.1 (the Message Reduction Theorem)

Any self-stabilizing protocol P in the model having the bitwise-independence property, and whose running time is , can be emulated by a protocol Emul(P) which runs in the model, has running time and has itself the bitwise-independence property.

Remark 1

The only reason for designing Emul(P) to run in the model in the Message Reduction Theorem is the consensus protocol we adopt, maj-consensus, which works in the model. In fact, Emul(P) can be adapted to run in the model by using a consensus protocol which works in the model. However, no self-stabilizing binary consensus protocol in the model with the same performances as maj-consensus is currently known.

Proof of Theorem 3.1. Let be the message displayed by an agent under P at a given round. For simplicity’s sake, in the following we assume that is even, the other case is handled similarly. In Emul(P), agent keeps the message  privately, and instead displays a clock written on bits, and one bit of the message , which we refer to as the P-bit. Thus, the total number of bits displayed by the agent operating in Emul(P) is . The purpose of the clock is to indicate to agent which bit of to display. In particular, if the counter has value , then the -th bit (i.e the least significant bit) of is shown as the P-bit, and so on. In what follows, we refer to as the private message of , to emphasize the fact that this message is not visible in Emul(P). See Figure 3 for an illustration.

Each round of P executed in the model by an agent is emulated by rounds of Emul(P) in the model. We refer to such rounds as a phase, which is further divided to subphases of length . Note that since each agent samples 2 agents in a round, the total number of agents sampled by an agent during a phases is .

For a generic agent , a phase starts when its clock is zero, and ends after a full loop of its clock (i.e. when returns to zero). Each agent is running protocol Syn-Simple on the bits which correspond to her clock . Note that the phases executed by different agents may initially be unsynchronized, but, thanks to Proposition 2.1, the clocks eventually converge to the same value, for each agent , and hence all agents eventually agree on when each phase (and subphase) starts.

Let be an arbitrary agent. Denote by , …, the P-bits collected by from agents chosen u.a.r during a phase. Consider a phase and a round in that phase. Let and be such that . We view as round of subphase of the phase. On this round, agent pulls two messages from agents and , chosen u.a.r. Once the clocks (and thus phases and subphases) have synchronized, agents and are guaranteed to be displaying the th index of their private messages, namely, the values and , respectively. Agent then sets equal to and equal to .

In Emul(P), the messages displayed by agents are only updated after a full loop of . It therefore follows from the previous paragraph that the P-bits collected by agent after a full-phase are distributed like the bits collected during one round of P in the model (see Definition 1), assuming the clocks are synchronized already.

Correctness. The bitwise-independence property of Syn-Simple (Lemma 2.2), implies that Syn-Simple still works when messages are constructed from the P-bits collected by Emul(P). Therefore, from Proposition 2.1, eventually all the clocks are synchronized. Since private messages are only updated after a full loop of , once the clocks are synchronized a phase of Emul(P) corresponds to one round of P, executed in the model. Hence, the hypothesis that P operates correctly in a self-stabilizing way in the model implies the correctness of Emul(P).

Running time. Once the clocks are synchronized, for all agents , using the first bits of the messages, the agents reproduce an execution of P with a multiplicative time-overhead of . Moreover, from Proposition 2.1, synchronizing the clocks takes rounds. Thus, the time to synchronize the clocks costs only an additive factor of rounds, and the total running time is .

Bitwise-independence property. Protocol Emul(P) inherits the bitwise-independence property from that of Syn-Simple (Lemma 2.2) and P (which has the property by hypothesis): We can apply Lemma 2.1 where Syn-Generic is Syn-Simple and P is the subroutine described above, which displays at each round the bit of whose index is given by a synchronized clock modulo (i.e. the one produced by Syn-Simple). Observe that the aforementioned subroutine is self-stabilizing, since it emulates P once clocks are synchronized. Then, in the notation of Lemma 2.1, Emul(P) is Syn-P.

4 Self-Stabilizing Clock Synchronization

In Section 2.2 we described Syn-Simple -  a simple self-stabilizing Clock Synchronization protocol that uses bits per interaction. In this section we describe our main self-stabilizing Clock Synchronization protocol, Syn-Bits, that uses only bits per interaction. We first assume is a power of . We show how to get rid of this assumption in Section 4.2.

4.1 Clock Synchronization with 3-bit messages, assuming T is a power of two

In this section, we show the following result.

Lemma 4.1

Let be a power of . There exists a synchronization protocol Syn-Intermediate which synchronizes clocks modulo in time using only 3-bit messages. Moreover, Syn-Intermediate has the bitwise-independence property.

Before presenting the proof of Lemma 4.1, we need a remark about clocks.

Remark 2

In order to synchronize a clock modulo , throughout the analysis we often obtain a clock modulo which is incremented every rounds. However, can still be translated back to a clock modulo which is incremented every round, by keeping a third clock modulo and setting

 C=C′+C′′modT.

Proof of Lemma 4.1. At a high level, we simply apply iteratively the Message Reduction Theorem in order to reduce the message to bits, starting with P = Syn-Simple. A pictorial representation of our recursive protocol is given in Figure 4, and a pseudocode is given in Algorithm 2999The pseudocode deviates from the presentation done in the proof, as it makes no use of recursion..

Let us consider what we obtain after applying the Message Reduction Theorem the first time to P Syn-Simple for clocks modulo . Recall that we assume that is a power of 2. From Proposition 2.1 we know that in this case, the convergence time of Syn-Simple is , the number of pulled agents at each round is and the number of bits of each message is .

With the emulation produced by the Message Reduction Theorem, the clock used in P =Syn-Simple is incremented only every rounds. Another way to interpret this is that we obtain a clock modulo and using Remark 2 we can view the clock , as a counter modulo that is incremented at each round. Hence, by the running time analysis of the Message Reduction Theorem, we obtain a protocol Emul(P) which synchronizes a clock modulo in rounds. The message size is reduced from to .

By repeatedly applying the Message Reduction Theorem, we reduce the size of the message as long as , i.e. as long as . The number of repeated application of the Message Reduction Theorem until the message size is is thus of order .

Let us analyze the running time. Let , and let be the smallest integer such that . We apply the Message Reduction Theorem times, and we obtain a message size and a running time , such that

 (4.1) Li+1≤γ1(logℓilogn+ℓiLi),

for some constant independent of . We set to be , taking the maximum with for technical convenience. The second term dominates in (Equation 4.1) because and . Hence is at most of order . More precisely, by induction we can bound , since

 (4.2) Li+1≤γ1logℓilogn+γi1\prodop\displaylimitsij=1ℓj⋅L1≤γ1ℓilogn+γi1\prodop\displaylimitsij=1ℓj⋅L1≤2γi1\prodop\displaylimitsij=1ℓj⋅L1≤γi+11\prodop\displaylimitsij=1ℓj⋅L1,

where we use the fact that , and the definition of .

The running time of Emul(P) Syn-Clock after the last application of the Message Reduction Theorem, i.e. , is thus

 (4.3) L\textscSyn−Clock:=Lτ≤γτ1\prodop\displaylimitsτi=1ℓiL1.

We use the following fact.

Fact 4.1

If , it holds

 ex1+x≤1+x≤ex≤1+x1−x.

From the bounds , , , and Lemma B.1, we obtain and

 ℓτ3≤2O((log⊛4T)2)≤2O(logloglogT)≤(loglogT)O(1).

We thus conclude that

 (4.4) L\textscSyn−Clock ≤γτ1\prodop\displaylimitsτi=1ℓiL1≤O(logloglogT)⋅ℓ1ℓ2ℓτ3⋅O(logTlogn) (4.5) ≤O(logloglogT)⋅O(logT)⋅O(loglogT)⋅O(loglogT)O(1)⋅O(logTlogn) (4.6) ≤log2Tlogn⋅(loglogT)O(1).

The total slowdown with respect to Syn-Simple corresponds to . Hence the clock produced by the emulation is incremented every rounds. In other words we obtain a clock modulo for some function . But using Remark 2 we can still view this as a clock modulo .

4.2 Extension to general T and running time improvement.

In this subsection we aim to get rid of the assumption that is a power of in Lemma 4.1, and also reduce the running time of our protocol to , proving Theorem 1.2.

Proof of Theorem 1.2. From Lemma 4.1, we know that Syn-Intermediate synchronizes clocks modulo in time using only -bit messages, provided that is a power of 2. While protocol Syn-Intermediate emulates protocol Syn-Simple, it displays the first bit of the message of Syn-Simple only once every rounds. Of course, it would be more efficient to display it times in a row, so that maj-consensus would make every agent agree on this bit, and then move to agreeing on the second bit, and so on. To achieve this, as in the proof of Syn-Simple, we can view a clock modulo , say , as written on bits. If agents already possess a “small” counter modulo they can use it to display the first bit for rounds, then the second one for rounds, and so on until each one of the bits of has been synchronized. This would synchronize all bits of the desired clock within rounds, w.h.p., while being very economical in terms of message length, since only bit is displayed at any time.

Therefore, we can use Lemma 4.1 to synchronize a counter modulo in rounds, using bits per message. Then, we can use a fourth bit to run maj-consensus on each of the bits of for consecutive rounds, for a total running time of rounds. At this point, an application of the Message Reduction Theorem would give us a protocol with running time using -bit messages. However, perhaps surprisingly, a similar strategy enables us to synchronize a clock modulo any integer (not necessarily a power of ).

Let us assume that is an arbitrary integer. Let be an upper bound on the convergence time of maj-consensus which guarantees a correct consensus with probability at least , for some constant large enough [DGM11]. Let be the smallest power of bigger than . By Lemma 4.1, using bits, the agents can build a synchronized clock running modulo in time . The other main ingredient in this construction is another clock which is incremented once every rounds and runs modulo . The desired clock modulo , which we denote , is obtained by

 (4.7) C:=(C′+QT′⋅T′)modT.

It is easy to check, given the definitions of and that this choice indeed produces a clock modulo .

It remains to show how the clock modulo is synchronized. On a first glance, it may seem as if we did not simplify the problem since is a clock modulo itself. However, the difference between and a regular clock modulo is that is incremented only once every rounds. This is exploited as follows.

The counter is written on internal bits. We show how to synchronize using a 4-th bit in the messages, similarly to the aforementioned strategy to synchronize ; we later show how to remove this assumption using the Message Reduction Theorem. Let us call a loop of modulo an epoch. The rounds of an epoch are divided in phases of equal length (the remaining rounds are just ignored). The clock determines which bit from to display. The first bit of is displayed during the first phase, then the second one is displayed during the second phase, and so on. By Theorem 2.1, the length of each phase guarantees that consensus is achieved on each bit of via101010Observe that, once clock is synchronized, the bits of do not change for each agent during each subphase. Thus, we may replace maj-consensus by the Min protocol where on each round of subphase each agent pulls another agent u.a.r. and updates her -th bit of to the minimum between her current -th bit of and the one of . However, for simplicity’s sake, we reuse the already introduced maj-consensus protocol. maj-consensus w.h.p. More precisely, after the first bit has been displayed for rounds, all agents agree on it with probability111111From Theorem 2.1, we have that after rounds, with large enough, the probability that consensus has not been reached is smaller than . Thus, after rounds, the probability that consensus has not been reached is smaller than . If we choose , we thus get the claimed upper bound . , provided is large enough. Thus, at the end of an epoch, agents agree on all bits of with probability greater than .

We have thus shown that, by the time reaches its maximum value of , i.e. after one epoch, all agents agree on w.h.p. and then increment it jointly. From Lemma 4.1, Syn-Intermediate takes rounds to synchronize a clock modulo w.h.p. Together with the rounds to agree on w.h.p., this implies that after rounds the clocks are all synchronized w.h.p.

Finally, we show how to get rid of the extra -th bit to achieve agreement on . Observe that, once is synchronized, this bit is used in a self-stabilizing way. Thus, since Syn-Intermediate has the bitwise-independence property, using Lemma 2.1, the protocol we described above possesses the bitwise-independence property too. By using the Message Reduction Theorem we can thus reduce the message size from bits to bits, while only incurring a constant multiplicative loss in the running time. The clock we obtain, counts modulo but is incremented every rounds only. It follows from Remark 2 that we may still view this as a clock modulo .

Remark 3 (Internal memory space)

The internal memory space needed to implement our protocols Syn-Simple, Syn-Intermediate, and Syn-Clock is close to in all cases: protocol Syn-Simple uses one counter written on bits, Syn-Intermediate needs internal memory of size

 (4.8) logT+O(loglogT+logloglogT+…)≤logT(1+o(1)),

and the internal memory requirement of Syn-Clock is of order .

5 Majority Bit Dissemination with a Clock

In this section we assume that agents are equipped with a synchronized clock modulo for some big enough constant . In the previous section we showed how to establish such a synchronized clock in time and using 3-bit messages. We have already seen in Section 1.2 how to solve the Bit Dissemination problem (when we are promised to have a single source agent) assuming such synchronized clocks, by paying an extra bit in the message size and an additive factor in the running time. This section is dedicated to showing that, in fact, the more general Majority Bit Dissemination problem can be solved with the same time complexity and using 3-bit messages, proving Theorem 1.1.

In Section 5.1, we describe and analyze protocol Syn-Phase-Spread, which solves Majority Bit Dissemination by paying only a additive overhead in the running time w.r.t. Clock Synchronization. For clarity’s sake, we first assume that the protocol is using bits (i.e. 1 additional bit over the bits used for Clock Synchronization), and we later show how to decrease the number of bits back to 3 in Section 5.2, by applying the Message Reduction Theorem.

The main idea behind the -bit protocol, called Syn-Phase-Spread, is to make the sources’ input bits disseminate on the system in a way that preserves the initial ratio between the number of sources supporting the majority and minority input bit. This is achieved by dividing the dissemination process in phases, similarly to the main protocol in [OHK14] which was designed to solve the Bit Dissemination problem in a variant of the model in which messages are affected by noise. The phases induces a spreading process which allows to leverage on the concentration property of the Chernoff bounds, preserving the aforementioned ratio. While, on an intuitive level, the role of noisy messages in the model considered in [OHK14] may be related to the presence of sources having conflicting opinion in our setting, we remark that our protocol and its analysis depart from those of [OHK14] on several key points: while the protocol in [OHK14] needs to know the the noise parameter, Syn-Phase-Spread do not assume any knowledge about the number of different sources, and our analysis do not require to control the growth of the number of speaking agents from above121212To get such upper bound, the analysis in [OHK14] leveraged on the property that in the model the number of agents getting a certain message can be upper bounded by the number of agent sending such message, which is not the case for the passive communication of the model..

In order to perform such spreading process with 1 bit only, the protocol in [OHK14] leverages on the fact that in the model agents can choose when to speak, i.e. whether to send a message or not. To emulate this property in the model, we use the parity of the clock : on odd rounds agents willing to “send” a display , while others display and conversely on even rounds. Rounds are then grouped by two, so rounds in the model correspond to round in the version.

In this section we describe protocol Syn-Phase-Spread. As mentioned above, for clarity’s sake we assume that Syn-Phase-Spread uses -bit messages, and we show how to remove this assumption in Section 5.2. Three of such bits are devoted to the execution Syn-Clock, in order to synchronize a clock modulo for some constant large enough. Throughout this section we assume, thanks to Theorem 1.2, that has already been synchronized, which happens after rounds from the start of the protocol. In Section 5.1.1, we present a protocol Phase-Spread solving Majority Bit Dissemination assuming agents already share a common clock.

Let be a constant to be set later. Protocol Phase-Spread is executed periodically over periods of length , given by a clock . One run of length is divided in phases, the first and the last ones lasting rounds, all the other phases lasting rounds. The first phase is called boosting, the last one is called polling, and all the intermediate ones are called spreading. For technical convenience, in Phase-Spread agents disregard the messages they get as their second pull131313In other words, Phase-Spread works in the model..

During the boosting and the spreading phases, as we already explained in the introduction of this section, we make use of the parity of time to emulate the ability to actively send a message or not to communicate anything as in the model141414Of course, agents are still not able to control who sees/contacts them. (in the first case we say that the agent is speaking, in the second case we say that the agent is silent). This induces a factor slowdown which we henceforth omit for simplicity.

At the beginning of the boosting, each non-source agent is silent. During the boosting and during each spreading phase, each silent agent pulls until she sees a speaking agent. When a silent agent sees a speaking agent , memorizes but remains silent until the end of the phase; at the end of the current phase, starts speaking and sets . The bit is then never modified until the clock reaches again. Then, during the polling phase, each agent counts how many agents with and how many with she sees. At the end of the phase, each agent sets their output bit to the most frequent value of observed during the polling phase. We want to show that, for all agents, the latter is w.h.p. (the most frequent initial opinion among sources).

5.1.2 Analysis

We prove that at the end of the last spreading phase w.h.p. all agents are speaking and each agent has with probability for some positive constant (where the dependency in is monotonically increasing), otherwise. From the Chernoff bound (Corollary A.1) and the union bound, this implies that when at the end of the polling phase w.h.p. each agent learns .

Without loss of generality, let , i.e. .

The analysis is divided in the following lemmas.

Lemma 5.1

At the end of the boosting phase it holds w.h.p.

 k(1)1+k(1)0 ≥(k1+k0)γphase3logn⋅{1}{k1+k0n−2√nlogn}, (5.10) k(1)1k(1)0 ≥k1k0(1−√9γphasek0).
• First, we prove (5.9). By using Fact 4.1, we have

 E[k(1)1+k(1)0] =k1+k0+(n−k1−k0)(1−(1−k1+k0n)γphaselogn) (5.11) ≥k1+k0+(n−k1−k0)(1−e−k1+k0nγphaselogn).

We distinguish three cases.

Case . By using Fact 4.1 again, from (5.11) we get

 E[k(1)1+k(1)0] ≥k1+k0+(n−k1−k0)(1−e−k1+k0nγphaselogn) ≥k1+k0+(n−k1−k0)k1+k0nγphaselogn1+


text:
26 days ago

## Lesson 2 Homework 5.4 Answer Key alabanzas carmageddo

Lesson 2 Homework 5.4 Answer Key

lesson 2 homework practice slope answers

common core lesson 9 homework answers

lesson 4 homework practice dilations answers

lesson 1 homework practice circumference answers

common core lesson 16 homework answers

lesson 1 homework practice lines answers

2 of another ', the 3rd are . Lesson 4.3 Homework Answers Pg 197 - #1-25 odd, 29-33 odd, 42-45 Pg 201 - #1-10 Pg 201 1) RS # JK ST# KL RT # JL. Lesson 14 HomeworkNYS COMMON CORE MATHEMATICS CURRICULUM 5 4 3. At Lauritas Bakery, 7 9 . 2. engage n . Title: Mod.. Fractions, Decimals, Division. Practice 350+ Key Math Skills.. Eureka Math Homework Helper 20152016 Grade 5 Module 2 Lessons 129. . Defend your answer using knowledge of place value and . Lesson 2 : Estimate multi .. Answer Key GRADE 5 MODULE 3 . 3. 4 14. 1 25. 2 36. 5 4. 6 15. 3 26. 4 37. .. Answer Key Lesson 1.2 Practice Level B 1. 3.4 cm 2. 1.8 cm 3. 2.1 cm 4. 25.5 5. 29 6. 6 7. 8. congruent not congruent 9. 10 . Dunkirk to Allentown 5 4.1 mi;. PARKDALE MATH HOMEWORK. Home; Kindergarten; 1st Grade; 2nd Grade; 3rd Grade; 4th Grade; . Grade 4 Module 2 HW Answer Keys Comments (-1) Grade 4 Module 3 HW .. Unit C Homework Helper Answer Key Lesson 7-4 Subtracting Algebraic Expressions 1. 14m 5 8m 2. 13m 9m 4 3. a. 8m 5 2m b. 6m 5 4. 2x 9 5. 3x .. Below, you will find links to LearnZillion videos that will help you throughout Module 3. Below the videos, you will find the Problem Set with answers, the Homework .. Unit 2, Lesson 10 and 11: Answers to Homework on the Reactions of Alcohols Page 63, Q 1 4 1a) substitution reaction b) addition reaction c) elimination .. Video outlining procedures to arrive to correct answers for released . Grade 5 EngageNY Eureka Math Module 4 Lesson 28 Homework . Homework Help 5 uploaded a .. 5 4. 2 5.a. The slope of . The slope of Conveyor 2 is 4. b. Conveyor 1 Lesson 5-4 Unit Rates and Slope . Unit C Homework Helper Answer Key 12. a. Check .. Unit C Homework Helper Answer Key Lesson 4-4 Distance in the Coordinate Plane 1. 5 mi 2. 3.9 . 2. 8 3. a. Answers will vary. b. 1 4. 2 5. 4 6. a. 43,425 125x .. Homework And Remembering Grade 4 Answer Key . To download free math expressions homework and remembering grade 2 . To download free homework book 2 answer key you .. Save Time Lesson Planning.. Welcome to 5th Grade Go Math Homework. Here you will be able to print Homework in case you have forgotten your book at school. Be prepared for the upcoming chapter .. Answer Key GRADE 5 MODULE 2 . NYS COMMON CORE MATHEMATICS CURRICULUM 6 Answer Key Lesson 2 Homework 1. a. 972 3. $6,000 b. 18,972 4.$28,466 2. a .. Lesson 5.4: Practice: p.83: 5.5 . as a completely free McDougal Littell Algebra 2 Practice . Sladers free McDougal Littell Algebra 2 Practice Workbook answers.. Prev - Grade 5 Mathematics Module 4, Topic B Overview. Next - Grade 5 Mathematics Module 4, Topic B, Lesson 3 . Grade 5 Mathematics Module 4, Topic B, Lesson 2.. Eureka Math is probably very different than your math classes in school or the way you learned math. It is not that one way is better than the other, the key is the .. Answer Key Lesson 5.4 Practice Level B 1. 8 2. 16 3. 5 4. 15 5. 12 6. 6 7. a. M(2, 4); P(2, 1) b. N(0, 1); KP 5 4 and KN 5 6 therefore KP 5 2} 3 KN. 8. (23, 21) 9. (5 .. Lesson 4.1 Graph Quadratic Functions in Standard Form Lesson 4.2 Graph Quadratic Functions in Vertex or . Algebra 2 -- Chapter 4: Quadratic Equations and Factoring .. Answer Key Lesson 5.3 Practice Level B 1. 19 2. 288 3. 868 4. No; you dont know that DA} and DC} are to the rays. 5. No; you dont know that D is to rays.. Fractions, Decimals, Division. Practice 350+ Key Math Skills.. and 4-digit numbers by the numbers 29. You can expect to see homework that provides . Lesson 2.1 ALGEBRA .. This page has answers to workshop homework. . Lesson 2 All In One - Lesson 3 . Control A sking Bids Slam Cue Bidding Slam Bidding 202 Roman Key Card RKC Q Ask .. answers in the form of fractions or whole numbers. . NYS COMMON CORE MATHEMATICS CURRICULUM Lesson 5 Homework 5 4 2.. Lesson 4 Homework Practice . Lesson 5 Homework Practice .. Lesson 2 Homework Practice Absolute Value Identify the opposite of each integer. 1. 10 10 2. 25 25 3. . 5. 4 4 6. 15 15 7. 8 8 8.. NYS COMMON CORE MATHEMATICS CURRICULUM . NYS COMMON CORE MATHEMATICS CURRICULUM 5Lesson 9 Homework 1 Lesson 9: .. Lesson 14 HomeworkNYS COMMON CORE MATHEMATICS CURRICULUM 5 4 3. At Lauritas Bakery, 7 9 . 2. engage n . Title: Mod.. 42 Homework Helper Lesson 1 : . answer as a statement. 4. Kyas mom drove 4 km 231 m from work to the grocery store.. All of the answer keys on this page are created from the homework pages within each Module. The answer key will only have the odd number problems completed.. Answer Key GRADE 5 MODULE 2 Multi-Digit Whole Number and Decimal Fraction Operations A STORY OF UNITS. Module 2: . 2 Lesson 4 Answer Key 5 2 Homework 1. a.. Unit E Homework Helper Answer Key . Answers will vary. Lesson 11-2 . 5 4. a. A, B, C b. 1 20 5. 0.962 6. 3 4 7. a. 38 63 b.. TG Grade 4 Unit 8 Lesson 4 Answer Key . 2 5,4 5 B.* 2 8, 6 . Answer Key Lesson 4: Comparing Fractions 12.. Grade 5 Module 2 Lessons . Math Terminology for Module 2. New or Recently Introduced Terms. Decimal Fraction .. Prev - Grade 5 Mathematics Module 4, Topic B Overview. Next - Grade 5 Mathematics Module 4, Topic B, Lesson 3 . Grade 5 Mathematics Module 4, Topic B, Lesson 2.. Grade 4 Unit 5: Big Numbers, Estimation, . Selected Answers. 5-2. . Study Link 5-4 English Espaol For problems . cd4164fbe1
she is doing homework
fun art homework
what is the first homeward bound movie
my dog ate my homework book
homework grids year 2
middle school homework binder
evaluate homework and practice module 6 algebra 2
the homework app - your class assignment planner
biography year 6 homework
imagem do homework


text:
# How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance

I was working in my project when I was struck by the question of whether it would be necessary, or at least cautious, prevent overflow and underflow in the calculation of these two distances.

I remembered that there is an implementation of the calculation of the hypotenuse to prevent this. Most languages implementers, and is known for Hypot

The calculation of the Euclidean distance remains the same "pattern" and I thought that if Hypot() controls the overflow and underflow should also beware of the Euclidean distance. I've disappointed to note that the language we use, and others, do not control the overflow and underflow for calculating distance. Will not worth spend this "additional effort"?

I did a searchs and came to a question in Math.StackExchange

There is no definitive answer to this issue and is somewhat old. The first thing I wondered is: Will okay? I think that yes, seeing that is a generalization of the same procedure that performs Hypot().

I decided to extrapolate this concept to the Mahalanobis distance. The original is as follows:

$$D_M(X,Y,L) = \sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i}\right)^2}$$

Since $L$ is the vector of eigenvalues.

And my proposal is this:

$$D_M(X,Y,L) = C\sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i }\frac{1}{C}\right)^2}$$

That is the same to:

$$D_M(X,Y,L) = C\sqrt{\sum_{i=1}^{n}\left(\frac{X_i-Y_i}{L_i C}\right)^2}$$

And $C$ is the max value from the $|(X_i-Y_i)/L_i|$:

$$C = \max_{i}\left(\mid\frac{X_i-Y_i}{L_i}\mid\right)$$

Is it okay?

• Did anyone could indicate whether this is correct? – Delphius Mar 14 '15 at 19:09

Assuming the $L_i$ are nonzero, such an algorithm will probably suffice in mitigating overflow issues, by analogy to the analysis done for norms; the Mahalanobis distance is like a weighted norm.


text:
Current Densities in Density Functional Theory

Elliott LiebPrinceton University

It is well known that any given density $\rho(x)$ can be realized by a finite energy determinantal wave function for $N$ particles. The question addressed here is whether any given density $\rho(x)$ and current density $j(x)$ can be simultaneously realized by a (finite kinetic energy) determinantal wave function. In case the velocity field $v(x) =j(x)/\rho(x)$ is curl free, we provide a solution for all $N$, and we provide an explicit upper bound for the energy. If the velocity field is not curl free, there is a finite energy solution for all $N\ge 4$, which uses the recent smooth extension of the Hobby-Rice theorem, but we do not provide an explicit energy bound in this case. For $N=2$ we provide an example of a non curl free velocity field for which there is a solution, and an example for which there is no solution. The case $N=3$ with a non curl free velocity field is left open. (Joint work with Robert Schrader.)

Back to Semiclassical Origins of Density Functional Approximations


text:
# Which metrics to focus on classification problem with imbalanced classes

Currently, I need to work on a binary classification project (e-commerce), where the buyer class (class 1) is a minority class and is the class of interest. Building a classification model has two types of error;

For the minority class class 1:

FP means we have predicted 1, while the actual class is 0, i.e. we classify a non-buyer as a buyer (precision gets lower).

FN means that we have predicted 0, while the actual class is 1, i.e. we miss an actual buyer (recall gets lower).

My question is what metrics I should use to assess different models. Apparently, accuracy is not a very good metric, due to imbalanced classes.

For both classes I will get some metrics, i.e. precision, recall and f1-socre. So where should I focus more?

P.S. Given extra information, that a non-buyer has a small cost and a buyer has some good revenue, would it change the metrics I should focus on?

For both classes I will get some metrics, i.e. precision, recall and f1-socre. So where should I focus more?

For binary classification, we usually have one precision and recall / F1 score. and it is usually on "positive" class. Trying to target on improving F1 will be a good practice.

Cohen's Kappa is another good metric for imbalanced problem. Details can be found in this post.

Cohen's kappa in plain English