A bit resistant to disruption
 

/*
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.

Depending on the answer, try to minimize the expected failure rate or
maximize the expected LED flash rate in the following use case:
*/

#define NCELLS 10 // number of cells

extern void sLed(int x); // 0: LED on green then off
// 1: LED on red then off.
extern int eRead(int j); // Read a cell.
extern void eErase(int j); // Erase a cell to 0.
extern void eProgram(int j); // Program an erased cell to 1.

int bRead(void); // Return 0 or 1 according to bit state.
void bToggle(void); // Change the state of the bit.

// Declarations and code for bRead/bToggle go here

int main(void)
{
int vState;
vState = bRead();
while(1)
{
sLed(vState);
bToggle();
vState = !vState;
}
return 0;
}

/*
Assume eProgram, eErase, sLed each last 1 second; everything else is
comparatively instant; a disruption occurs with odds p each second;
unspecified eRead values are assigned at random with mean 0.5; the LED
is off following disruption; a failure is a violation of the
requirement: if a disruption occurs with the LED on in some color, then
the first time the program lights a LED it must be with that color.


Notice that disruption without warning is the standard under which most
real-life hardware actually operates (with the exception of systems with
physical protection against adversarial reset and a power reserve with
means to sense imminent power loss), even though this is often left out
of the specification. And that real disruption-surviving media (EEPROM,
Flash, CDRW, though not battery-backed SRAM) do have the limitation that
read after interrupted change of state sometime gives an unstable
result. While "programming a cell that is not erased cause undefined
behavior" is not the rule, it can exist due to a poorly specified API,
an overcautious hardware specification, or in some cases due to tue
hardware limitations.

The problem is derived from actual requirements in a Smart Card. This is
neither homework, nor an attempt to gather brainpower for free: I'm the
author of the problem and have conclusively determined the feasibility,
with a concise proof. A similar problem "A bit in bottles" is in
rec.puzzles, some of the replies contain answers, and I committed mine.
http://groups.google.com/group/rec.p...892b3cf88af0de

Francois Grieu
*/

Re: A bit resistant to disruption
 

Francois Grieu <fgrieu@gmail.com> writes:
>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.

This is a complete sentence defining the »objective«, which
actually does not allow for any further requirements to be
listed later. Otherwise it would need to include a clause such as:

»... to implement a single bit according to requirements
given below.«.

For example, if I would write »The objective /is/ to
calculate the sum of 2 and 3.« The structure of this
sentence means the objective is defined once and for all.
I can not add any requirements (»propertier«) to be met later.
Otherwise, I would need to write »One /part/ of the objective
is to calculate the sum of 2 and 3.« or »The objective is to
calculate the sum of 2 and 3 fulfilling the following properties.«
or so.

But the sentence cannot be understood as it is written, because
what it means for a bit to be »resistant to disruption« is unknown.
(At least to me, that is.)

>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().
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯
I thought the hard case was a disruption during the execution of bToggle().
If I can assume that it is not being interrupted, why can't I then
implement bToggle in the most obvious way?

Re: A bit resistant to disruption
 

On 2010-02-07, Francois Grieu <fgrieu@gmail.com> wrote:
> 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.

Note that the power can go out at any time while bToggle
is executing, creating an obvious ambiguity: did this outage occur
before or after the bit was toggled?

What if the power goes out while the the expression bToggle() is
evaluating, but before the call has taken place? What if the power
outage occurs just after bToggle has been called, and is returning?

In the event of a system disruption such as a power loss, the best that
we can ensure is that the data is /consistent/. There is no way to
ensure that the data has the absolutely most recent value.

For instance, a database transaction to update some records either
did happen or did not happen; the database is not in some in-between
inconsistent or corrupt state.

A single bit cannot ever be inconsistent!

Re: A bit resistant to disruption
 

Stefan Ram a écrit :
> Francois Grieu <fgrieu@gmail.com> writes:
>> 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.
>
> This is a complete sentence defining the »objective«, which
> actually does not allow for any further requirements to be
> listed later. Otherwise it would need to include a clause such as:
>
> »... to implement a single bit according to requirements
> given below.«.

These requirements are properties a) b). I stand corrected.

> For example, if I would write »The objective /is/ to
> calculate the sum of 2 and 3.« The structure of this
> sentence means the objective is defined once and for all.
> I can not add any requirements (»propertier«) to be met later.
> Otherwise, I would need to write »One /part/ of the objective
> is to calculate the sum of 2 and 3.« or »The objective is to
> calculate the sum of 2 and 3 fulfilling the following properties.«
> or so.
>
> But the sentence cannot be understood as it is written, because
> what it means for a bit to be »resistant to disruption« is unknown.
> (At least to me, that is.)
>
>> 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().
> ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯
> I thought the hard case was a disruption during the execution of bToggle().

