Petersen's Algorithm.

It's solution to problem of synchronizing two processess (running programs) wanting to enter critical section of code (section that cannot be accessed by more than one process at the same time).

Using global variables (that indicate which process[-es] want to enter critical section, and which process waits) and simple programming instructions we can ensure that only one process enters critical section at given time.

Pseudocode:
var
  process1wants: boolean := false;
  process2wants: boolean := false;
  whoWaits: 1..2 := 1;

process P1;
begin
  while true do
  begin
    personalAffairs;
    process1wants := true;
    who_waits := 1;
    while process2wants and (whoWaits = 1) do {nothing};
    criticalSection;
    process1wants := false;
  end
end;

process P2;
begin
  while true do
  begin
    personalAffairs;
    process2wants := true;
    who_waits := 2;
    while process1wants and (whoWaits = 2) do
    criticalSection;
    process2wants := false;
  end
end;

Basics of Concurrent Programming.

Concurrent work is multiple works happening at the same time, processor time quants are divided among many processes.

Process is a running program.

Thread (lightweigh process, LWP) is object inside heavyweight process that has it's own control & that shares resources with other threads in the same process.


Critical Section.

Critical section is a code section that can be accessed by only one process or thread at the same time.

Critical section has uses for example in banking: we do not want data to be overwritten as it's written by other process, or read during writing.

Example pseudocode:

process P;

begin
  while true do
  begin
    personal_affairs;
    begining_protocol;
    critical_section;
    ending_protocol;
  end
end;

Readers & Writers.

In computer science, the readers-writers problem is an example of a common computing problem in concurrency.

Shared resource is abstracted as a Reading Room.

More than one Reader may be in a Reading Room, but if writer is in a Reading Room - no one else can be there.


An example algorithm for handling the readers-writers problem is as follows:

Reader's beginning protocol:
  reader waits (goes asleep), if there's writer in a reading room.

Writer's beginning protocol:
  writer waits (goes asleep), if there's someone in a reading room.

Reader's end protocol:
  if is last exitting person, then awakens & lets writer in - if writer waits.

Writer's end protocol:
  if readers wait, then awakens them all, otherwise, if writer waits, awakens one.


There should be a limit on maximum number of readers let in in a reading room, when writer(s) is/are awaiting.


See also: Petersen's Algorithm, Classic Concurrency Problems.

Automated Tests.

Application Design & Use Cases.

Often, when a customer orders application, she or he orders a collection of a certain functionalities.

For example:
- logging into online email application,
- deleting all spam in spam inbox,
- logging off automatically after a given time,
- configuring email sorting preferences,
- ...

