Washington Technical Resources

Phonetics: 2500 year old Sanskrit grammar in BNF form

2016-05-10T23:01:00.002-07:00

In last post I talked about the Syntax parsing and special X-Bar theory that applies to the natural languages. In this post we'll start our exploration with 2500 years old grammar in Backus Naur Form and move to internal structure of words and syllables.

Sanskrit

My mother tongue is Marathi Language which is a daughter language of Sanskrit and preserves most of the grammatical features of Sanskrit including 8 cases, 3 genders. 50% of the vocabulary is directly from Sanskrit (tat-sama ) and another 25% can be derived by single sound shift (tat-bhava).

3 years of Painful High School Grammar

I took 3 years of Sanskrit in high school but all I remember is sheer pain learning its grammar.

Imagine all those latin conjugation and declination tables ? Well ! Sanskrit has 10 times more tables.
You think French liaison and ellisions are hard ? Sanskrit has most such rules for sound changes.
You think German has long words ? Yes, Sanskrit has that as well. Including famous splitting of prefix and the main verb.

Panini's Grammar

The most authoritative grammar of sanskrit is actually formulated using form similar to modern context free grammars.

Panini developed his Grammar around 500 BC
He used 14 classes of phonemes and taking that as lexical terminal symbols of his grammar described Sanskrit grammar as set of 3,959 rules to describe all grammatically correct ways to construct Sanskrit sentence.

The word factory

Human - a talking animal

Despite our differences all humans are born with an ability for the language most human languages have following properties

30-60 sounds that are put together to make syllables.
The syllables are put together to make words
words form phrases
phrases form sentences
sentences form discourse

Structure of Words and Syllable

How human voice is produced.