No. If there is a disruption during bToggle, what the next undisrupted
bRead() returns is left unspecified.

> If I can assume that it is not being interrupted, why can't I then
> implement bToggle in the most obvious way?

Implement bToggle as you wish. The difficult requirement is a), given
that eRead may return unstable data.

Francois Grieu

Re: A bit resistant to disruption
 

Francois Grieu <fgrieu@gmail.com> writes:

Given:

>extern int eRead(int j);
>extern void eErase(int j);
>extern void eProgram(int j);
>void mySafeProgram(int j)

Wanted:

>the result given by any two undisrupted bRead() is the same
>unless bToggle() was invoked in-between.

So, what about the following implementation?

int bRead( int const j )
{ int const value = eRead( j );
if( value )mySafeProgram( j ); else eErase( j );
return value; }

Re: A bit resistant to disruption
 

On 2010-02-07, Francois Grieu <fgrieu@gmail.com> wrote:
>
> The objective is to implement a single bit resistant to disruption,
>

As has been said, a single bit cannot be "inconsistent" in the
sense that a database or complex structure might be. If you want
it to hold across power failures, this is likely a hardware issue.

bit ^= 1;

is likely to be a single instruction on your hardware so if you
#define Toggle() as such, there's nothing more that can be done
via software.

Re: A bit resistant to disruption
 

Kaz Kylheku wrote:
> On 2010-02-07, Francois Grieu <fgrieu@gmail.com> wrote:
>> 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.
>
> Note that the power can go out at any time while bToggle
> is executing, creating an obvious ambiguity: did this outage occur
> before or after the bit was toggled?

This is why after bToggle() is disrupted, the result of the next
undisrupted bRead() is left unspecified.

> What if the power goes out while the the expression bToggle() is
> evaluating, but before the call has taken place? What if the power
> outage occurs just after bToggle has been called, and is returning?

Count that as disrupted bToggle().

If you want a "falsifiable" test, consider the use case given. Any
correct bRead/bToggle pass this test. Any bRead/bToggle that pass this
test can be turned into a correct bRead/bToggle2 by having bToggle2
invoke bRead and discard the result then invoke bToggle.

> In the event of a system disruption such as a power loss, the best that
> we can ensure is that the data is /consistent/. There is no way to
> ensure that the data has the absolutely most recent value.

Agreed.

> For instance, a database transaction to update some records either
> did happen or did not happen; the database is not in some in-between
> inconsistent or corrupt state.

Agreed.

> A single bit cannot ever be inconsistent!

With actual physical EEPROM or Flash, after a change of a cell has been
disrupted, two readings without a change are not guaranteed to return
the same value. This is because a cell is read by comparing the charge
in the cell to a reference value, with some uncertainty, and that charge
only changes slowly (in the order of a millisecond, and a power loss, at
least a deliberate one as in short circuit, occurs faster than that).
Note this is one area where SRAM + battery backup is better (positive
feedback between the two sides of a SRAM cell makes it inherently
stable, or at least makes metastability plain unobservable). All this
stuff is very often overlooked, and gives rise to all kind of subtle and
hard to track issues, especially when temperature changes and when
disruption is frequent or/and adversarial (which must be assumed in
Smart Cards, especially when remotely powered).

One usual solution is that after reading a bit as erased, you erase it
again; and after reading it as programmed, you program it again
(positive feedback with software); so that next time you read, you'll
get a stable value. A relatively easy (I would not say trivial) tweak
using a second bit avoids premature wear out after things have
stabilized. You then have a "bit" in the usual sense and can use it to
perform e.g. atomic database transaction using classical algorithms.

But in the present problem things are made complicated by prohibition of
over-program of cells.


Francois Grieu

Re: A bit resistant to disruption
 

Stefan Ram a écrit :
> Francois Grieu <fgrieu@gmail.com> writes:
>
> Given:
>
>> extern int eRead(int j);
>> extern void eErase(int j);
>> extern void eProgram(int j);
>> void mySafeProgram(int j)
>
> Wanted:
>
>> the result given by any two undisrupted bRead() is the same
>> unless bToggle() was invoked in-between.
>
> So, what about the following implementation?
>
> int bRead( int const j )
> { int const value = eRead( j );
> if( value )mySafeProgram( j ); else eErase( j );
> return value; }
>

Assume bRead() just has returned 1.
A disruption occurs.
bRead() is called again.
A disruption occurs during that bRead(), while it is doing
mySafeProgram(), sometime during eErase() or eProgram(); say, in between
to simplify.
bRead() is called again without disruption, and returns 0.

Property a) is violated, regardless of how you implement bToggle, which
you did not specify BTW.

Francois Grieu

Re: A bit resistant to disruption
 

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

Re: A bit resistant to disruption
 

On 2010-02-07, Francois Grieu <fgrieu@gmail.com> 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.