Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > A bit resistant to disruption

Reply
Thread Tools

A bit resistant to disruption

 
 
Stefan Ram
Guest
Posts: n/a
 
      02-07-2010
Francois Grieu <(E-Mail Removed)> writes:
>A disruption occurs during that bRead(), while it is doing


I do not see how to implement a solution, but by storing
an error detecting code into more than one bit for each
of the values for ON or OFF one could at least /detect/ an
indefinite bit with a certain probability.

 
Reply With Quote
 
 
 
 
Francois Grieu
Guest
Posts: n/a
 
      02-07-2010
Andrew Poelstra wrote:
> On 2010-02-07, Francois Grieu <(E-Mail Removed)> wrote:
>> Andrew Poelstra wrote :
>>> As has been said, a single bit cannot be "inconsistent" in the
>>> sense that a database or complex structure might be.

>> A bit, agreed. The state of a cell, disagreed. See my answer in the
>> sub-thread that you mention.
>>
>> If you want a useful model of an EEPROM cell and don't want to dive into
>> how hardware works, think of a bottle that can only be emptied or filled
>> slowly, and is read by grossly weighting it on a scale giving only
>> light/heavy reading. This is how classic EEPROM and Flash work
>> (multilevel Flash store e.g. 2 bits per cell with a scale having 4
>> readings instead of 2, we don't consider that).
>>
>> (snip)
>> Francois Grieu

>
> I know how Flash and EEPROM work, on a basic level - which is why
> I think you need a hardware solution. You can buffer and checksum
> to validate the data as best you can, but in the end if you lose
> power in the middle of a flash write you may very well be screwed.


I count that as one "I think the answer is: impossible". All the persons
that I know have solved the problem (that's three including me) seem to
have changed their mind at least once.

Francois Grieu
 
Reply With Quote
 
 
 
 
Francois Grieu
Guest
Posts: n/a
 
      02-07-2010
Stefan Ram wrote:
> Francois Grieu <(E-Mail Removed)> writes:
>> A disruption occurs during that bRead(), while it is doing

>
> I do not see how to implement a solution, but by storing
> an error detecting code into more than one bit for each
> of the values for ON or OFF one could at least /detect/ an
> indefinite bit with a certain probability.


Now we are moving into the right direction!

Hints: try to prove impossibility. Any hole in your proof may lead to a
solution. That, or prove a procedure, any hole...

Francois Grieu
 
Reply With Quote
 
Moi
Guest
Posts: n/a
 
      02-07-2010
On Sun, 07 Feb 2010 18:51:25 +0100, Francois Grieu wrote:

> /*
> Disclaimer: This is a hard problem, only minimally disguised into
> something on-topic for comp.lang.c
>
> You are programming a C99 conforming freestanding implementation.
> Disruption (reset or power off/on cycle) can occur at *ANY* time without
> advance warning, and stops whatever operation is underway. The program
> is re-executed from main() after a disruption.
>
> The objective is to implement a single bit resistant to disruption,
> accessed using two procedures to be written:
> int bRead(void); // Return 0 or 1 according to bit state. void
> bToggle(void); // Change the state of the bit.
>
> These two properties shall be met:
> a) The bit is stable in the absence of Toggle. That is, the result given
> by any two undisrupted bRead() is the same unless bToggle() was invoked
> in-between.
> b) The bit is changed by Toggle. That is, the result given by any two
> undisrupted bRead() is different if bToggle() was invoked exactly once
> in-between and no disruption occurred during that execution of
> bToggle().
>
>
> The only way to store information across disruptions is using a number
> of independent physical EEPROM cells, designated by index j. Access to
> the EEPROM cells is by the following three functions. The properties
> stated for theses functions apply for any fixed non-negative integer j
> less than the number of cells, and "for that cell" is implied
> everywhere.
>
> // Read a designated EEPROM cell; always returns 0 or 1. extern int
> eRead(int j);
>
> // Erase a designated EEPROM cell.
> // After undisrupted eErase, eRead returns 0 until eProgram is invoked.
> extern void eErase(int j);
>
> // Program a designated *ERASED* EEPROM cell. // After undisrupted
> eProgram, eRead returns 1 until eErase is invoked. // Programming a cell
> that is not erased cause undefined behavior. extern void eProgram(int
> j);
>
> An EEPROM cell can be left neither erased nor programmed by a disrupted
> eErase unless that cell was already erased, or by a disrupted eProgram.
> For a cell in such halfway state, eRead returns a value specified only
> to be 0 or 1. That otherwise unspecified value may in particular change
> after disruption (due e.g. to uncontrollable random noise and/or
> temperature and/or voltage drift in the hardware used by eRead), even
> though the sate of cells is unchanged by disruption or/and eRead.
>
> Note: if a cell is not erased (left in a halfway state or programmed),
> an eProgram of that cell is prohibited. A workaround is to use the
> following rather than eProgram():
> void mySafeProgram(int j)
> {
> eErase(j);
> eProgram(j);
> }
>
> Before the first run, all EEPROM cells have been erased. eRead, eErase,
> and eProgram terminate unless a disruption occurs, assuming constraints
> on j and eProgram are met. bRead and bToggle must similarly terminate
> unless a disruption occurs.
>
>
> Can it be done? If yes, what is the minimum number of cells needed? Give
> a proof.


First shot: two hits in my cerebral hash-table
1) alternating bit-protocol (difficult with only one bit at a time ...)
2) Leslie Lamport's reading <--> writing in opposite directions.

NB, I like the problem (though it is not strictly c.l.c stuff

AvK
 
Reply With Quote
 
Francois Grieu
Guest
Posts: n/a
 
      02-08-2010
Moi wrote :

>> Can it be done? If yes, what is the minimum number of cells needed? Give
>> a proof.

>
> First shot: two hits in my cerebral hash-table
> 1) alternating bit-protocol (difficult with only one bit at a time ...)


Nice. However in the present problem there are no errors, only those
pesky disruptions.

> 2) Leslie Lamport's reading <--> writing in opposite directions.


When I wrote "hard problem", I did not mean quite that hard...

> NB, I like the problem (though it is not strictly c.l.c stuff


At least "freestanding implementation" is on topic and exactly describes
the context: digital computer, no error, single process, all variables
lost on disruption, no standard library for persistent storage. And
c.l.c may be one of the best place to reach programmers facing that
issue (minus perhaps the prohibition of over-program, which is what
makes the problem challenging).

Francois Grieu
 
Reply With Quote
 
Moi
Guest
Posts: n/a
 
      02-08-2010
On Mon, 08 Feb 2010 07:26:45 +0100, Francois Grieu wrote:

> Moi wrote :
>
>>> Can it be done? If yes, what is the minimum number of cells needed?
>>> Give a proof.

>>
>> First shot: two hits in my cerebral hash-table 1) alternating
>> bit-protocol (difficult with only one bit at a time ...)

>
> Nice. However in the present problem there are no errors, only those
> pesky disruptions.
>
>> 2) Leslie Lamport's reading <--> writing in opposite directions.

>
> When I wrote "hard problem", I did not mean quite that hard...


I think that your failed eeprom_reset_bit() and eeprom_set_bit()
operations are more or less equivalent to Lamport's "sending messages to another process".
Messages can be lost in transit, your eeprom-operations can fail
because of a crash.
The only difference is that in the eeprom-case there is a sort of tri-state
logic; in the case of lost messages the domain stays restricted
to just two cases.

If I understood the problem correct:
1) the machine can be expected to crash *any moment*, so even while "in recovery mode"
2) an undefined cell (either rewritten or partially cleared) produces a random
value; subsequent reads may yield different values.

My current approach uses a state machine with a kind of graycodes
(maybe necklaces: http://www.theory.csc.uvic.ca/~cos/i...klaceInfo.html ; I am not
sure yet how this should be named)
The guiding idea is that in any state there is a maximal number of
bits that could be undefined (tri-state): the bits that could have been affected
by the previous or next state in the graph.
While recovering this number is two, in "normal operation" it may perhaps be just one.

My guess is I need three or four bits / bottles.
.... still working on it ...

AvK
 
Reply With Quote
 
Francois Grieu
Guest
Posts: n/a
 
      02-09-2010
Moi wrote :
> On Mon, 08 Feb 2010 07:26:45 +0100, Francois Grieu wrote:
>
>> Moi wrote :
>>
>>>> Can it be done? If yes, what is the minimum number of cells needed?
>>>> Give a proof.
>>> First shot: two hits in my cerebral hash-table 1) alternating
>>> bit-protocol (difficult with only one bit at a time ...)

>> Nice. However in the present problem there are no errors, only those
>> pesky disruptions.
>>
>>> 2) Leslie Lamport's reading <--> writing in opposite directions.

>> When I wrote "hard problem", I did not mean quite that hard...

>
> I think that your failed eeprom_reset_bit() and eeprom_set_bit()
> operations are more or less equivalent to Lamport's "sending messages to another process".
> Messages can be lost in transit, your eeprom-operations can fail
> because of a crash.
> The only difference is that in the eeprom-case there is a sort of tri-state
> logic; in the case of lost messages the domain stays restricted
> to just two cases.


Yes I see your point. One redeeming difference is that things are
strictly sequential / singe-process in my case.

> If I understood the problem correct:
> 1) the machine can be expected to crash *any moment*, so even while "in recovery mode"


Yes. Notice this is very real-world.

> 2) an undefined cell (either rewritten or partially cleared) produces a random
> value; subsequent reads may yield different values.


Yes, with one exception: if a cell/bottle was erased/empty, and you
erase/empty it again while a disruption occurs, it remains erased/empty.
The makers of EEPROM will reluctantly accept to give this insurance,
which is self-evident with bottles. There is no equivalent in the other
direction, for you can't program/fill a cell/bottle unless it is fully
erased/empty [or so insisted the makers of my EEPROM].

> My current approach uses a state machine with a kind of graycodes
> (maybe necklaces:http://www.theory.csc.uvic.ca/~cos/i...klaceInfo.html ; I am not
> sure yet how this should be named)
> The guiding idea is that in any state there is a maximal number of
> bits that could be undefined (tri-state): the bits that could have been affected
> by the previous or next state in the graph.
> While recovering this number is two, in "normal operation" it may perhaps be just one.
>
> My guess is I need three or four bits / bottles.
> ... still working on it ...


You are the first poster with a proposition that I won't contradict, and
are so far untouched by the "at least one public change of mind" curse!

> AvK


Francois Grieu
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      02-09-2010
On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
> You are the first poster with a proposition that I won't contradict, and
> are so far untouched by the "at least one public change of mind" curse!


The tricky part, so far as I can tell, is that we can't tell what a
partially-written bit might look like. On the other hand, in theory,
only one write can be interrupted, as I understand it.

Hmm.

Okay, here's an approach. Imagine without loss of generality that our
goal is to toggle the bit in cell 0, and that we have additional bits to
toggle. The bit is "T".

Let's see. Okay, when toggle() is called, we'll start by clearing a working
area. So we have some unspecified number of bits which is our working area,
call them W[0] ... W[N].

The first thing we need to do is be sure that we can recover the previous
value in the event of a disruption. So, necessarily, we need a bit to hold
the known-previous-value. Let's call that W0. But how do we know whether
W0 holds a bit we care about? We need a flag for whether W0 has been written.
Let's call that W1. So, read() should do something like:
if (W1)
return W0
else
return T

What about toggle()? If W1 is set, then it was interrupted during an
operation. It should try to extract the value from W0 and push it back
into T. Once it has done that, it can clear W1 (because it no longer
needs to be able to remember the value in W0), then W0. That reduces us
to the default state, which is that T holds the current bit and we wish
to toggle it.

Given that, we then:
* Copy T into W0
* Set W1
* Erase T
* if T was previously 0, program T
* erase W1
* erase W0

The rationale of this ordering is that, at every time:
* if W1 is set, W0 holds the correct value of T
* if W1 is unset, T is known to be correct

If we are interrupted while setting W1, we were interrupted before we modified
T, so that's not a problem -- T is still at its correct old value. If we
are interrupted while setting W0, we were interrupted before we set W1, so
that's not a problem -- T is still at its correct old value. If we are
interrupted during any of the erasing or programming of T, that's not a
problem -- W0 and W1 are set, so we'll pick up the right value next time
we come in. If we are interrupted during the erase of W1, that's fine. If
it gets erased, it's clear and T has the right value. If it doesn't get
erased, it's still set, and W0 still holds the correct "previous value",
so we'll be in one of the trustworthy intermediate states.

So I think that's it.

So!

// Read a designated EEPROM cell; always returns 0 or 1.
extern int eRead(int j);
// Erase a designated EEPROM cell.
// After undisrupted eErase, eRead returns 0 until eProgram is invoked.
extern void eErase(int j);
// Program a designated *ERASED* EEPROM cell.
// After undisrupted eProgram, eRead returns 1 until eErase is invoked.
// Programming a cell that is not erased cause undefined behavior.
extern void eProgram(int j);

/* default state:
* bit 0 holds the current Durable Bit
* bit 1 is undefined
* bit 2 is clear
*
* during a toggle:
* bit 2 is set
* bit 1 holds the current Durable Bit
* bit 0 is undefined.
*
*/

int
bRead(void) {
if (eRead(2)) {
return eRead(1);
} else {
return eRead(0);
}
}

void
bToggle(void) {
int t;
if (eRead(2)) {
t = eRead(1);
eErase(0);
if (t)
eProgram(0);
eErase(2);
}
t = eRead(0);
eErase(1);
if (t)
eProgram(1);
eProgram(2);
eErase(0);
if (!t)
eProgram(0);
eErase(2);
}

I realized on consideration that I don't need to finish this with
eErase(1), because bit 1 is undefined. Thus, if eErase(2) completes
at the end of bToggle(), the toggle is complete and bit 0 holds the
newly toggled bit. If it doesn't complete, 1 still holds the right
value.

Note that there exists at least one case (previous value was zero, and
a disruption occurred) where 0 is erased twice without having been
programmed.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
Francois Grieu
Guest
Posts: n/a
 
      02-09-2010
Seebs wrote:
> On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
>> You are the first poster with a proposition that I won't contradict, and
>> are so far untouched by the "at least one public change of mind" curse!

>
> The tricky part, so far as I can tell, is that we can't tell what a
> partially-written bit might look like. On the other hand, in theory,
> only one write can be interrupted, as I understand it.


Only one write can be interrupted. But a series of disruptions can lead
to multiple partially-written cells. See below.

>
> Hmm.
>
> Okay, here's an approach. Imagine without loss of generality that our
> goal is to toggle the bit in cell 0, and that we have additional bits to
> toggle. The bit is "T".
>
> Let's see. Okay, when toggle() is called, we'll start by clearing a working
> area. So we have some unspecified number of bits which is our working area,
> call them W[0] ... W[N].
>
> The first thing we need to do is be sure that we can recover the previous
> value in the event of a disruption. So, necessarily, we need a bit to hold
> the known-previous-value. Let's call that W0. But how do we know whether
> W0 holds a bit we care about? We need a flag for whether W0 has been written.
> Let's call that W1. So, read() should do something like:
> if (W1)
> return W0
> else
> return T
>
> What about toggle()? If W1 is set, then it was interrupted during an
> operation. It should try to extract the value from W0 and push it back
> into T. Once it has done that, it can clear W1 (because it no longer
> needs to be able to remember the value in W0), then W0. That reduces us
> to the default state, which is that T holds the current bit and we wish
> to toggle it.
>
> Given that, we then:
> * Copy T into W0
> * Set W1
> * Erase T
> * if T was previously 0, program T
> * erase W1
> * erase W0
>
> The rationale of this ordering is that, at every time:
> * if W1 is set, W0 holds the correct value of T
> * if W1 is unset, T is known to be correct
>
> If we are interrupted while setting W1, we were interrupted before we modified
> T, so that's not a problem -- T is still at its correct old value. If we
> are interrupted while setting W0, we were interrupted before we set W1, so
> that's not a problem -- T is still at its correct old value. If we are
> interrupted during any of the erasing or programming of T, that's not a
> problem -- W0 and W1 are set, so we'll pick up the right value next time
> we come in. If we are interrupted during the erase of W1, that's fine. If
> it gets erased, it's clear and T has the right value. If it doesn't get
> erased, it's still set, and W0 still holds the correct "previous value",
> so we'll be in one of the trustworthy intermediate states.
>
> So I think that's it.
>
> So!
>
> // Read a designated EEPROM cell; always returns 0 or 1.
> extern int eRead(int j);
> // Erase a designated EEPROM cell.
> // After undisrupted eErase, eRead returns 0 until eProgram is invoked.
> extern void eErase(int j);
> // Program a designated *ERASED* EEPROM cell.
> // After undisrupted eProgram, eRead returns 1 until eErase is invoked.
> // Programming a cell that is not erased cause undefined behavior.
> extern void eProgram(int j);
>
> /* default state:
> * bit 0 holds the current Durable Bit
> * bit 1 is undefined
> * bit 2 is clear
> *
> * during a toggle:
> * bit 2 is set
> * bit 1 holds the current Durable Bit
> * bit 0 is undefined.
> *
> */
>
> int
> bRead(void) {
> if (eRead(2)) {
> return eRead(1);
> } else {
> return eRead(0);
> }
> }
>
> void
> bToggle(void) {
> int t;
> if (eRead(2)) {
> t = eRead(1);
> eErase(0);
> if (t)
> eProgram(0); // [B]
> eErase(2); // [A]
> }
> t = eRead(0);
> eErase(1);
> if (t)
> eProgram(1);
> eProgram(2);
> eErase(0);
> if (!t)
> eProgram(0);
> eErase(2);
> }
>
> I realized on consideration that I don't need to finish this with
> eErase(1), because bit 1 is undefined. Thus, if eErase(2) completes
> at the end of bToggle(), the toggle is complete and bit 0 holds the
> newly toggled bit. If it doesn't complete, 1 still holds the right
> value.
>
> Note that there exists at least one case (previous value was zero, and
> a disruption occurred) where 0 is erased twice without having been
> programmed.


This one is incorrect. Assume a disruption where I inserted [A]; now
cell 2 is uncertain. Assume cell 2 is read as 1 during the next bToggle,
and a disruption occurs at [B]; now cells 0 and 2 are uncertain, and
bRead can return 0 (if cells 2 and 0 are read as 0) or 1 (if cell 2 is
read as 0 and cell 0 is read as 1).

Hint: there's nothing to prevent bRead from invoking eErase or/and eProgram.

Francois Grieu
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      02-09-2010
On 2010-02-09, Francois Grieu <(E-Mail Removed)> wrote:
>> void
>> bToggle(void) {
>> int t;
>> if (eRead(2)) {
>> t = eRead(1);
>> eErase(0);
>> if (t)
>> eProgram(0); // [B]
>> eErase(2); // [A]
>> }
>> t = eRead(0);
>> eErase(1);
>> if (t)
>> eProgram(1);
>> eProgram(2);
>> eErase(0);
>> if (!t)
>> eProgram(0);
>> eErase(2);
>> }


> This one is incorrect. Assume a disruption where I inserted [A]; now
> cell 2 is uncertain. Assume cell 2 is read as 1 during the next bToggle,
> and a disruption occurs at [B]; now cells 0 and 2 are uncertain, and
> bRead can return 0 (if cells 2 and 0 are read as 0) or 1 (if cell 2 is
> read as 0 and cell 0 is read as 1).


Okay, I misunderstood the spec. I thought that an erase necessarily
either worked or failed to work, and couldn't leave a cell indeterminate.
Re-reading the spec, I see that isn't correct. That does make this a
lot trickier.

> Hint: there's nothing to prevent bRead from invoking eErase or/and eProgram.


True. I'm not sure how it matters, though; a hypothetical user can just run
bToggle() over and over without ever hitting bRead(), so I can't usefully
rely on anything it does, I don't think. I'm assuming this has to work
in the general case, not just in the specific example case given.

I suspect this could be solved with another bit, but I'm too sleepy to figure
out how right now.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / (E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Disruption & Market Control Lawrence D'Oliveiro NZ Computing 8 04-03-2008 11:48 PM
Script disruption with Macromedia Flash HellPope Huey Firefox 4 08-16-2005 07:42 PM
How water resistant is a water resistant lens? Derek Fountain Digital Photography 2 03-18-2005 11:30 AM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit,Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new! Ionizer Computer Support 1 01-01-2004 07:27 PM
Re: adsl service disruption JM Computer Support 0 07-22-2003 07:53 AM



Advertisments