Human speech articulation begins in the larynx. The vibrations created there are modified through out the vocal tract which ultimately comes out of the mouth as series of sounds which we understand as sequence of phonemes. Larynx is where the "voice" starts but that sound is progressively modified in the mouth by forming various shapes with our tongue and lips. I have modified the standard diagram to show the schematic of the vocal tract. The most important key concept is this: Our tongue is a very flexible muscle that can form various shapes and that profoundly affects the way we perceive the basic sound that begins at the larynx. [Edited from original here : http://en.wikipedia.org/wiki/File:Illu01_head_neck.jpg.]

That brings us to the next concept. There are two types of sounds viz. vowels and consonants.
When the airflow from larynx is not obstructed we perceive that sound. Anyone how has dealt with waveform of human sound knows that most of the waveform is basically sound of vowels. However the most interesting sounds are generated when the airflow is blocked (or substantially modified) for the brief amount of time. This time frame is seriously tiny compared to rest of the vowel sound and we perceive it as consonant.
In terms of digital signal processing the waveform of the voice that starts in larynx is modified by the resonance of the vocal tract and therefore we apply the convolution of the simplified model on the right side.

Vowels

Vowels take most of the time in speech signal. All consonants are meaningful only in the context of background of robust vowel signal. The larynx is actively producing "voice" during the vowels.
The quality of vowel depends on four attributes.

Height of tongue position- In other words whether the gap between tongue and roof of mouth is closed or open. generally four positions are considered. Open, Open mid,Close mid and Close.
Position of tongue - Front, central or back
Roundness of lips - The roundness of lips add another effect. They are generally rounded for back vowels.
Nasalization ? are the vowels nasalized.

Below is the list of known vowels and their IPA symbols.

Edited from original here : http://en.wikipedia.org/wiki/File:IPA_chart_2005_png.svg

The best way to analyze vowels is to look at their frequency spectrogram and look at the peaks. The first three formant are specifically interesting. The roundness of lips changes the positions of formant.
Again there are further diphthongs and glides that are combination of two vowels.

Consonants

The consonants are interesting because they are numerous, show great variation in how they are produced and the signal is available for only the short time. They are "negative" because the voicing and vowel are interrupted or blocked by the position of tongue. Here I am going to use somewhat non-standard terminology and classification only because that is how I understand it. Also because i was introduced to the subject via Sanskrit Grammar.
There are three main things to look for - (A) Properties of original sound that is obstructed (B) manner in which the air flow is obstructed/modified
(C) place of obstruction/modification

Properties of original sound

Voiced vs Unvoiced - whether voicing continues or not . [b -p]. [k -g][t-d] are some examples . (saghosh and aghosh.सघोष- अघोष )
Aspirated vs Non aspirated - this difference is important in Indic langauges it effectively doubles the consonants available for use in languages. (alpa prana- maha prana अल्पप्राण- महाप्राण)

Manner in which flow is obstructed /Modified

Stops - The airflow completely stops
Friction - Sound produced by friction is introduced in the mix.
Affricates - these are combination of stop, followed by the friction at the same place.
Liquids - sibilant and approximants - where air flow is partially blocked
Nasals - the airflow goes through the nasal channel

Place of articulation

Labial

Bilabial
Labio-dental

Coronal

Dental
Alveolar

Palatal

Alveo-palatal
Retroflex
Palatal

Dorsal

Velar
Uvular

Radial

Pharyngeal /Epiglotal
Glotal

Edited from original here : http://en.wikipedia.org/wiki/File:IPA_chart_2005_png.svg

Syntax: Colorless green ideas sleep furiously

2016-05-10T23:00:00.002-07:00

In 1957, the father of modern linguistics Naom Chomsky came up with a sentence "colorless green ideas sleep furiously" as an example of sentence that is syntactically correct but semantically non-sense. He founded a branch of grammar referred as "Generative Grammar" based on the idea of production rules. Here I talk about the basics, X-Bar theory and generalized phrase structure grammar.

The basics of Context Free Grammar

The context free grammar is specified by a system of production rules. Starting with a set of terminal symbols, non-terminal symbol and a distinct starting symbol each production rule specifies how to generate a valid sentence in a given grammar.

Given a sentence identifying the sequence of rules that generate that statement is called Parsing. The raw text is first "tokenized" using lexer and syntax tree is generated during parsing.

The grammar is generally specified in a form similar to Backus Naur form
There are two ways to parse top-down or bottom-up.
The LL parsers look ahead k symbols and deterministically chose next production rule to apply. (Often a simple recursive decent parser can be written "by hand" making generous use of switch statements)
LALR parsers on the other hand use a "shift/reduce" parsing where a state transition table is used to decide whether to "shift" current token on to the stack or to "reduce" the stack by applying a grammar rule. This often requires getting help of parser generators like yaac.

The "Language Instinct" and X-Bar Theory

As linguists started applying formal grammar theory to the natural languages they realized there is an underlying common structure to all languages.

The sentence is made up of phrases
The sentence always has verb.
The order of Subject(S) Object(O) and Verb(V) is fixed for a given language. Eg. English is SVO, Indic languages are SOV , while semantic languages tend to be VSO.
The order of adjectives (A) , Nouns(N) and Specifiers (Sp) is fixed
This ordering is similar to way individual phrases themselves are structured internally.

X-Bar theory

The theory is formally called "X-bar" which posits that each phrase is made up of a binary tree. Each phrase must have a district element called "head" and the phrase structure is specified by following rules. The structure applies to Noun Phrase, Verb Phrase and Preposition Phrase. (Even the sentence itself!)

Phrase ::= Spec X''
X'' ::= X' Adjunct*
X' ::= X Complement*
X ::= Head

By changing the order for symbols in each rule we get rules for your favorite language. Eg In English and Indic languages the adjective is before noun , where as in Spanish (and other Romance languages) it comes after noun.

the blue sky
el cielo azul

Language Instinct

Even the languages spontaneously generated by kids show the same "inherent structure" leading to the hypothesis that "parsing ability" is a part of cognitive circuit that every human is born with. Cognitive Psychologist Steven Pinker explains this very well in his book "Language Instinct".

Essentially for each language we learn the parameters that fix the order of symbols in X-Bar theory

Generalized Phrase Structure Grammar

In BNF form of grammar the production rules are given in the following manner

A ::= B C D

Where A is a parent and it can have three child nodes in that order.
However the generalized phrase structure grammar parsing strategy will separates immediate dominance and linear precedence.

Instead of specifying a single production rule, it is broken down into three separate parts

Immediate Dominance : In simple terms it says A is the parent of B, C and D . It does not specify in which order B, C, D should occur.

Eg Rule A--> B, C, D specifies that A can have three children

Linear Precedence : Specifies order in which children are. Orders can be partially specified

Eg Rule B C specifies that under A, B must occur before C

Head Identifying Rule: Each such production has exactly one head element and must occur in the production.

Eg. ConditionalBlock ~ IfClause

if {} - is valid
if {} else {} - is valid
else {} - is not because the head is missing.

Example is
QueryExpression --> SelectClause, WhereClause, FromClause.

With the separation of Dominance and Precedence all of following are valid production of the rules.

select * from tbl where col == 10;
from tbl where col ==10 select *;

My JVM dream, now 20 years later..

2016-05-10T22:59:00.003-07:00

Back in 1996, I first encountered Java Virtual Machine while still in collage. And immediately fell in love. But worse - I got obsessed with it. Obsessed with this crazy idea of writing new languages that targeted JVM. 20 Years later that obsession secretly continues ...

Fortran Compiler For Java Virtual Machine

To complete my Computer Engineering degree, we had to submit a group project at the end of the final year. I was able convince my awesome and insanely talented friends to take that as our project.

We chose fortran because lots of literature available on Fortran
We contacted Center for Development of Advance Computing (CDAC), and they indicated interest in porting their scientific simulations in Fortran to our JVM.
Sun JVM team shared their JVM specs with us. (I just realized I actually work for the same company now !!!)

What we delivered

Assembler for JVM
Fortran compiler that outputs in our assembly language
Java based IDE for editing and building fortran code.

The BIG DREAM - JVM as a target for writing new languages

Obviously back in those days as a young collage student, my intention was to conquer the world! But by developing new and interesting higher order languages ...

Paradigm Shift I really wanted was ...LINQ !

The language I really wanted us to implement had native SQL syntax ...here is what my handwritten version of seminar says ...

Where are we now 20 years later?

http://www.infoworld.com/article/2923035/java/java-at-20-jvm-javas-other-big-legacy.html#tk.ifw-infsb

List of JVM languages

Top Languages running on JVM

Scala
Groovy
Jython
JRuby

Lambda and Streams

Java now supports lambda and stream processing

Where to next ?

It looks like world is still warming up to the notion of targeting languages to JVM and getting to know lambdas.

And I feel like my dream is still alive and a driving force for me...

Scarce Data Problem: Mysterious Indus Valley Script

2016-05-10T22:58:00.002-07:00

Once upon a time, nearly 5000 years ago there was an urban Civilization with 1000 planned Cities across the North-Western India. It is called Indus Valley Civilization

The Cities

Most of the cities were along banks of the now dry river and at its peak this Civilization had a population of over five million.

For that era it was very advanced civilization with houses built out of baked bricks and public facilities like baths and huge granaries. One of the cities Harappa had about 700 houses with private wells and most cities had Citadels. The civilization had developed metallurgy.

The Oldest Writing on Indian Subcontinent

One of the most interesting thing about this civilization is that they developed a script and left behind around 4000 seals with around 400 distinct symbols.

The script is still undeciphered and the underlying language has not been identified.

The script is found all over the North-Western India as well as Egypt and Mesopotemia.
Script is continued over hundreds of years with regularity and similarity between seals found across the region and across the centuries
There is no bilingual text available like Rosetta Stone.
Most seals are extremely brief with longest being only 17 character

Original Scarce Data Problem

Does this script represent a spoken language ?
If yes what language ? What can we learn about this language ? How does it related to present day languages of the South Asia
What are these seals trying to tell ? What were they used for ?

Answers to these question can shed light on early history of Indian subcontinent and cultural sphere. But this is not just an old Indian civilization it is the World Heritage for all of humanity.

Call to Action:

How can we use our big data tool set and machine learning to decipher Indus Valley Script ?

[All images from Wikipedia - thank you to all original creators]

Managing Projects: Software By Numbers

2016-05-10T22:57:00.002-07:00

I read a wonderful book in 2004 named Software By Numbers by Mark Denne, Jane Cleland-Huang. It introduced the concept of "Minimum Marketable Feature" and "Incremental Funding Methodology". It radically changed how I viewed project management and continues to inspire me even today.

The main message is - by carefully choosing the way in which software components are assembled, we can create identified units of market value before the application/product is anywhere near completion.

Minimum Marketable Feature (MMF)

Typically an MMF creates the market value in following ways

Competitive differentiation
Revenue generation
Cost Saving
Brand Projection
Enhanced loyalty

As the name suggest the features need to be marketable which means you can use them to decide price for the product, promote them and more importantly create revenue by help selling those products.

Kano Matrix

An incomplete software still has value to the user. However a car that consist of only engine and wheelbase is unlikely to be thought any useful. You need more than basic functionality. Similarly a super cool luxury car that does not move is equally useless. What you need is a balance of "cool" and "required" features. This idea is captured in a model developed by Nariaki Kano.

The model categorizes the features in a few interesting categories

Must-Have or Basic Needs: Lack of must have features causes dis-satisfaction, but once these features are present adding more Must-Have features does not make the product attractive to the customers
Delighter: Lack of these features does not make customer unhappy but it does make your product boring. When added these features create excitement and makes your product attractive.
One dimensional or Performance Needs: The customer satisfaction is directly proportional to 'how much' of the feature you are providing. For cars milage is one such feature - more the better and as it goes down so does customer's dissatisfaction.

Incremental Funding Methodology

The goal of the incremental funding is to accelerate achievement of first the self funding point and then the breakeven time.

Below is the a high level of procedure to do exactly that.

Define Dollar Value of the MMF: Once we have MMFs defined and categorized next task is to assign a dollar value to that feature. This is the incremental revenue generated by adding an MMF to the product. Obviously it is calculated based on additional buyers and price increase. For Must-Have feature the dollar value is defined by possible loss if the feature was absent.
Estimate Cost : Next we estimate the cost of creating and maintaining/servicing this feature.
Identify Risks : We also need to capture the uncertainties associated with the features.
Identify the dependencies between MMFs.
Calculate Rate of Return for each MMF. The rate of return can be calculated using various standard techniques like Net Present Value (NPV) or Internal Rate of Return (IRR)
Sequence: Finally Sequence the delivery of the MMFs to maximize return in by delivering them in minimum amount of time

[Images: for Kano wikipedia and for incremental funding the book]

Look Ma No Locks - Act III - "STRONG" Eventual Consistency with CRTDs and other Geeky Stuff

2016-05-10T22:56:00.002-07:00

In Act-I we saw that Consistency and Serializability were the goals of our Hero Developer was striving for, the plot started with the basic idea of Two Phase Locking and in Act II we encountered the concept of "Tunable Consistency" in the form of isolation levels and then stumbled upon the CAP theorem , both very important developments. In this Act III, the story continues with new and exciting developments in research community - namely CRDTs and Co-ordination Free Consistency...

What is this "Eventual Consistency" business?

If our Micro-Services were dealing with Read-Only-Data then we could scale them infinitely by adding one clone after another- all nodes will have same data and every result would always be consistent. But alas - the world changes and so must our data - on each individual node responsible for that piece of data. The problem is that the change has to "Start" somewhere and then must spread to all other nodes in the cluster and eventually somehow we must detect that change propagation is "Finished". Network is unreliable and THAT exactly is the curse of being a distributed system, my friends. There is that brief amount of time when the change has been "Started" but not yet "Finished" completely. How do you deal with the next change request already in the queue ?

Now, you can be pessimistic and wait for the first change to Finish Completely before next one Starts. OR - you can be optimistic and assume the Best Case and proceed to adapt the next change before first one Finishes and only deal with any issues when they arise. The intuition here is that the series of changes may be re-ordered or delayed but "Eventually" every one sees the all changes and "deals with it" in case when problems arise. (It is as if my otherwise consistently normal friends behave a little strange when in Las Vegas, but they are eventually back to normal when we are back in Seattle...)

In short here is the reality

By the time you detect the consistency problem, the client requesting the change may be long gone already and you are left alone with inconsistencies to resolve.
Eventual consistency is a meaningless term until you define what it means to "reconcile" the differences/inconsistency. Eg. What happens after you detect that two customers have added the same last remaining item to the cart or have booked the same last seat on the plane? What is your MERGE strategy ?
In eventual consistency you decide to pay very little price upfront for the consistency but your are signing up to pay heavy price later to reconcile and correct the in-consistency when it arises. The math works as long as the cost of "Fixing" is amortized over mostly problem free executions.
It is an absolute requirement that ultimately all nodes resolve the inconsistency the same way. I repeat - It is an absolute requirement that ultimately all nodes resolve the inconsistency the same way. It is turtles all the way down - How do all nodes come to know what was the resolution decision and how do you propagate that decision consistently? Fun times ...

I'm already thinking of writing a next best seller novel based on the effects of eventual consistency and meaning of destiny - Is it cute Ms. Isabella who gets the last seat or it is really her destiny to miss the flight and meet Mr. Right on the next flight ?? ...

Commutativity : 2 + 3 == 5 == 3 + 2

What if there was no additional costs to pay when inconsistency was detected in eventually consistent system?
What if no coordination was required to resolve inconsistency in a distributed system?
What if every node already knew how to resolve the inconsistency in a prescribed deterministic ways?
What if there were no bad effects of message re-ordering to begin with ?

Suppose our Hero Developer wins three lotteries in a row in three days . Now, it doesn't matter in what order he gets paid from each lottery. As long as he gets the money in reasonable time - it's all good. The commutative nature of natural numbers "adds up" to a solid logic based reasoning that eventually our Hero Developer will be rich by the amount that equals to sum of all three lottery prizes !

In 2007 , Marc Shapiro and others at INRIA, formalized this notion in what is called as "Conflict Free Replicated Data Types" .

This system works in following conditions ...

If the system is monotonically increasing , then it never has to "roll-back"
And if state transitions are partially ordered and MERGE operations are associative, commutative and idempotent
THEN the replicas that have received and applied the same set of updates must immediately have equivalent state. There is no conflict arbitration process, because conflicts do not exist in strongly-consistent systems.

In short, if only operation we allow is INCR(account, amount) then is monotonically increasing and addition being commutative, associative as long as the operations have "at least once" and "at most once" guarantees (i.e. idempotent) , the system is STRONGLY consistent and co-ordination free !!!

Mr. Luca Pacioli and Double Entry Accounting

The Father of profession of Accounting, Luca Pacioli was a Italian mathematician who invented what is now known as double entry accounting system. This system revolutionized the world of commerce. This system is fundamental to modern civilization as is Newton's Mechanics or theory of Social Contracts. In his system there is a column for Debit and another column for Credit. The total balance is result of subtraction of one column from the other

How is that relevant ?

Both debit and credit are monotonically increasing and follows the rules of addition in short can be implemented as CRDTs. And natural number can be represented as a sum of a positive and negative number

What other data structures can be implemented as CRDTs

Sets
Maps
Graphs

Shipping Pie vs Shipping Pie Recipe

The theory of CRDT makes a great deal of distinction between shipping the end results and shipping the instructions to achieve the results. While shipping End Result is cumbersome. It is theoretically easy to deal with and easy to prove properties of the system. While shipping recipe is easy it is not as accessible to theoretical treatment. The genius of team who developed CRDTs at INRIA is to show the equivalence of both the approaches.

The story continues next week ....

Look Ma, No Locks - Act II - Tunable Consistency

2016-05-10T22:55:00.002-07:00

The last post described why our industry started using locks excessively in database system to achieve Serializable transactions. The conflict and tension between Availability and Consistency became more serious as days passed by...

This post first talks about how the concept of database Isolation Levels is actually an early attempt to define Tunable Consistency and then describes the essence of now famous CAP theorem.

Next post will lay out necessary foundations to understand current research in this area including commutatively and example STRONG eventual consistency model called Conflict-free Replicated Data Types.

Locks everywhere in all shapes and sizes.

To increase the performance we had to start using different types of locks for different types of things and operations. There were obviously separate reader and writer locks. There are page level locks and then there are row level locks. Sometimes we use transaction level locks, but most times the locks are statement level locks. In short there were locks everywhere in all sizes and shapes. But our insatiable thirst for throughput meant that we were ready to let go of some consistency guarantees. Stage for Availability vs Consistency battle was set.

Are these Database Isolation Levels or Tunable Consistency Levels in disguise?

To increase throughput (aka availability) we started dropping the locks starting with range lock, then read locks and even write locks. But that obviously started showing up undesirable side effects. Recall that any transaction is in final analysis a sequence of reads and writes and that all reads and writes to the same data items can potentially cause inconsistent state as a result of random scheduling.

Later these bad effects were categorized as follows

P0 - Dirty Read – Transaction could read uncommitted data written by another transaction. In short your reads are dirty.
P1- Non-Repeatable Reads – If transaction read same data item twice then value may be different between two reads. You reads are not reliably repeatable
P2- Phantom reads – This happens when a query with a where clause is executed twice and between those two calls new data gets added or deleted that satisfies the query- the result is phantom reads. Some other names for this are motion blur, fuzzy read
In addition there are many other phenomenon viz. Lost Update, Cursor Lost Update, Read Skew, Write Skew etc etc.

In short, there is no free availability without reduced consistency

Based these bad side effects, the ANSI standard defines following four isolation levels. In reality these are rather Consistency Levels and you can choose the reduced consistency for better performance

Read Uncommitted – This is lowest level of consistency guarantee. Dirty reads are possible, so are Non-Repeatable and Phantom reads
Read committed – In this next higher consistency level, only the committed data is read. Although dirty reads are prevented other anomalies are still possible
Repeatable Reads – At this consistency level single item reads are repeatable but phantom reads are still possible
Serializable – This is the highest consistency guarantee. It is not possible to have dirty reads, phantom reads or non-repeatable reads
Snapshot – this is yet another consistency level where your transactions can see only the snapshot of the data as it existed before your transaction began.

Distributed Transactions – the basics

As computer systems were connected to each other on a distributed network, our industry started exploring Master-Backup architecture. However there is always some delay between when transactions are committed at Master and when Backup is updated - leaving possibility for In-Consistency
Alternatively you could have synchronous updates - The protocols like two phase commit and three-phase commit were introduced just for handling this sort of stuff. In essence a transaction is not committed until all machines participating in the distributed atomic transactions first commit their share of the transaction. The obvious side effect is that while Consistency is increased the Availability is decreased because of all this co-ordination effort …

Enter the CAP theorem

The CAP theorem says that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:

Consistency (all nodes see the same data at the same time)
Availability (a guarantee that every request receives a response about whether it succeeded or failed)
Partition tolerance (the system continues to operate despite arbitrary partitioning due to network failures)

The theorem is easy to understand and equally easy to misapply. Many have interpreted this as a binary choice between Consistency and Availability (because partitions are always ever present).

However what the theorem REALLY demands of you is following :

better partition detection ,
better partition management
And more importantly mitigation and recovery when partition recovers.

More on this next time ...

References:

A Critique of ANSI SQL Isolation Levels http://research.microsoft.com/pubs/69541/tr-95-51.pdf
CAP Twelve Years Later: How the "Rules" Have Changed http://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed

Look Ma, No Locks - Act I

2016-05-10T22:54:00.004-07:00

I have seen too many people signing up for "SQL vs NoSQL war" without understanding what exactly they are fighting for and more importantly - for whom and for what reasons.

This is a first act of the drama that is "SQL vs NoSQL war"...enjoy.

Opening sequence: Writes, they always conflict

Ever since John von Neumann started reading and writing to memory addresses he left a problem for future generations to solve. If you read a variable twice (or two different variables) then value obtained during those reads depends upon whether someone else wrote and changed the value of variable(s) behind your back between those calls!

The problem is pervasive - from processor registers and caches ..to memory and disks, ...from single processors to distributed systems.

The problem becomes even more severe when transactions are involved.

Say you have just two statements with primitive operations of add, multiply and assign , and initial values of variables are as follows ; x=1 and y =2

z = add(x, y)
y = multiply( 10 * x)

What is the value of z if you could possibly simulate all combinations of read and writes for 3 variables x, y, and z happening one after another?

If 1 is executed before 2 then z == 3.
In other case it is 12 !

Which one is it - REALLY?

Now what if there are two transactions with 8 steps each ? what about 679 steps each ? I get dizzy just thinking about this - I hope you see the problem here ...

This is NOT a theoretical problem, with pipelining architectures the operations are indeed executed in any random order every time you run. With reordering of messages in a distributed system this is a real problem.

What happens if we "double click" and we break statements above down to smallest possible unit of execution? may be a single processor instructions or even a micro-instructions ?!

Real geeks know it already : It is all about History

The real geeks represent this sort of thing as a directed graph where an operation that depends on other operations is connected by a directed edge in a graph.
Real geeks truely understand that there are many ways to traverse nodes in such a connected graph.
Real geeks also know that there are many permutations and combinations to visit the nodes in this graph and each path or History is just one way things could happen.
There are many alternative Histories of your travel through the graph - you just happen to take one path and know one History.

The Seer : Transactions - Do or Don't, Don't try

One of the greatest invention was the idea of transactions. You read number of items and write number of items - but here is the rule everyone follows - ALL the variables change at once or NONE of them change at all !

Seers invented this great idea of ATOMIC operations - batch your operations in transactions and at the end - either COMMIT or ABORT but never leave your application in a ZOMBIE state.

Are all the problems solved ?

NO!!! Mr. Problem shows up again. Effect of series of transactions still depends on which transaction ran first !!

First Breakthrough : Serializable transactions - what if we decide order should not matter at all - just like that ?

What if you did not allow transactions to complete at all if they are NOT serializable , meaning that the side effect did not depend on the order in which transactions were executed ? Here is a simple rule that solves the problem - If order between transactions did not matter then and only then allow them to proceed or else fail them right away

No mercy - you need to be Serializable! Anyway, what is the difference between an explicit ABORT and implicit ABORT (when transaction does not even meet our requirements of serializability) ?

Here is our requirement - Given transactions T1 and T2, the effects are same if T1 in its entirety was executed before T2 or vice versa.
A stronger requirement is - ANY interleaving of operation in transaction T1 and T2 produce the SAME effect.

First Problem : But How do you even know when set of transactions is serializable ?

The Seers know the answers - as always

A History of transactions is Serializable if and only if its operation dependency graph does not include any cycles.

The Journey begins:

The serializability theorem looks like a very promising destination to go to. It feels like worthy purpose to live for a database system ...

The Question is - How do you get there ?

First Wrong Turn: Two phase locking

In the old days when there was simple one core computer the answer was obvious ...use two phase locking.

The algorithm is pretty simple

In phase ONE try to acquire all the locks you will ever need (or else abort if you can't)
Do you stuff (censored version)
In phase TWO release all the locks you acquired in step 1

The Shortest theorem ever !!

If there are cycles in the "History Graph" then phase ONE will fail for one of the transactions and it is not member of Serializable Transaction Set..
That is it - that is the theorem - in a Directed Acyclic Graph you can't visit the same node twice ... no two transactions can acquire the same lock !!

Deadlocks : Oh my god !!!

....

the story continues in next week's episode ....

Einstein and Time Travel in Distributed Systems

2016-05-10T22:53:00.001-07:00

Exactly 100 years ago this month in Nov 1915 Einstein published his Field Equations and forever changed the physics and our understanding of space and time. His ideas are still relevant in the field of Distributed Systems. This is my tribute to Einstein by showing how his fundamental principles directly apply to distributed system design.

Accept the reality and work backwards to fix your theories

In last century Einstein changed the physics and turned it upside down several times again and again by simply accepting the reality as it is and working backwards to fix the physics to deal with it.

First Einstein used the reality of constant speed of light to derive special relativity and famous E=mc2.
Then he used the simple everyday fact about equivalence of inertial mass and gravitational mass to derive General relativity. Theories about unimaginable stuff like blackholes and Big Bang followed.
He accepted the fundamental reality of quantum nature of interactions between light and matter and led the foundation of quantum mechanics by explaining photo electric effect. By accepting the simple fact that two photons are indistinguishable from each other he derived the Bose-Einstein statistics that is the basis of how Lasers work and at the root of everything IT - from VLSI to printers to optic fibers to Compact Disks.

Photon the Messenger of Force

The greatest achievement of last century is Quantum Field Theory , the most successful of which is Quantum Electro-Dynamics (QED).

The theory posits that all interactions between matter particles are mediated through force particles. In short one matter particle sends a message to other particle in the form of a photon. After receiving this event/message the second matter particle changes its internal state. The Quantum Field Theory reduced all physical laws to this basic interaction scheme. A Fermion (a matter particle) keeps on doing what it is doing i.e remains in the same state until it either sends a message or receives a message - a Boson (force particle).

In short the nature at it's most fundamental level works on this Message Passing paradigm

No Global Clock and Only Local Effects

When you look at the night sky there are billions of shiny stars. You can see a star only because a photon from that star started perhaps billions of years ago and hitting your eye right now getting converted to chemical-electrical signal. Have you ever wondered that the moonlight you see now might have actually started ~8 minutes ago at the surface of the sun and reached you only after reflecting at the surface of the moon? Suppose you see a shooting star and two minutes later see a super-nova. What event do you think really happened before and which one after? It really depends on frame of reference - your local frame of reference.

In a distributed systems messages get reordered and messages get delayed . How do you know which event happened before another event. This is super important because without ordering the events any attempt of maintaining consistency is impossible.

But not all hope is NOT lost because we still know two things

that star became unstable before it went super nova
that light from shooting star was emitted before you received it.

Formally this relation is captured in a Strict Partial Order < such that

If event A happened on the same process before event B then A < B
If event A is sending of message M and B is the receiving of that message then A < B
Transitive : If A < B and B <C then A < C
Irreflexive : The event can not be before itself !
Necessity : If A < B is true then B < A must be false.

Black holes and Gravitational Lensing

In Distributed Systems the messages often get lost or sometimes a node just fall into the blackhole. We know the presence of the node and its state only by receiving a messages from it.

But equally importantly because of gravitational bending of light we might have multiple images of the star. A parallel in distributed systems is when you get multiple duplicated messages from the same event and need to deal with it

In conclusion,

Einstein based all his theory on this fundamental principle of causality and his genius is converting theory of local effects into a theory that can describe the entire universe and the birth of Space and Time .

Below is the image of photograph that proved the light-bending effects of suns gravitation that turned Einstein's general theory of Relativity into Law of Nature.

Thank you very much Albert Einstein.

Note : all images from wikipedia - many thanks to the original creators of those images.

Benevolent Dictator vs. Part-time Parliament

2016-05-10T22:51:00.002-07:00

Distributed systems require Leader Election and today I am going to try to explain two most popular algorithms - PAXOS and RAFT.

Once the problem is defined and some basic building blocks are identified both the algorithms are very easy to understand. The Paxos protocol was first published in 1989 by Leslie Lamport as the basis of State Machine Replication method. Raft was designed in last couple years from "ground up" specifically for easy understandability.

Background : Need For Consensus

Army of clones

In a typical scale out architecture we have a number of clients making requests to a cluster of servers.

When these servers are identical and stateless any server can process any request from any client. That is the basis for "scale-out" architectures. When servers are stateful the same logic still applies as long as each server has the same state.
When the client request change the state, that is when we need consistency and atomicity with many concurrent clients talking to many servers. This is where you need to co-ordinate using consensus protocols

Electing a leader and following commands

One very powerful approach is to elect a single leader who makes the changes to the state and then all other machines follow exact steps leader followed to make state change.
This change of state is defined by a deterministic state machine.(Mealy State Machine to be exact). Same sequence of input command executed on each nodes creates the identical state changes at each node. Leader broadcasts the input messages to this state machine and followers make local state changes. This is what Leslie Lamport means when he says "State Machine Replication".

Crashes and Dropped Messages

Life would have been awesome if there were no crashes and no lost messages and no network partitions. But failures do happen and that's exactly the reason why we need complicated protocols.
The basic assumption of distributed system is that there is no global shared state and the state has to be transferred by passing messages. Messages have delays and so the state changes have delays.
Every node in the cluster will be slightly different due to delays between when commands were sent by the leader and when they were received and applied by each follower.

The basic requirement for Leader Election

The basic requirement of consensus is that despite crashes and network partitioning there is exactly one elected leader and every one knows about it when elected.

Toolbox: The Building Blocks

Let's first start with examining some familiar concepts and tools before we analyze PAXOS and RAFT. In both algorithms any node can propose but only one is finally accepted as leader. "Proposer" proposes and "Voters" vote on it. In both algorithms once the leader is elected the results are broadcast.

Optimistic Concurrency and Thomas Write Rule :

The optimistic concurrency works by requiring every write to follow a two step process - first fetch the latest version of data and then update it.
This is just Compare and Swap in different form. If your update is based on outdated version then it will be rejected. Thomas' write rule says ignore outdated writes.
This is "lock-free" and gives very high throughput.

Two phase commit

The classical commit protocol has two phases - a prepare phase and a commit phase . In prepare phase we solicit votes and leader is elected only when commit is issued and successful.

Why we need majority ?

It is possible that two nodes simultaneously believe that they are the leaders.
But by definition and mathematical certainty only 1 can get the majority votes. Therefore there can be only one leader - thus satisfying basic requirement.

Bidding and Auctions

Think of leader election as as an auction - the highest bidder always wins. Proposals from higher bidder cancels voter's previous commitments - the transaction is aborted for previous bidder/proposal.
There is always some well defined way of saying which Candidate has higher bid.
This bidding and auctioning process is integral part of the leader election.

Paxos

Below are the high level details of the algorithm. Here is how it works

At a higher level Paxos combines "read value" part of optimistic concurrency with propose phase of two phase commit in first step. In second step it combines "write value" part with commit phase.
In step 1, the proposer "makes up" a integer version number/timestamp and calls it "proposal number". In the spirit of Thomas's rule no voter accepts any "outdated version" by making sure it always accepts the highest proposal number. This pretty much looks like an auction - the highest bidder always wins.
If proposal gets ACK from the majority of the nodes then proposer send the "commit message". The only confusing aspect of the algorithm is that if the value is already chosen then proposer just sets the same already chosen value instead of its own. (It sure does feel like an uneccesary no-op though)
Again using Thomas' rule voters reject the request to commit if they have seen a higher numbered proposal. Proposal to write higher version cancels voter's previous commitments - as far voter is concerned the commit is aborted for the proposer.
When proposal gets majority of committed ACKs, the election is over.
Leslie Lamport compared this method to a fictional legislative consensus system used on the Paxos island in Greece. That is your "Part Time Parliament". Leslie envisioned that for each new state change a new leader is elected and everyone follows it only for that single change. For next state change request the process repeats.

RAFT

RAFT instead elects a dictator for fixed term. Once elected, everyone follows the leader until a new leader is elected.
For each state change, the leader first sends a Prepare message on behalf of the client. When it receives majority of ACK on prepares it sends commit message. Commit is complete when majority have committed. The cycle continues for the next change..
New election is started when the term for current leader ends or any node thinks leader is dead. A node thinks a leader is dead if it has not received any heartbeat or command from the leader in given timespan.
The node suspecting a leader death then decides to become a candidate. Candidates seek a majority vote. If the Candidate doesn't get elected in the first round then it just keeps on trying again and again until someone is elected. As simple as that, keep on asking for vote until either you win or know that someone else is already a winner.
If node itself is not a candidate then it always accept the candidate which has advanced most in its processing. Again this is kind of an auction. In other words the bid from the candidate with the most consistent state always wins.
But how does RAFT avoid or minimize the chance of election getting into the infinite loop where no one ever has the majority ? The answer is annoyingly simple - The node waits for a random amount of time before becoming a candidate and asking for a vote. It is statistically improbable that there will be two candidates asking for the vote at the same time. By carefully choosing the random wait time progress can be made - this is exactly how ethernets work !

Conclusion

Leader election is fact of life in distributed systems. Although Paxos and Raft look very different at the surface , deep down they use the similar building blocks.

References:

Paxos Made Simple
http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf
In Search of an Understandable Consensus Algorithm

http://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14

Resilient Distributed Datasets and origins of my obsession

2016-05-10T22:49:00.003-07:00

Yes- it is true. I am obsessed with in memory data processing and it goes waaayyy back. Back in my college days I had a very simple but very powerful insight or vision. I feel super lucky because over the years every now and then I just happen to stumble upon more and more opportunities to make it real...I'll talk about LINQ, Project Orleans and then finally RDDs.

In the beginning

The obsession started some 17-18 years back when I was writing a paper for my college seminar. Being a compiler freak, my idea was to write a language that manipulated in memory collections using sql like syntax. What remains today of that dream is a couple dozen hand written versions of that paper and reams of BNF grammars for that dream language. Here are couple of examples ...

And here is another example ...(didn't I tell that this obsession goes way back)

While( !done) iterate;

One idea that I kept on toying with (rather ad infinitum) was that of representing a sql query as a enumeration. (See example of one such idea.) I didn't actually get it working in the college. I almost forgot about it.

Later on while at Microsoft, my passion was rekindled . Off the normal day job hours, I tried to meddle with some research projects like COmega and Common compiler Infrastructure. Unfortunately I was not able to make any real contributions. I moved on and joined Amazon.com...a number of years passed.

Laziness Pays Off

Later in 2008 Microsoft released LINQ and then eventually java followed it by lambdas and streams. It felt like my dream was realized by someone else already. I needed a a new obsession and so I was free to forget about the whole idea. Except - the Lazy Evaluation was destined to turn my world upside down again.

Back to the Future<> in 2011 : Project Orleans at Microsoft Research

I was lucky enough to get a contract position in Microsoft's eXtreme Computing Group in Microsoft Research. More specifically in Cloud Computing Futures team. The project was using Asynchronous Message Passing to implement an Actor Model based compute engine. Think of these actors as objects distributed in a cluster using some sort of Consistent Hashing Ring. Almost like a memcache for actively callable objects. Admittedly this project was the coolest project I have ever worked on and worked with some of the brightest engineers I have ever met. ( I helped with implementing state management and code generation.) With the help of "mostly in memory" processing we were able to achieve amazing throughput for live Halo 4 services.

Enter Apache Spark and Resilient Distributed Datatypes

After a trip down a memory lane we arrive at Today's state of the art - Resilient Distributed Datasets (RDDs), a distributed memory abstraction that lets programmers perform in-memory computations on large clusters in a fault-tolerant manner. From the RDD paper ...

.... RDDs provide an interface based on coarse-grained transformations (e.g., map, filter and join) that apply the same operation to many data items. If a parti-tion of an RDD is lost, the RDD has enough information about how it was derived from other RDDs to recompute just that partition. Thus, lost data can be recovered, often quite quickly, without requiring costly replication.

References :

Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing https://www.cs.berkeley.edu/~matei/papers/2012/nsdi_spark.pdf
Orleans: Distributed Virtual Actors for Programmability and Scalability http://research.microsoft.com/pubs/210931/Orleans-MSR-TR-2014-41.pdf
http://research.microsoft.com/en-US/people/philbe/disckeyotephilbefinal.pdf
http://dotnet.github.io/orleans/Introduction

Microservices: Managing for Frequent Reads and Rare Writes

2016-05-10T22:48:00.000-07:00

It is a rare service that does not need to persist its state.

Choice of your design critically depends on how frequently data gets written and allowable delay between when data gets written and the time when readers (and other nodes in the cluster) see that update. Let us examine a class of services where there are very infrequent rare writes and massive numbers of reads. This type is the most common kind of service in my experience. Here I outline a common way to design such Microservice. I have used this simple "design recipe" for many services and it has worked for me every time over the last decade.

Step 1 : Treat it as a Read Only Service

The first step towards designing a service is to assume it to be Read Only and optimize it for fast access and scalability. When data is readonly you can make million copies of your service and you don't need any coordination. They all return the same results for same input.

An example would be a service that returns Maximum or Minimum recorded temperature for a given the Zip Code. Input for this service is historical data. We assume it is somehow injected in the system already. Temperature gets recorded daily and so it is okay to update the result set on daily basis. Until we get new updates the service just serves readonly data. Another example would be Catalog Search on football memorabilia/ collectible site which will have some structured data in product catalog. It is highly unlikely that new products are added every hour and product details are upadated every second.

Precompute results: The first optimization obviously is to pre-compute results.Eg. min/max results for given zip codes are calculated offline in a batch (or hadoop) job. The resulting data is then loaded into some persistent database. Your service is then just the look up of this pre-computed data for given type. Performance is increased many folds. You can increase the performance even further by trading space for speed by denormalizing the results. How often you calculate the result set data is domain specific. It can range from minutes to daily to even weekly. Most domains tolerate delays extremely well and do not require true "as of now" results. Now where do you store the output of a batch job? I prefer using distributed high availability key-value stores for storing such "denormalized" and pre-computed results. The resulting service code is then mostly looking up data in key-value stores (and do some parameter validation and minor post processing)
Cache results: But we are still hitting the datastore for every request. Networks are fast these days but not fast enough. Next optimization is to use distributed caching to decrease latency. The result data is treated readonly anyway.
Cache results locally in memory: We can increase the performance even further by using multiple levels of cache by first storing some of the data locally in server memory.

The "hot data" lives mostly in memory, the "warm data" is a RPC call away in distributed cache and "cold data" is always reliably stored in distributed key value store and summoned at any time. It is very easy to scale your service up or down by adding more caching or service instances.

Now is the time to start thinking about those Writes.

Step 2: Handle Writes

The writes are rare but DO change the state of the system. We must handle concurrency and consistency properly.

Separation of Concerns

There is a common pattern called Command Query Responsibility Segregation (CQRS). Essentially you have two separate interfaces: one for update and the other for read. We designed our read interface earlier.

The Write interface is generally your plain vanilla 3-tier web service backed by a very high performance Relational Database. The data in your database is the ultimate source of truth about your service. I prefer this database to be strongly consistent i.e. ACID. The read interface never ever read from this database. They read from the key-value persistent store. A batch job periodically reads the data from the master database and transforms it into key-values and stores in No-SQL store. We have already discussed how to handle this readonly key-value data effectively. Note that the eventual consistency comes from the delay between when data is added to master database and when it shows up in key-value stores. There are age old multi-phased state of the art protocols to handle failures and backups and fail-overs in case of master read/write RDBMS. It is very much appropriate to use standard database technology given low write traffic. Again recall that this database does not contain the data about the entire universe but only the slice of reality that is relevant to out micro service. Usually the data size is not a problem these days.

Optimistic Concurrency

Although write traffic is low it still needs locking and properly scoping your transactions and using correct isolation levels. Use of optimistic concurrency and locking can increase performance of your database without sacrificing the consistency.

Use Event Sourcing

Event sourcing is a technique where we record and preserve each every change made to the system. This is yet another way to increase throughput and resiliency of the system.

Use Complex Event Processing

So far we are relying on batch model . But this is not hard and fast requirement. You can build complex pipelines on top of event stream using likes of Reactive X , Spark Streaming , Apache Storm

Step 3 : Get Closer to Data

Use Ephemeral Local Store: One disadvantage of caching is that memory is limited and you still need to fetch data from remote machine (be it memcache or your no-sql store). Yet another optimization is to copy data to each mid-tier machine. There are probably a dozen different ways to achieve this each with its own pros and cons. But the important point is that - the data access is then becomes just a local access and much faster than accessing remote machines.

Use Actors: You can also use actor based run-times to add fault tolerance and optimize write performance. Akka is one such example.

Conclusion:

Many domains tolerate delay in data being updated and that update being visible to everyone. Many micro services have very high read traffic but rare write traffic. There is a simple and effective "design recipe" to build them that works wonderfully in practice.

Happy Coding !

References :

Data Concurrency and Consistency in Oracle Databases http://docs.oracle.com/cd/B28359_01/server.111/b28318/consist.htm
Oracle High Availability Database http://www.oracle.com/us/products/database/high-availability/overview/index.html
Oracle No-sql database http://www.oracle.com/us/products/database/nosql/overview/index.html
Memcached http://memcached.org
Leveraging Massively Parallel Processing in an Oracle Environment for Big Data Analytics
http://www.oracle.com/technetwork/database/bi-datawarehousing/twp-hadoop-oracle-194542.pdf
Why use event sourcing ?http://codebetter.com/gregyoung/2010/02/20/why-use-event-sourcing/
Actor Models https://en.wikipedia.org/wiki/Actor_model

Microservices: Settling Architecture vs Design Debate

2016-05-10T22:46:00.002-07:00

It is an old religious war in software industry. Where does Software Design end and Software Architecture start ? My answer to that question is - boundary that separates a microservice from the things outside of it from the stuff inside it. Inside a micro service we need Design, outside of micro service we need Architecture.

What is Software Architecture?

The wikipedia definition captures the essence of what Software Architecture is. I take liberty to re-iterpret it a little bit.

Software Architecture is the set of structures needed to reason about the software system. Each structure comprises software elements (aka Micro-service), relations among them, and properties of both elements and relations.

Software architecture choices include specific structural options from possibilities in the design of software. Software architecture is about making fundamental structural choices which are costly to change once implemented.

Martin Fowler defines the architecture in an interesting way. "The important stuff—whatever that is".

ISO/IEC/IEEE 42010 defines it as "fundamental concepts or properties of a system in its environment embodied in its elements, relationships, and in the principles of its design and evolution"

Architecture vs Design

Architecture is defining the interactions and contracts of a micro service with the rest of the system. Design is making implementation choices (like internal OO Design, data structures and algorithms.) Your Architecture involves figuring out what micro services you need. Defining data they communicate and store. Details of database design, choice of MVC framework is Design.
Architecture is strategic , Design is tactical. Making trade-offs around consistency and availability is Architecture. Making space/time tradeoffs or deciding to precompute partial results or choosing a caching mechanism is then all part of the Design.
Design is concerned with local issues, Architecture is concerned with global issues. We can change our Design without asking anyone else. (Eg. Change data structure, algorithm or refactor OO Model). To change Architecture we need to communicate it to others and the change has ripple effect.
Design is executable. Architecture is not.

Discovering and Defining Microservices

There are two steps to discovering the Microservices

1. User Story Mapping

Input : Our starting point is scenario or epic. A user has a concrete need in mind and a task to accomplish. User does that by interacting with our system through series of actions. Input to our architectural discovery process is long list of user stories.

Activity: We group related stories into the clusters. These clusters indicate the underlying feature or "capability" that the system must provide.

Output: Each feature or capability is potentially a micro-service. (Prune the list as required.)

2. Component-Responsibility-Collaboration Cards

Input : List of microservices, list of user stories.

Activity:

For each micro service create a card with two sections Responsibility and Collaboration.
Responsibility section includes (a) What do I know ? (b) What do I do? (c) What do I decide ?
In Collaboration section include (a) Who do I interact with? (b) What data I exchange with others?
For each major user story walk through the micro services and in the process assigning responsibilities to them and discovering collaborations and details of those interactions.

Output: Well defined set of micro-services with clear responsibilities and identified interaction with collaborators.

References:

The New User Story Backlog is a Map http://jpattonassociates.com/the-new-backlog/
Creating an Agile Road Map Using Story Mapping https://www.scrumalliance.org/community/articles/2013/august/creating-an-agile-roadmap-using-story-mapping

Microservices: Lego Blocks in Modern Architecture

2016-05-10T22:45:00.002-07:00

Until recently there was no real word to describe the kind of software that I developed over the last decade. I have worked on distributed systems that were massively scalable with millions of users and billions of transactions. I have worked on service oriented architectures that delivered user functionality at rapid pace. I discovered, learned and practiced a particular style of software architecture. But until recently could not find a simple phrase to describe it.

Now I can say I developed Microservices ! But what is Microservice ?

Defining Microservice

Wikipedia defines : Microservices is a software architectural style in which complex applications are composed of small, independent processes communicating with each other using language agnostic API. These services are small, highly decoupled and focus on doing a small task, facilitating a modular approach to system-building.

In short, for each service "Do one thing and do it well".

But I like following definition better

Microservice Architecture is a service-oriented architecture composed of loosely coupled elements that have bounded contexts.

Loosely Coupled

Loosely coupled means each microservice is a unit of software that is independently replaceable and upgradeable and deployable. It is not microservice architecture If all services have to be deployed at once or they talk to the same database and requires coordinating schema changes. Micro services can be scaled independent of each other (ideally in elastic automated ways.). This allows separate development teams (perhaps geographically separated) to develop services using separate schedules, frameworks and methodologies.

Bounded Context

Bounded context as name suggests is a partition or silo of domain model that is mostly selfcontained – Microservices and its peers interact purely through APIs and don’t share data or schema. The key is that each organizes and manages its own data. This is a critical feature of this architecture.

Organized around business capabilities

Now essence of Microservice is that each Microservice is they expose business functionality as a component. And then you can build your application as as suit of services by putting these components together.

Using Language Agnostic API

With language agnostic APIs, it enforces clear separation between interface of the Microservice and its implementation. This ensures true interoperability between various components. SOAP and REST are two approaches that have already become industry standard.

Marriage made in Heaven: Containers as Deployment Units.

Containers are the future of application delivery. It is an application packaging and delivery method that guarantees that your containers will always run the same, regardless of the environment it is running in. In short it is well contained. This is exactly the fundamental requirement of Microservices

Container is an old concept. Most familiar being the java web archive and servlet containers. Latest and the most popular incarnation being the docker containers. Linux containers allow higher density and better utilization of hardware resources.

The advantages are

Rapid provisioning
Scale quickly.
Eliminates the environment inconsistencies
Improves the velocity of development by allowing development teams to choose the software stack that is best for their service.
Easy sharing
Isolate problems
Simplifies continuous integration and testing

References

Web Containers https://en.wikipedia.org/wiki/Web_container
Docker https://www.docker.com/whatisdocker
Oracle Zones http://www.oracle.com/technetwork/server-storage/solaris/containers-169727.html
How netflix does Microservices https://www.nginx.com/blog/microservices-at-netflix-architectural-best-practices/
Book titled : "Building Microservices" http://shop.oreilly.com/product/0636920033158.do
Video Library http://www.infoq.com/microservices/
"Microservices: Java the Unix Way" http://www.infoq.com/presentations/Micro-Services

For More Agility Do the Waterfall !

2016-05-10T22:42:00.000-07:00

Yes you read it right. If you want to be more Agile then my recommendation is to do Waterfall model . But do it in reverse direction.

Here is my simple theory - If the Waterfall model is opposite of Agile, then by doing Waterfall in opposite direction you get Agile! If Waterfall has long product cycles then we make them super short.

Without further ado..

Fail Early, Fail Often, Fail Cheap

Agile Development has one and only one reason for its existence - We need to respond to changing customer requirements in timely manner by better utilization of productive resources.

Now that requires discovering customer requirements. In his book Lean Startup author Eric Ries talks about using Validated Learning - a process in which one learns by trying out an initial idea and then measuring it and validating the effect. Our goal then is to define and discover a minimal viable product (MVP) which is the "version of a new product which allows a team to collect the maximum amount of validated learning about customers with the least effort"

Turning back the Arrow Of Time

Let now do the Waterfall in opposite direction.

1. Announce your product's General Availability : Start with writing an internal press release of your finished product. The target audience is end user who is going to benefit from your solution. Describe how your product is better than your competition and how it exceeds customers expectations. Like a real news story, include a narrative scenario of how one customer solved their most pressing problem using your product.

At this point if there are not enough real benefits to make it a compelling value proposition then it is unlikely that product will succeed in the market place. Rework on your product idea. Don't rush this step. Get it right - are you appealing to right market segment ? Do they really have that problem that you are trying to solve? Remember Mr. Kano? Have you used right portfolio of exciting/cool features and must have functionality ? Have you covered all stages of Buyer Experience Cycle ?

Once you have this narrative scenario/ press release - use it as a light house to guide all your discussions and planning. This press release is what James D. Murphy, author of book Flawless Execution calls Future Picture - a high resolution description of the way we'd like things to be. The richness, the completeness is what makes it work by having sufficient content and clarity to provide guidance down the road.

2. Test with limited Beta Users

Invite your most friendly customers to test your product. At this point obviously what you don't have is the working code. But worry not , you can still conduct the usability testing by conducting what is called Paper Prototyping. Instead of customers interacting with actual software they walk through the mockups and paper drawings. http://interchangeproject.org/2013/11/02/paper-prototyping/

This is super useful because you get direct feedback about your product and discover missing and confusing features. It is super cheap and super easy - because all you require is paper and pencil.

But make no mistake - this is NOT about UX design only. For every user interaction there must be an underlying API that must implement that functionality. Your services don't live in a vacuum - they are there to enable user scenarios - so first discover what those user stories are. This also uncovers a underlying mental model that users, experts and developer use to think about the "stuff" in your applications domain. In his book Domain Driven Design, author Eric Evans explains importance of discovering what he calls Ubiquitous Language. This model is input to your entity model. Using the ubiquitous language in conversations with domain experts and end users is an important part of testing it, and more importantly discovering the domain model.

The most valuable outcome of this stage is domain model and set of user stories.

3. Deployment

Next you should write deployment scripts and figure out how you are going to deploy your software. It helps resolve many issues early in the game

(a) how do you do branching ? Service release management? (b) How do you handle various deployment stages - (prod, pre-prod etc) (c) How do you package it - docker image? VM image? .jars ? (d) How do you manage dependencies in your code ? (e) Do you have stateful services or stateless ? How many ? How many for each stage? How do you scale them up or down? Where is the configuration stored (f) where do logs go ? (h) what about test infrastructure ? How do you stress the product ? how do you measure performance ? (i) can you use open source ? do you have to open you code? (j) How do you configure CDN? (k) How do you charge the customer (l) What is your architecture ? 3 tier? 8 tiers ? how do micro-services discover each other ?....so on.

All these decisions affect the way your team works.

In addition it is a pre-requisite for integration testing. The software does not need to be ready - yet. If your software is a command line utility, it just prints "hello world" . If it is a REST service it just returns 200 OK. If its a mobile app it just shows a logo. It is otherwise useless - does not do anything interesting. But most importantly - you can deploy it !!

4. Integration

Next is integration.

Define end to end Acceptance Tests: By this time you have broken down your news release scenario into manageable set of user stories. You must now define acceptance criteria for each user story.

Assign clear responsibility to services/ components: You have an idea about how your architecture looks like and you have assigned capabilities to each micro-service/ component. It is time to define how they fit together. Are there missing components ? Is data lost in translation ? Do you need to transform data? Walk through each scenario and user story to discover what functionality a service needs to implement, what data it needs to store and what data other services can provide.

Define perf and scalability goals: This is the time to define your performance/scalability goals for each scenario (and sometimes each user story). Having clearly defined measurable targets helps drive implementation decisions.

Create Scenario Score Card : Create a score card to track how far are you from meeting all your goals - SLA, usability, capacity utilization.

5. Unit Test

Use Test Driven Development for each service/component. Ask your dev team to write test cases before writing any code.

This is a well established practice in many places. I need not elaborate...

6. Implementation

This is where you have reached the point in development process where there is lot less uncertainty and increased clarity about the intended functionality.

Early in the cycle everything in the Scenario Score Card will be in red, but that motivates team to fix that and strive towards a green score card. Release criteria is simple - when everything is green you know you are ready to ship the product for real !

You are writing tons of quality code and completing feature after feature. You are experiencing what the psychologists call - the Flow !

Flow, also known as the zone, is the mental state of operation in which a person performing an activity is fully immersed in a feeling of energized focus, full involvement, and enjoyment in the process of the activity. In essence, flow is characterized by complete absorption in what one does.

7. Design

You have shippable product. You have well commented and well tested code. It is time to write one pager "Getting started .." design document, so that new hires know where to start looking for the executable design !

Conclusion

For More Agility Do the Waterfall !

Resurrecting Object Curry - Part 4 : Managed or Native ?

2012-05-18T00:32:00.001-07:00

As I mentioned in earlier posts Object Curry was a language I was designing so to speak in my college days (1996-1998) and that I am planning to resurrect it and make it more modern.

One important issue is whether object curry is "Managed" or "Native" ?
It is very hard question for me to answer correctly but lets just go back to source and see what were original thoughts.
As it often happens ideas about language turn into a platform and then into OS concepts. So for a while I started calling Object Curry by various names like Component Mantra , OS Mantra and even the name Winix
Here are the original thoughts , I think many of the ideas are still valid...
I'll add commentary to the posts and ideas in my next post after the weekend. But for now just paste the original notes..so here you go straight from the source.

Virtual Machine for C.

Two stage architecture.

Web Pointers for Distributed Computing !

Some object memory layout stuff

Final thoughts

I think I will still go with the C virtual machine design. The "C pointers" here are garbage collectable.
For now we'll just output C code (instead of C++11) and pretend there is VM that handles it.
Support web pointers .
I have a set of hand written documents that tell why VM should not be low level but should have very high level instruction set. (so that linker-loader has more knowledge that it can use to optimize , something very relevant even today. ) I will go over it again...

Resurrecting Object Curry - Part 3 : New/Experimental Parsing Algorithm.

2012-05-16T21:51:00.002-07:00

In part two I talked about using parsing strategy that is inspired from Generalized Phrase Structure Grammar. In Object Curry compiler I am going to use a new and experimental strategy.

Separation of Immediate Dominance and Linear Precedence

In BNF form of grammar the production rules are given in the following manner
A ::= B C D
Where A is a parent and it can have three child nodes in that order.
However my parsing strategy will separate immediate dominance and linear precedence.
To best of my knowledge no one has attempted to define parsing strategy and grammar specification as defined below..

Immediate Dominance : In simple terms it says A is the parent of B, C and D . It does not specify in which order B, C, D should occur.
Eg Rule A--> B, C, D specifies that A can have three children

Linear Precedence : Specifies order in which children are. Orders can be partially specified
Eg Rule B < C specifies that under A, B must occur before C

Head Identifying Rule: Each such production has exactly one head element and must occur in the production.
Eg. ConditionalBlock ~ IfClause

if {} is valid
if {} else {} is valid
but else {} is not because the head is missing.

[place holder for the diagram]

Example is
QueryExpression --> SelectClause, WhereClause, FromClause.

With the separation of Dominance and Precedence all of following are valid production of the rules.

select * from tbl where col == 10;
from tbl where col ==10 select *;
...

Syntax Directed Translation and Attribute Value Calculation.

The values of attributes at each node in a syntax tree is calculated in following manner.
Synthesized attributes : Values of the parent is a function of values of its children.
Eg. In expression from x join y , the value of tuple type is determined by value of its children

Inherited Attributes: Attribute value is inherited from parents to the children.
In java like try catch block the closable variables are inherited.

Inferred attributes : The attributes are calculated using rules that are applicable to only nodes that have certain properties.

Algorithm
1. Variant of recursive descent for creating syntax tree.
2. Topological sort based evaluation of dependency graph of attribute values.

I might stumble upon unexpected problem.

Useful References :
[1] Generalized Phrase Structure Grammar by Gazdar,Klien, Pullum and Sag
- Book about theory of natural languages!
- chapter 3 , nature of grammatical rules.
[2] Compilers : Principles, Techniques and Tools by Aho, Sethi, Ullman
- the compiler book
- chapter 5, Syntax directed translation.

Resurrecting Object Curry - Part 2 : To Write is to think

2012-05-16T17:45:00.001-07:00

In my earlier post I indicated that I plan to resurrect "my" language Object Curry. The source of this "inspiration" was my handwritten notes that I have kept from college days.
Many of the writeups seem silly ( but sme are really interesting) and had some new ideas.
But what are these "notes" and why I have kept them for so long ?

To teach is to understand - To write is to think.
I have just too many teachers in my family. My grandma was a teacher , my father is a medical doctor and of course a head of the department in a medical college. My mom was a principal of high school. My other grandma's sister was teacher. Both my uncles married teachers and my other aunt married a english professor and one of my cousin ... well you get the point. Something like Marisa Tomei in My Cousin Vinny.
The point is that my father says that to teach is to really understand. When you teach something to someone, you benifit the most during the process. You aquire clearer , crisper and potentially profound understanding ...
Somewhere in my my highschool years I started writing notes for myself as if I am teaching it myself! That habit remained though out the college days and even trace of it today .
Though I am writing for myself my tone was always as if I am teaching class or writing a tutorial.

Putting your fuzzy thoughts in writting helps make them concrete, crystal clear and most importantly durable.

Language is defined by how it is used.
Any language is ultimately defined by how it is used and how it feels to program in it. So instead of defing a precise spec and BNF grammar I will just go with sketch of an idea. Language is what my compiler will implement it !
I have tried thousands of syntax variations on my whiteboard and every time I try something out I discover some problem with it.

What's the plan then ?

I will go through with my old writeups and try to see what is still useful and what can be extended. May be create new write ups. Benefit: may be I'll come up with something cool.
Implement parser in at least three langauges ( one of C#, java, Objective C) Benefit: I will practice parser writing and practice writing in 4 different dev environments.
Write as many algorithms in Object Curry as you possibly can. (Graph colouring or k-mean or page rank etc) Benefit: Revise my algorithms ! Make my Object Curry truely useful.

Unless of course I take project some place else or come up with even better idea.

Ground Rules for Parser
I am going to use parsing strategy that is recursive descent styled. But a twist taken from Generalized Phrase Structure Grammar. where child nodes may not be ordered and where there are still partial ordering.

The parser will for now output C++11 source code for now.

Resurrecting "Object Curry" - Part 1: SQL/NF and Datalog

2012-05-16T15:11:00.004-07:00

In my college days I was working on a language called Object Curry. (Around 1996-1998).
As I was cleaning my stuff yesterday, I came across treasure trove of large numbers of my handwritten notes from college days. That's where I found "specs" for my language "Object Curry ™".

Many of the ideas are still applicable and I have decided to write a compiler and updated spec for the language. I plan to use parsing strategy from natural languages called Generalized Phrase Structure Grammar.
If the output is sensible enough I'll take it further.

What's in the name ?
The name is derived from my attempt to mix object oriented programming with sql/nf like querying.
That sounded like a tasty Indian Curry. On top of it can claim connection to currying in functional programming.

Renovation of syntax
I actually found two syntax for the language on Pascal like and other C like. But over the years I have kind of merged it look like below.
The syntax remains pascal inspired but with more curly braces than before.

class Foo
{
public x : int;
private y : char; //note reverse order and pascal like colon
protected arr : int { 1, 2 ,3};
public Fn(param:string): int
{ ... }

}

SQL/NF
SQL NF is form of nested relational calculus first published in 1985 , it has nested tables and two new operators nest and unnest.
Here are some of the original hand written notes. These ideas are still valid and used in new version of Object Curry.

Original Object Curry was an attempt to solve impedance mismatch between querying collections using declarative syntax and still being able to use in memory data structures. (see this note or this one)
The enum keyword from C++ is repurposed to create some amazing syntax possibilities including piping and sequence generation. Mixing C++ pointers, streaming and iterators there was some good facility for cursor management.
The dynamic queries were also a possibility.

I will blog about the new syntax and semantics very soon.

How is this different than LINQ?

"Discovered" or rather stumbled upon by me before C# and Linq.
Uses SQL/NF as its basis and does not have group by.
Not Library based but syntax based. Compiler knows a lot more about the underlying collections.
"Query plan" so to speak is decided at compile time.

Integration with Datalog and Prolog.

I was very fascinated by possibility of Object Curry having some capabilities like Datalog and better integration with Prolog.

Here are some initial thoughts from my college days

Am I being nostalgic or this has some practical applications?

I think the concepts and syntax elements in the Object Curry are still valid in the era of NoSQL, json, GPGPU and map reduce. Hopefully I am able to come up with a practically useful implementation.

Applying Radical Programming: Software is a Batch Process

2011-04-26T12:56:00.000-07:00

Before applying the lean thinking to software engineering we must understand what are the concerns that lean thinking tries to solve and where exactly process of producing software fits in.
See my earlier post What is radical programming? if you want and introduction to Radical Programming.

Mass Production vs Mass Customization
Unlike craft production mass production relies on the standard components and economy of scale. Each unit is like every other unit and parts are interchangeable. The assembly line can increase the throughput but then it becomes very difficult to change and to customize.
On the other hand the more customization is required the less standard and costly the production becomes. Why is this relevant to software engineering ? That is because each software system is unique we have a need for high degree of custom software development and at the same time we need to bring in mass production techniques.

User Story (Use case) is the unit of software production.
In Radical Programming we treat user story as the unit of production. Our output is measured in terms of number of user stories implemented. We imagine an assembly line where a user story starts its life as a simple statement of user need which is developed into full set of acceptance tests and lightweight use case. It is then translated into design delta and finally implemented, tested and integrated. Individual user stories are the basis of calculations to make production decisions.

Process Types
One of the most critical factor in implementing efficient production system is to identify the process type that best achieves the tradeoffs between quality , time and flexibility.
There are five types to choose from

Project Process - There is a high degree of customization and very low volume . Which means each project is unique. Flows and dependencies are very complicated.
Job Process - Even though it is customized the volume is high enough. Which means each job is not as unique as project. Each new order is handled as a single unit and produced made to order. Flows and dependencies are jumbled. Examples are your doctors's visit, jobs with car mechanic, process for auto loan approval. Variety is achieved through "made to order" strategy.
Batch Process: There is high volume and variety is achieved through "assemble to order". Most importantly items are produced as a batch. Some intermediate products might be pre-processed.
Line Process: Volumes are very high. Fast food services and car assembly lines are examples of line processes. There are line flows with very little inventory held between operations.
Continuous Process: It requires extremely high volume and very generic standardized product.

Software as a batch process with Time Boxing

Like Scrum the radical programming achieves its goal using series of scrums. In radical programming we treat the software production as a Batch Process where we produce batch of user stories each iteration.

by Sachin Joshi
for Washington Technical Resources

Simple theory of Management: 8 Ps

2011-04-26T11:07:00.000-07:00

I have a very simple theory about what senior managers need to do. There job is to convert potential into profitability through internal and external interaction.

And that means specifically managing 8 Ps described below. Call it "Sachin Joshi Model of Management" if you wish.

Discussion is more relevant to executives and other senior managers who in my vocabulary are called "business owners".

Financial Perspective

1. Profitability : The reality is that businesses need to keep themselves profitable which means managers must take right financial decisions. At minimum it means managers must be financially literate. Beyond budgeting and forecasting there are many decisions that require using finance/accounting tools. Selecting the right project size and team size. Pricing the products. Making buy vs build vs rent decisions. One of the most useful concepts are Minimum Marketable Feature and idea of Real Options.
External Perspective
2. Positioning : Nothing is so critical than finding the right fit to market and positioning the products in a market place. Nothing succeeds like an idea whose time has come. Your talent as a manager is in finding that right idea. The entire process of dividing the markets in right segments, selecting the right customers and solving right set of problems for them is all what I call "positioning". It requires making right decisions all the time. And that doesn't happen without instituting the customer focus. Customer focus is not some magic thing you do but a value system and tool that results in a well defined procedure for "positioning" your service.
3. Partnerships: No business works in isolation. So yet another job is to manage partnerships with vendors and clients.
Internal Perspective

4. Programs: Many managers make mistake of thinking that what they are delivering is product or a project. But in reality what they are doing is managing series of projects and set of products which requires Program Management. Defining and managing program objectives is a top item in job description of senior manager. A successful manager must be able to map strategy into programs and then translate the vision in terms of program objectives. (I plan to write a blog about mapping strategy into program objectives.)

5. Process : No software gets built without proper process in place. One of the important jobs of manager is to define process and actively manage it. There is a large body of knowledge dedicated to project management and process improvements. Wisdom and drive in applying these principals to increase quality is what managers demonstrate everyday.

6. Policy: Make sure that technical standards are defined and followed. Rather than actually making each and every decision themselves senior managers define policy. To me policy is framework in which those decisions are made. One of the most important job of managers is to define that framework and provide guidance in applying it to everyday decisions.

Growth Perspective

7. People: The generative power of business comes from the talent and creativity of its people. And no where is this more important than in software. Success in providing the environment where people can grow is how we must measure our progress

8. Productivity : Equally important is increasing our production capability or "Productivity". Smart tools turn smart people into even smarter geniuses.

by Sachin Joshi

For Washington Technical Resources

Speech Technology : Phonology

2011-03-22T00:38:00.000-07:00

Words are formed by series of syllables which re formed by series of phones. In last blog we looked at the Phonetics and how variety of speech sounds are generated.

Contrasts, Phonemes and Allophones
We already looked the variety and variations of the phonetic elements. But not all sounds are used by all the langauge. Most importantly not all sounds are distict in the same langauge. Consider ph and p (aspirated vs non aspirated). This distinction is not important in english but extremely important in indic langauges. Similarly indic langauges have two D's one dental and other palatal. English has mostly alveolar where as spanish has mostly dental. If indic langauge has vast number of consonants the english langauge has many finer distinctions betweeen vowels. The point ? What makes two sounds similar or distinct really depends on the langauge. From speech technology perspective this distinction is important because speakers may not articulate sounds exactly like each other when that distinction doesn't matter. Whereas when speech recognition fails to distinguish the sounds when they should it is a problem.
When two or more phonetic elements are distinct but map to the same phoneme it is called allophones. One of the most striking example of allophones having distinct value is "visarga" in Sanskrit where 's' and 'h' are equivalent to each other. Similar historical allophone is hard 'g' like in gut and soft 'g' as in ginger. That is exactly the reason why we have letter 'g' used for two completely different sounds. At some point these sounds were considereed close to each other and therefore allophones of each other.

Structure of Syllables
Sounds are either 'singable' meaning they are sonorant or not. Vowels, nasals and liquids are singable.All others are not. Sylables almost always have sonorant sound at the nucleus.

Syllable is formed by Onset+(Nucleus+Coda).

Not all combinations are relevant. Some langauges allow many constonants in onset while others can not handle it. In every language there are some obvious constraints on what words are valid and what are non-sense. We must understand these constraints.

Once we understand all this our next task is to actually group the phonemes into sylables.

Stress, Mora and Syllable timed languages
In a stressed langauge like english or russian each stressed syllable takes about equal time. Where as in other languages like Spanish or most of the indic languages the syllables are timed equally. The mora based langaues are yet another way of timing the phonemes.

Sandhi
Yet another complication is formed by what is called Sadhi in Sanskrit and Liasion in French. I have studied Sanskrit for three years and I know first hand the pain of "breaking" the Sandhi and coming up with individula words. I won't go into all the details but all of us in all of the langauges merge words while talking and we must be able to separate them when recognizing the speech.

Speech Technology : Phonetics

2011-03-20T23:45:00.000-07:00

Last year around this time I was working on one of my projects related to speech recognition. It was a personal side project and I really did not give the project enough attention. Plus it had been a long time since I had seen stuff like Fast Fourier Transform and I kind of procrastinated .Well - it is time to again start where I left and true to its original meaning - blog. This is a series of blogs is where I speak whatever is on mind about speech technology, phonetics and various options available for implementing it.
I first got introduced to the subject of phonetics back in 1992. I was in college and used to visit my aunt every weekend. My uncle used to teach Communication Skills in a technical college. He must be having a couple of dozen of books on english language and teaching english. While going through his bookshelf I found a book on english sound system. That was the start of a fascination for phonetics and languages. My dad also had bought all volumes of Marathi Vishwakosh (Encyclopedia) which I used to read a lot in my free time. (And I had a lot of free time back then). I then read about phonetics and grammar of my language and about human language in general. That fascination still remains ...
The language ability of our race has made us the only species able to successfully transition to civilization. Every human being has capacity of language and it is impossible to think of human society with out language.
[Without language we would be still in sub saharan desert and probably extinct by now. As a side note please do watch Journey of Man if you get some time. Anthropology is yet another subject I am fascinated with.]
How human voice is produced.

The most important key concept is this: Our tongue is a very flexible muscle that can form various shapes and that profoundly affects the way we perceive the basic sound that begins at the larynx.

[Edited from original here : http://en.wikipedia.org/wiki/File:Illu01_head_neck.jpg.]

That brings us to the next concept. There are two types of sounds viz. vowels and consonants.
When the airflow from larynx is not obstructed we perceive that sound. Anyone how has dealt with waveform of human sound knows that most of the waveform is basically sound of vowels. However the most interesting sounds are generated when the airflow is blocked (or substantially modified) for the brief amount of time. This time frame is seriously tiny compared to rest of the vowel sound and we perceive it as consonant.
In terms of digital signal processing the waveform of the voice that starts in larynx is modified by the resonance of the vocal tract and therefore we apply the convolution of the simplified model on the right side.

Vowels
Vowels take most of the time in speech signal. All consonants are meaningful only in the context of background of robust vowel signal. The larynx is actively producing "voice" during the vowels.
The quality of vowel depends on four attributes.

Height of tongue position- In other words whether the gap between tongue and roof of mouth is closed or open. generally four positions are considered. Open, Open mid,Close mid and Close.
Position of tongue - Front, central or back
Roundness of lips - The roundness of lips add another effect. They are generally rounded for back vowels.
Nasalization ? are the vowels nasalized.

Below is the list of known vowels and their IPA symbols.

Edited from original here : http://en.wikipedia.org/wiki/File:IPA_chart_2005_png.svg

The best way to analyze vowels is to look at their frequency spectrogram and look at the peaks. The first three formant are specifically interesting. The roundness of lips changes the positions of formant.
Again there are further diphthongs and glides that are combination of two vowels.

Consonants
The consonants are interesting because they are numerous, show great variation in how they are produced and the signal is available for only the short time. They are "negative" because the voicing and vowel are interrupted or blocked by the position of tongue. Here I am going to use somewhat non-standard terminology and classification only because that is how I understand it. Also because i was introduced to the subject via Sanskrit Grammar.
There are three main things to look for - (A) Properties of original sound that is obstructed (B) manner in which the air flow is obstructed/modified
(C) place of obstruction/modification
Properties of original sound

Voiced vs Unvoiced - whether voicing continues or not . [b -p]. [k -g][t-d] are some examples . (saghosh and aghosh.सघोष- अघोष )
Aspirated vs Non aspirated - this difference is important in Indic langauges it effectively doubles the consonants available for use in languages. (alpa prana- maha prana अल्पप्राण- महाप्राण)

Manner in which flow is obstructed /Modified

Stops - The airflow completely stops
Friction - Sound produced by friction is introduced in the mix.
Affricates - these are combination of stop, followed by the friction at the same place.
liquids - sibilant and approximants - where air flow is partially blocked
Nasals - the airflow goes through the nasal channel

Place of articulation

Labial

Bilabial
Labio-dental

Coronal

Dental
Alveolar

Palatal

Alveo-palatal
Retroflex
Palatal

Dorsal

Velar
Uvular

Radial

Pharyngeal /Epiglotal
Glotal

Edited from original here : http://en.wikipedia.org/wiki/File:IPA_chart_2005_png.svg

Common Tasks in Speech Recognition

Audio signal capture
Spectral Analysis
Phonetic Feature Identification
Phoneme Identification
Phoneme to word translation

Does democracy make most people unhappy? Future of democracy

2011-03-18T01:47:00.000-07:00

I am a student of computer science, a science fiction writer and I am interested in philosophical discussions every once in a while, so while world is busy transitioning to democracy I started thinking about how computer science , social networking can help usher the democratic utopia. My mind was racing, I started thinking about machine learning, "collective intelligence algorithms", optimization and things like Nash Equilibrium etc..I already had an idea of science fiction taking shape in my head...and BAM ..I realized something very simple.
I realized we have to solve a very basic problem first!

First Past Post Voting or Formula for maximum dissatisfaction?
In many countries the elections are held using what is called first past post method. The person with most votes wins the seat. call it winner takes all. This sounds fair but in a multi party system like India or UK or many other countries there are always more than a couple of political parties and many a times a winning candidate get less than 50% of votes. This means that there are more people NOT liking the winning candidate than the ones who voted for him/her.

Here is an example - there are 4 parties

Candidate A - 35% votes
Candidate B - 30% votes
Candidate C - 20 % votes
Candidate D - 15 % votes

Clearly candidate A is winner but also that 2/3 of the population does not like him.
As if it looks like Democracy makes more people unhappy than it makes them happy !!
This is not a problem with multi-party system but a problem with vote counting method.

Are there any alternatives? Yes enter Science of Voting Methods
Science of Voting Methods
There are many voting systems. Some are proportional and preferential.
Please see: http://en.wikipedia.org/wiki/Voting_system
One of the methods that can be readily used is Single Transferable Vote http://en.wikipedia.org/wiki/Single_transferable_vote. Here the voters rank the candidate with their preference and candidate with most preferential votes is declared a winner. To me this seems like a simple fix that once again makes most people happy Jeremy Benthum style. One of the barriers has been the complexity of vote counting. But with the advent of computerized vote counting it can be easily administered at relatively low cost.

Popular Votes vs Representational Democracy.

This is a pure thought experiment with no relation any country/nation/state what so ever. Let us talk about a 22nd century colony on Mars. Let call it XYZ. The problem with first past post voting was solved long time ago in 21st century. But there are other problems though that need to be solved differently. And that is a problem of representing evenly distributed minority.
Say in XYZ there is a 30% population which is considered minority. But it is evenly distributed. In this case it seems like they will be massively under represented. They can never elect 30% of the representatives- in theory they may get none.

Bicameral Parliament with a different structure.
One of the invention of modern democracies is bi-cameral parliament/ congress. There is a upper house and a lower house. Generally a upper house has equal (or fair) representation for each state/province. However theoretically this need not be the case. A party list system where an entire country votes for their favorite party can also be used. Each party gets the seats proportional to the aggregate votes they receive in election. In this example instead of states sending delegates, parties send their nominated candidates. In this minority can be always get their say.

Tri-cameral parliament ?
Many people will object to the idea of changing the upper house. But how about adding a third house which is popularly elected? Let's call it middle house! Instead of two houses passing the law three houses will need to do that. Well that sounds complicated but the idea of "double majority" is not far from it.
Responsible Executive and Separation of Concerns?
There are two styles of democracies - Presidential and Parliamentary. In parliamentary system there is no clear separation and in presidential system no clear accountability. We can actually solve these problems by merging the concepts with president being responsible to lower house and only middle + upper house acting as legislature. Lower house still has the budget!

Well, well !! That's enough for now. Political science is not a subject of this blog we are only interested in the algorithms for voting system so we'll leave all that undiscussed and unsaid and let the people from 22nd century figure out tri-cameral parliament.

Democracy of the future.
So how will democracy of the future look like ?

With instant communication and tele conferencing do representatives need to be present in the "house" ? Or can they just "log into the parliament" to cast their vote and participate in a debate.
Is law making in Open Source style possible ?
Can there be a one big direct democracy?
Can a giant computer cluster solve the optimization problem of representing most people with least amount of representatives?

Really how will future democracy look like?

Disclaimer : This is a blog related to science, computers, philosophy and its intersection with the society. I have not expressed any political views here. It is from pure theoretical perspective and as an interesting computer science problem. This is not a place for flame wars and random comments. Intellectual discussions and comments are welcome. But if you express your political views those are yours not mine!

What is Radical Programming?

2011-03-17T22:52:00.000-07:00

What is Radical Programming?

It is a post-Agile software construction methodology which aims at order of magnitude improvements in value delivered through software projects.

The word radical has a Latin root radix.

Webster defines: (1) proceeding from root (2) fundamental (3)unusual (4) cool.

In that respect it recognizes that the primary source of all the value ultimately created through a software is the source code itself. It recognizes that root purpose of the software is to satisfy customer need.

Eight-fold way of Radical Programming.

Aim of any software is to create customer value. Aim of Radical Programming is to create order of magnitude returns on the efforts required to generate that value.

The eight principles of Radical Programming work together to achieve exactly that.

In today's fast moving world with multi faceted sales channel Software Product Line Engineering is the most sensible option. It creates multiple differentiated versions of product by using the same underlying code base and repository of components. As you can see it is component oriented reuse.

1: Four Quadrants

Radical Programming uses a variant of Software Product Line Engineering that simultaneously undertakes parallel activities in four quadrant.

Quadrant I : Creating and discovering Domain Model. All prototypes, spike solutions and various differentiated product versions reuse the same object oriented domain model.
Quadrant II: Product Assembly.Various differentiated product versions are constructed using iterative development. Rapid delivery of customer feature is the primary aim. The secondary aim is to achieve maximum reuse possible.
Quadrant III: Creating Platform code. Most products require common infrastructure and we spend significant time in developing productivity tools
Quadrant IV: Aspect Orientation.We also spend significant time taking care of global and cross cutting "aspects" like performance, security ease of use etc

2:Value Streams

Applying lean thinking to Software Engineering it envisions the assembly line where features are continuously "manufactured". A feature starts it life as user story and goes through various development stages of acceptance tests, precondition, post conditions, detailed description and test , design, implementation , unit tests and is finally released. Radical Programming considers software delivery as a Batch Process. Scrum and Kanban are used to deliver the batch. Body of knowledge developed for lean thinking and batch management is then systematically applied.

3:Code is Design

Radical Programming treats Code as the primary expression of Design. It uses code centric approach to development where unnecessary documents are eliminated. Various techniques and concepts like Static analysis, Literal programming and Design by Contract are used. Code is re-factored mercilessly.

4:Standard Architecture

One of the ways to achieve great flexibility and productivity is to use standard architecture with predictable interaction between components. N-tier service oriented architecture or plugin based architecture or pipeline like architecture. Emphasis is on implementation agnostic interfaces and loosely coupled interfaces so that components can be readily interchanged. There are many many design principles that can be seen in existing systems and design philosophies. Eg. Unix Philosophy, COM, N-tier SOA with REST etc, Many "component oriented" CMSes.

5:Data Driven Design

One of the main principles of Radical Programming is to use data driven programming. This means program logic is driven by configurable data sets. Every argument that can be made for DSL is equally valid for data driven programming.

6:Fractal Time Boxing

Time boxing is a familiar concept, however time boxing is applied to various time horizons and product definition and planning is handled only at the appropriate level of details. Vision is defined on 1-3 year time horizon, the mission and strategy is calibrated every quarter and quarterly goals are achieved by series of monthly/fortnightly releases. At every "scale" the process looks similar because we deal with uncertainty, deliverable and work to be done at only the appropriate level of details.

7:Spiral Development

Spiral development is different than iterative development. In the context of Radical Programming it means within a sprint product is developed by first building it in big chunks and refining it again and again. Rapid development and progressive elaboration is the mantra.

8:Flexible Team Structure.

In short it is a self organizing team with collective code ownerships and lack of silos. Developers sometimes wear SDET hat and sometimes volunteer to drive issues like product wide secuirty/performance etc. Load balancing is the matra.