Use cases are means of specifying these functionalities, defined by a number of steps (click here, scroll here, type something here, read report's field #n, etc ...).

A minimal set of use cases often determines how user interface should look, is often a formal requirement for ordered application functionalities - can be a part of the business contract between a customer & a developer company.


Automated Tests, Changes & Debugging.

Often tests for use cases can be automated, can be performed after any change is introduced into the code ... just before program's compilation, just before running an application, or at any other convenient moment.

By using Automated Use Case Tests, programmers can be comfortable that when they (or their teammates) change parts of the code, the older parts of the code (previous functionalities) that they are responsible for - won't prove erroneous after the new code additions.

Automated Use Case tests often show when part of the code is erroneous after changes, and while these are far from being 'proofs of code's correctness', these are extremely practical nevertheless. Even if not every error is caught by these - carefully designed tests can quickly find basic functionality failures. Other errors can still be found & fixed using other methods, and it's still easier to fix one error than multiple overlapping ones.

More than that - carefully designed automated tests can help programmer to create 'Mental Test Harness' that let's them more boldly & quickly do larger changes in code without inspecting the same things over & over, without fearing of application breakages so much.

This also builds Trust & Responsibility in the teams - with tests it's quick & easy to find out when someone breaks other teammate's code parts - at early stage of failure at that, so it can be addressed before error turns to be too complex to address quickly, before true stress, psychological dramas & employee firings start, before project's budgets & time schedules are endangered.

In many ways, Automated Tests help to develop applications with much more of the speed & security, with only a small amount of extra code at start (tests have to be designed & written too) & with a small amount of maintenance (when requirements change, tests have to be modified).


Documentation & Automated Tests.

Important aspect of code's quality are automated tests and documentation.

Developers should not write in documentation anything they please, there should be formal standards on what to write and how.

Class documentation should state the Contract between class user and class creator - class responsibility, invariants, what results code provides on which conditions. Results are not only returned values of methods, but also exceptions thrown, state changes, methods called and events raised.

As of how classes should be documented - there's for example Javadoc writing guidelines and requirements, these are about style, keywords and syntax.


Automated Tests for each of classes should be grouped in a single file.

Within that file many tests can be provided, one or more tests for each of tested class' methods.

Tests should check if documented contracts are intact, should check every of 'border criteria'.

Tests can also be written for software's use cases.

... for Java's automated testing tools, check, if You wish:
- JUnit 5,
- EasyMock.


See also: Software Development & Quality.

Contracts.

Introduction.

Design by Contract is the Software Collaboration Method.

Contract / between class user and class author / should state under which condition class will provide it's services to class user, and what these services are.


Contract.

There are Preconditions, Postconditions and Invariants that regulate contract.

Precondition is a condition that is required for something to happen. Precondition can be simple or complex, complex precondition consists of multiple simple or complex preconditions as well.

Postcondition is something that is guaranteed to happen if preconditions are met & program behaves correctly.

Invariants is something that is guaranteed to hold, at least in observable moments in time, or perhaps even all the time.


If class user provides 'correct' / or using alternative wording: 'legal' / preconditions to object, methods will ensure that postconditions are met.

Invariants are always met / though some disagree, for there's 'observable moment' argument /, or contract is broken.


Examples for Preconditions:

- requirements for method arguments allowed values,
- concurrency requirements,
- perhaps more.


Examples for Postconditions:

- program's process(-es) will compute and provide results correctly,
- program will finish within the agreed time frame in at least 90% of situations,
- perhaps more.


Examples for Invariants:

- heat in Reactor will never go above the Critical Value,
- variable 'divisor' will never have '0' value,
- variable 'divisor' will never have '0' value during computations phase,
- perhaps more.


Inheritance / in simple words /.

To not break contract, following conditions must be met:

1. subclasses must require no more than it's neccessary for superclass to work correctly / but can require less /.

2. subclasses must meet all requirements of superclass / but perhaps can give more /.

This is related with the Liskov's Substitution Principle / LSP /.


Exceptions in Java.

When contract is broken during Runtime, an Exception should be thrown.

A few thoughts on code quality - mostly for Java, but can be abstracted and used with different technologies.

In my opinion java code of quality should have following properties:

1. Proper naming of classess, methods, variables and constants.
2. Single, properly defined and documented responsibility of each class and method. No unneccessary code (to remove code duplication you can use constants (final keyword, UPPERCASE_NAMES) and split methods with large chunks of code into few smaller methods so you can reuse them. To ensure single responsibility of method or class move some code into another method or class. Single responsibility class or method is more reausable and easier to document, read, test and modify. [or to break if someone wants to try firing quality coder].). Single responsibility of method may involve calling more than one instruction as long as it is considered atomic. For example: changeStateWithSideEffect(...);
3. Documented methods headers (first lines of methods and all information therein, including variable names) according to javadoc documentation.
4. Use of 'assert' keyword, software contracts, preconditions, postconditions and invariants.
5. Fitting 'a complete code part' on a 'single screen', if possible and worthwhile; ... easier thinking, less scrolling, perhaps more.

Later JUnit/Easymock automated tests can be added to build test harness.

Also, code should be properly formatted.

Commits / to code repository, using technologies such as SVN or Git / should be commented.

Methods should be abstract, empty or final.

Ideally, methods should consists of three instructions. init(...); transform(...); return [(...)]; Complex instruction counts as single instruction;

There can be more requirements / for example: coding in idiomatic way / , but in practice it's almost perfect if these are used. Professionals after all have no time to comment code, or they want to be priceless and unfirable by bosses, in a not-so-nice, unfair way.


See also:
> [ Design by Contract ],
> [ 'SOLID': Five Principles for Object-Oriented Software Quality ],
> [ Software Development & Quality ].

'Three Spies Problem'.

By node in this post we understand internet device, network of such form a graph.

Communication from node A to node B can go through other transitory node T or through
transitory nodes T₁, T₂, ... T_n.

Then we can reach node B with message with 100% success rate if transitory node(s) won't fail.

We can send messages via transitory nodes in many ways.

Let's assume we have three transitory nodes, that is - T₁, T₂ and T₃.

Then we can transmit a message:

1. Via random or predetermined node.

If that node fails, signal needs to be retransmitted.

2. Via all nodes at once, whole message.

It succeeds as long as at least one transitory node does not fail, but signal can be captured easier.

3. Via all nodes, 1/3 of message through each.

Transmission fails if at least 1 node fails. But lost part(s) of message can be resent later. There's less risk of capturing whole signal by opposing forces as well.

4. Via all nodes, 2/3 of message through each. (different 2/3 via each).

Transmission succeeds 100% of time when at least two nodes won't fail. Whole signal is captured if 2 transitory nodes are captured. When one node won't fail, 2/3 of signal are sent, then rest can be transmitted again.

When splitting signal into 2/3, whole has to be encrypted, then split into 3 parts, concatenated (joined) appropriately, then ecrypted each 2/3 again. It's difficult to decrypt message or its parts that way if one has no private keys.

For security, transmission can occur via different nodes (different internet route paths for example), and not at the same time. This can be done via three different internet cafes for example.


See also, if You wish, ... :
- 'Incoming Cipher Crisis'.

Object State & Context.

About.

State / pl: 'stan' / can be defined in many ways.


Finite State Machine.

A finite-state machine (FSM) / pl: 'automat skończenie stanowy' / is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time.

The FSM can change from one state to another in response to some input.

States can be represented using circles; the change from one state to another is called a transition / pl: 'przejście', 'funkcja przejścia' / and can be represented on image using an arrow that points from one circle to the same or another circle, and is associated with input(s) that triggers a given transition.

An FSM is defined by:
- a list of its states,
- initial state / pl: 'stan początkowy' /,
- optionally acceptance (final) state(s) / pl: 'stan(y) akceptujący(-e)', 'stan(y) końcowy(-e)' /,
- transitions,
- inputs that trigger appropriate transitions.

Initial state can be represented by colouring nodes, for example - we can have black circles for non-initial states and green circle for initia state.

... for more, feel free to look: [ Finite-state machine on Wikipedia ].


Finite State Object.

One can look at object, at it's variables. Variables can be - and are - represented as list of 0's and 1's. Variable values can be concatenated into one list. All of possible permutations of 0's and 1's in this list represent all of possible of this object's states. State's name (label) can be a binary number, a list of 0's and 1's that changes when state changes. In this case we consider variables not by their's names, but by positions of their the values on the concatenated
state-bit-list.

Or, we can look at a state as on a combination of variable values, when we assign a list of 0's and 1's to each of variable names.

In both cases, object's type is important part of object's state, like a variable with it's value, represented by 0's and 1's, as any of information can be.

For details of the differencies between permutations and combinations, feel free to: click.

Similarly, object's methods can be seen as 'families' of transition functions / pl: 'rodziny funkcji przejścia' / between object's possible states. Object, method's name & possible parameter(s) - if any - passed to the method, together determine unambiguously / pl: 'jednoznacznie' / which transition to trigger.

In this way, object can be seen as finite state automaton, also called FSM - Finite State Machine.

... i call FSM implemented as object an FSO - Finite State Object.

In FSO, each of possible states can be represented graphically as a dot labelled with its list of 0's and 1's ... and method(s) - if any - is/are arrow(s) leading from one state to one or more other state(s). Obviously not every state must be connected with every other possible state. Not every method must change object's state as well ... then there's either no arrow associated with this method, or there is/are arrow(s) that point(s) to the same FSO that it originated from - useful when we want certain 'side effect(s)' to happen as a part of transition (see below).

FSO can have the 'side effects' that can trigger / pl: 'wyzwalać' / on transition, can send message(s) to other FSO(s), can call method(s) on other FSO(s). That way, Directed Graphs of FSOs can be seen as complete models of programs, that can be executed as well.


Context.

We can select a group of objects and contain it in another object, then states of contained objects are parts of grouping object's state. Anything outside connected to grouping object can be named 'context' / pl: kontekst /.

Speaking more abstractly and precisely, context is 'external state', is combined state of what surrounds the object, what is within certain distance from the considered object (we include objects' identities as a part of combined state here).

... and distance can be measured in many ways - not only in meters in straight line on map. It can be, for example, number of bus stops on the way to target. Or average time to reach 'Point B' from 'Point A'. Or number of nodes passed in graph, with weighted or unweighted edges.


Mind States.

I think and feel that buddhism's concept of Mind can be explained as similar to Finite State Machine(s).

For more details, feel free to look: [ Self-Improvement and Mind States ].


Links.

- Automata, Languages & Computations / Work in Progress Still /.