Skip to content

Resource Locking Circular Storage with Partial State Operations

Jump to bottom
hdemarco4 edited this page Sep 12, 2017 · 1 revision

Resource Locking - Circular Storage with Partial State Operations

  1. Project Name

Resource Locking - Circular Storage with Partial State Operations 2. Project Description

This project involves creating a program than gains access to a resource. Resource access is controlled by a resource-locking software device that maintains a circular store of bits. The device unlocks the resource whenever all of the bits in the store have the same value.

In this document, the symbol F represents the value false. The symbol T represents the value true. Thus, a device unlocks a resource whenever all values in the store are set to T or all are set to F. The contents of a device are described by a pattern, shown as values within square brackets in this document; for example, [T T T F T F T]. The symbol – is used to represent an unknown or undisclosed valued. The symbol ? is used to represent a request to disclose a value. 3. Resource-Locking Software Device Specification

The number of bits stored is specified when the device is created.
Each bit is arbitrarily initialized to F or T when the device is created. For example, one potential initial state such a device is [T F F T F T].
The device maintains the bits in a circular store. The store behaves like a circular shift register with values T or F.
The device may rotate the bits a random number of times. This operation is called spin.
The device permits limited observation and modification of its state.
A subset of the bits may be observed following a spin.
The number of bits that may be disclosed per observation is specified when the device is created.
Following an observation, The observed bits may be changed.
Further behaviors and constraints are specified by the set of commands recognized by the device.

3.1 Device Commands

In the following examples, the number of bits stored by the device is 4 and the number of bits that may be observed/changed is 2. 3.1.1 Spin ≝ allBitsIdentical? ← SPIN

The device responds to a SPIN command by circularly-rotating the bits of the store, one position to the right, an unspecified number of times. Considering an initial state [T F F T], a single rotation would result in [T T F F]. Another rotation would yield [F T T F]. The actual number of rotation actions is unknowable. (For all intents, it is random.)

The SPIN command returns a boolean value of true if all bits of the store have the same value.

A SPIN command is valid if it is issued immediately following device creation or a PEEK, POKE, or SPIN command.
The result of an invalid SPIN command is unspecified.

3.1.2 Peek ≝ result ← PEEK(request)

The device responds to a PEEK command by revealing partial state information. The PEEK command accepts a request pattern, indicating which of the bits are to be disclosed. For example, the request pattern, [– ? – ?], asks for the values of the bits at locations specified with a question mark.

The PEEK command returns a result pattern, indicating the values of the requested bits. For example, if the current state of the store was [F T T F], then the PEEK request pattern [– ? – ?] would result in the returned pattern [– T – F].

A PEEK command is valid if all of the following conditions are met:
    PEEK is issued immediately following a valid SPIN command
    The number of bit locations to be disclosed specified in the request parameter is exactly equal to the number of observable bit locations specified at creation
The result of an invalid PEEK command is unspecified.

3.1.3 Poke ≝ POKE(pattern)

The device responds to a POKE command by potentially modifying the state of the device. After a PEEK command, the disclosed bits may be set by placing a T or F in the corresponding locations of the pattern parameter. For example, if the PEEK request parameter was [? – – ?], then a POKE with pattern [F – – T] would set the leftmost bit to F and the rightmost bit to T.

A POKE command is valid if all of the following conditions are met:
    POKE is issued immediately following a valid PEEK command
    The pattern parameter specifies T or F in each of the positions that contained ? in the previous PEEK request pattern
The result of an invalid POKE command is unspecified.

3.2 Algorithmic Processing Example The following pseudocode expresses an algorithm that toggles one bit of the register.

SPIN flippattern = PEEK([? ? - -]) if (flippattern[0] == F) then flippattern[0] = T else flippattern[0] = F POKE(flippattern)

  1. Unlocking the Resource The resource is unlocked when all bits in the register are set to the same value; that is, either all are T or all are F.

  2. Questions 5.1 Is there an algorithm to set all bits to 1 that uses only the SPIN, PEEK, and POKE commands? 5.1.1 If not:

    Why does no such algorithm exist? Is there a heuristic that can achieve success in most cases? Explain.

5.1.2 If so:

Describe the approach such an algorithm would take.
Describe an approach to an algorithm that requires the minimum number of commands to unlock the resource.
  1. Device API

You are provided with the specified API for the Device class that implements the resource-locking software device.

  1. Document the Development Process to Deliver an Unlocker of 4-Bit/2-Disclosure Devices

For this exploration, we will consider only a 4-bit/2-disclosure resource-locking device. That is, the circular store contains exactly 4 bits and excatly 2 of the bits may be observed/modified via the PEEK and POKE commands.

You are provided with the required API for the FourBitTwoDisclosureDeviceUnlocker class.

You must document your team's actual development activities and deliver source code for an implementation of the FourBitTwoDisclosureDeviceUnlocker class.

Clone this wiki locally