Counting Representation

Democracy is great and so is the idea of representative government. The point where it starts hurting is that majority wins. By definition, majority is representative of just majority.  Even majority representing majority is questionable. Majority does represents majority when we have just two parties. But when we have more the two, we can be easily sure that majority is not represented. For example, in a three party, highly contested elections 34% would count as winning majority and it excludes 66% (real majority).  Essentially, majority of votes don't translate to majority in representation.

Surprisingly, it is easy to fix. All we need to change is what we count. The basic idea is to add the dimension of time to representation. Instead of the crude approximation of majority, we can have complete representation for everyone over time.  As popular is management circles, you only get what you measure.

How do we measure representation? As we discussed earlier, votes don't translate to majority representation. Well some of the votes do translate to representation. The votes which are cast to the winning party. The votes that are not cast and the votes that are not cast to the winning party are useless. They don't count toward representation.

Without much ado, here are the rules of the game:

1. Votes which result in representation are "spent"
2. Votes that don't get representation are "not spent"
3. Votes that are not cast are "not spent"

In other words, votes can be stored and used across elections.  Each vote is worth 5 years of representation. They work just like currency as store of "political value".  For example: say we had a two party system with 100 people and say party A won the election with 51 votes. These 51 votes are counted as spent. Rest 49 people get to keep their unrepresented vote for later use. In the next elections, 49 people will have 2 votes each and 51 will have one vote each. It is easy to see that with 98 votes, these 49 people will we able to easily get their representation.  

Given 65 years of life expectancy and 18 years as voting age, people get to vote around 10 times in their life. If the number of political parties is less that or equal to 10, even some 10% of the population will get a chance to form a government during their life time. To make this work with even larger number of parties, we will need to either have more frequent elections or allow inheritance of "political value", just like property and money.  This makes it possible for any arbitrary group of people to eventually form a government, perhaps once in few hundred years. 

It is easy to see that this method of counting representation leads to representation of all people over time. It will probably help stop the madness around "winning" elections and all that goes into it. Why? Because if you win, you make it easy for others to win the next time. If you loose, you chance of success increase over time. 

From what I could reason about, the system has two equilibriums. One: If people are cleanly partitioned into groups, over time each group gets representation and world becomes fair in terms of representation. If the groups are greedy, they will choose policies which advance their own groups. Sadly, the same strategy will be used by each of the other groups. Sad, but fair. 

The second equilibrium, would be towards enlarging or growing the size of these groups. Essentially, if the two groups can sort out their differences and work towards what is common and important for them, we get one less group and hopefully policies which work towards welfare of all the people in this larger group. The recursive logic will bring us to some manageable number of groups or even just one.  We might even see groups getting split when they cannot reconcile their differences, but that still leaves the process fair, just and representative. 

No matter which way the wind blows, we can always be sure that everyone is getting represented over time. If nothing else, it reduces the cost of running political parties and hopefully that is the money which can be used for advancement of the country and providing public goods. 

Criticism is most welcome!  

On eventually consistent file listing

Introduction 

Cheap s3 storage comes with unusual cost: correctness.  One of the key problems while working with highly partitioned data stored in s3, is the problem of eventual consistency in file listing. What exactly is this problem and how can we think about mitigating its impact: we will discuss in this post.

File listing is a very common operations since the invention of files. Given a directory or path, it gives us the list of files under that path. Tons of lines of code written over file systems, depend on correctness of this operation.  Unfortunately, this assumption breaks when the listing is done on s3 or for that matter any blob store.

Deconstructing file listing 

One way to think about eventual consistency of file listing is to argue that we get a wrong answer. This is correct to some extent but not powerful enough to do something about it. To do something about it, we need to dig a bit deeper and understand the nature of this wrongness. I find it useful to characterise this in the following form:

• Ghost files 
• Conceived files 

Lets try to understand what they mean. Ghost files are files which are listed by the file listing operation but they have actually been deleted from the file system. This is a very common reason for job failures in spark and hive. They are called ghost for obvious reasons. Conceived files on the other hand are those files which actually exist, but were not returned by the listing API.  In the happy (immediately unhappy) path, eventual consistency causes jobs to fail, because further operations on ghost file keep failing, irrespective of the number of retries. In the unhappy (short term happy) path, we have data loss because of conceived file, because they are simply missing in the final result,  resulting in incorrect answers.  

Given these two constructs, we can argue that the wrongness of a listing operation will occur either because of Ghost files (files which shouldn't be present in the listing but are) and conceived files (files which should be present in the listing but are not there). We can now have separate solutions for dealing with detection and consequences of these two file classes.

Dealing with Ghost files

Ghost file are files which shouldn't have existed in the listing API to start with. Once they show up, they cause different problem depending on what operations we are doing with these files. Most common problem would be subsequent file not found errors. One way to deal with this is to do a fresh listing operations and do a set subtraction.
Let A be the result of listing operation at time t1
and B be the result of listing operation at time t2,
where t2 > t1.
Set A-B i.e the files which are in A but not in B, is essentially the list of currently known ghost files. Once detected, we can choose to deal with them in some form. One simple way is to ignore the failures caused by ghost files, because we know they should fail. The other option is to remove them from our task queue, because we know they are not part of the final solution set. We might need to iterate multiple times (say, till a fixed point) to find out all the ghost files.

Dealing with Conceived files

Conceived files are the files which didn't even show up.
Lets again consider that A be the result of listing operation at time t1
and B be the result of listing operation at time t2,
where t2 > t1.
Set B-A i.e the files which are in B but were not in A, is essentially the list of current known conceived files. These are files which we would have missed if we only do a single listing operation. Once detected, we can choose to deal with them in some form.  Handling of conceived files is relatively simple. We just need to add them to our working set. We might need to iterate multiple times (say, till a fixed point) to find out all the conceived files and treat them as if they were part of the original listing operation. 

It is tempting to say why not wait until the system has become consistent before starting the work. In theory it works, it practice we don't know how much time it will take. Starting with whatever information we can get from the listing API, we get a head start and can keep revising our task set depending upon what further listing API reveals. What we get through this approach is correctness but without introducing any performance penalties.

In conclusion, we can deal with eventual consistency in file listing operations by repeating the listing operation, detecting ghost and conceived files and modifying our work queues to take our new knowledge about the listing status into account.