Friday, April 13, 2012

Distributed Algorithms and Convexity

I like this  paper in CIDR 2011 which shows you how to use the convex properties of functions to implement distributed algorithm with provable properties. The idea is that if functions are logicaly monotonic then they have nice properties. This paper fills in the details of what we already knew but with the exact details of what these good properties are. FYI: logically monotonic implies that inputs only add to outputs. Said differently incremental implementations of functions based on selections, joins and projections all have the logical monotonicity property. And this brings us to convexity because that is exactly why these properties exist: selections, joins and projection is all about preserving the convexity property of the function. And finally this is why I like monadic and stream oriented programming: its about implementing incremental algorithms and with enough care you can preserve nice provable properties!

On a side note: type inference and non-linear optimization all strive on convexity.  Many concepts are built on a basis of convex properties, so your really want to pay attention to this!

No comments: