Market-Based Resource Allocation
In 1988 Mark Miller (of E and Xanadu) and K. Eric Drexler (author of Engines of Creation) propsed what they called the 'agoric model' for resource allocation. For instance, each process can bid in auctions in order to purchase CPU time on which to run (or, for that matter, resell). Having recently read several pieces of Singularity-oriented fiction (Accelerando and After Life being the better of them), these concepts seemed particularly on target.
It's already fairly common to 'rent' CPU time and memory (in the form of virtual private servers and remote storage), but right now all companies offering such services only sell large blocks, at more or less fixed rates. My suspicion would be that this gives a larger income per client, but at the cost of utilization. Would it be more profitable to use a fine grained model, renting disk at, say, 10^-7 pennies per kilobyte-hour?
It was also interesting to consider these papers in the context of E, smart contracts, financial cryptography, and a half a dozen other concepts. Still a lot of things to learn...
The Agoric Papers, and a related Wired article from 1996.
Posted in programming at 2006/12/13 04:52; 0 comments
In an earlier post, I lamented the dearth of really solid C++ networking libraries. Someone on the Monotone list mentioned a networking library, Asio that I'm getting warm fuzzies about. The interface reminds me a bit of Python's Twisted (which I have beeen carrying around in my head as an ideal for some time now), is actively maintained, fairly portable, and seems to have a bright future - it's being included in the next release of Boost, and it looks likely that it will be included in C++ TR2 (meaning there is a very strong chance that something derived from Asio will be included in the next version of the C++ standard, due out in a year or two).
The normal synchronous interface is very simple and easy to use, though it also isn't anything particularly special; OO wrappers to Berkeley sockets abound. The real prize is an asynchronous interface based on the Proactor pattern [Asio = asynchronous I/O]. I'm still having some trouble really wrapping my head around the proactor, but I've got good feelings about the design and implementation, so I'm going to keep playing around with it.
Right now Asio is mostly focused on networking, but in principle should be extendable to file access, windowing event loops, audio input and output, and all kinds of other interesting things.
Posted in programming at 2006/11/05 03:13; 0 comments
Algorithmic Complexity Attacks on Allocators
A few years back some researchers presented the concept of performing denial of service through algorithmic complexity attacks, which essentially cause pathological behavior in data structures like hash tables through carefully chosen inputs. Of course the general concept was well known; Introduction to Algorithms, more or less the standard algorithms textbook, begins the section on universal hashing with "If a malicious adversary chooses the keys to be hashed, then he can choose n keys that all hash to the same slot, yielding an average retrieval time of O(n)". In the case of data structures, the typical response is randomization, which is simple enough in the case of hash tables. Universal hashing is the theoretically clean way, but even something very crude, like initializing a CRC feedback register with a randomly chosen value, will often be more than sufficient.
There have been a small number of papers over the years which present memory allocation in game-theoretic terms - one side being an application, the other being the allocator. Each "turn" of the game involves the application making an allocation or deallocation request, and the allocator must respond in an online fashion (that is, it can't batch together requests and reply all at once - it's only context for requests are those which have already completed, and has no knowledge of future requests). This form of analysis doesn't seem particularly useful in the common case; applications tend to have very regular patterns of dynamic memory use, and an allocator which had no pathological cases might well perform much worse on average, compared to a general purpose allocator with some obscure pathological case that never came up in common workloads. However, it does seem very valuable from the perspective of analyzing complexity attacks.
Can these attacks be carried out against memory allocators in practice? How strongly can an attacker affect the memory allocation patterns of an application (especially fat targets like servers and OS kernels?). What pathological cases exist within common memory allocator implementations, and how serious are they?
Are there any known designs for randomized memory allocators? I have done a literature search and haven't been able to find anything along these lines.
Posted in security at 2006/11/01 23:46; 0 comments
I came across Magma, a company that builds PCI enclosures. Insert a PCI-E card to your host machine and connect it over to a secondary box with 4 to 13 PCI or PCI-X slots. However, the cost is sufficiently high that it would be cheaper to just buy a second machine. Shame, since I could actually use this, if the price was reasonable.
Posted in hardware at 2006/10/31 15:01; 0 comments
Some C++ Libraries Worth Looking At
C++ is a horribly schizophrenic language. The infamous Stroustrup quote that "In C++ it's harder to shoot yourself in the foot, but when you do, you blow off your whole leg" goes a long way towards describing the issue - C++ is a language of surprising expressive power, but most of the time that power is aimed at feet. But when it's used well, it leads to some rather lovely pieces of code. Here's my rundown of some favorite C++ libraries. All of these libraries are freely usable in both open source and commercial applications; while that wasn't a precondition, it is a very nice bonus.
Boost is probably going to be on every list of C++ libraries worth using. While I haven't used all of the libraries in Boost, I can say that Boost.Python and the function/bind library are quite lovely to use.
Building it from source is a good reminder of how slow GCC can be, though. Install binaries if you can.
SOCI provides a very reasonable interface to relational databases, with plugins for SQLite, Postgres, and various databases I never use and don't much care about (Oracle and MySQL). A quick example.
sql << "select phone from phonebook where name = :name",
into(phone), use(name);
Downsides include the build system, which is less than enlightened, and the fact that some ways of using the library seem to leave applications open to SQL injection attacks.
OTL is another C++ database/SQL library. It seems interesting, though SOCI's syntax feels more natural to me, and OTL's database support is heavily biased towards Oracle and MS SQL; again, nothing against either of these databases, I just don't see myself using them often. Or ever, for that matter. Others are supported through ODBC, but are apparently somewhat beta-ish.
GTKmm is the first C++ GUI toolkit I've seen that I would actually want to program in. Partially, this is due to GTKmm's advantage over other libraries, which are typically much older and developed their own string/vector/assocarray/etc classes; which, of course, doesn't play very well with the rest of your STL-using code. One could drink the full glass of Kool-Aid and use the GUI toolkit types in all your code, but the idea of tying my entire application to the interface code doesn't give me good feelings. In contrast, GTKmm plays nicely with the STL, is cleanly designed, and seems significantly more extensible than I'll ever need. Support for Aqua would be really nice, but then again, I don't own a Mac, so what do I care?
Sheesh, what do you expect? I wrote the stupid thing. Anyway, I feel like the design is quite nice, much less due to my own brilliant coding ability (hah!) than my willingness to steal good ideas wherever and whenever possible. To provide some redeeming social value to this section, I'll mention that Crypto++ is the "other" C++ crypto library. They're very different in terms of style, so if you're looking for something in this niche I'd recommend trying them both and deciding which one feels more natural to your programming style.
Blitz++ and POOMA are often considered among the Tier 1 C++ libraries, but as I don't have much interest (or ability) in hydrodynamics, they have little practical use for me. On the other hand, work on these libraries has produced a number of interesting papers and new techniques - as a source of inspiration for writing high-performance C++ code, they can certainly be worth examining.
You might have noted a distinct lack of network libraries on this list. There are literally dozens out there, the best of which seems to be Netxx, which, aside from the fact that it's not maintained anymore, seems quite decent. It's not entirely perfect (perfect being defined as "how I would do it"), but having gone down that rabbithole once (see above), I'm willing to settle for a solid 98%. I'm not sure if I'm willing to settle for "maintain it yourself", though. A much heavier alternative is ACE, but the more I look at ACE the leerier I become of it. ACE is in much the same state as Qt; a good, interesting, solid state-of-the-art-in-1994-or-so design that hasn't been updated in a decade due to compatibility concerns. Right now I'm thinking of it more as a source of ideas than of code.
So what is missing from our box of C++ libraries? Most C++ applications could benefit from judicious use of the STL and the Boost libraries. GTKmm seems a solid choice for GUIs (assuming you don't just wrap your low-level code using Boost.Python or SWIG and then write the GUI in Python or Ruby). Networking is a bit of a hole, though you've certainly have a number of options there; there just doesn't seem to be a compelling choice right now.
I'd like to see an embedded language (ideally of a Scheme/Lisp flavor) that really got along well with C++ code. A decent P2P library (perhaps something interoperating with JXTA or OpenDHT) would be delightful.
For another perspective on some of this, I'd recommend this post by Graydon Hoare, which while somewhat dated (2004) is very much worth reading (I'm willing to attest that he is both smarter and a better programmer than I am - though I'm not sure how much that opinion is worth to anyone).
Posted in programming at 2006/09/25 10:47; 0 comments
[1] 2 3 4 >>