Computational Requirements for an n-Way Exchange, Part I

The underlying matching problems that describe an n-Way exchange can be solved with a variety of similar algorithms on a variety of different architectural platforms. For instance, the primary problem, optimal matching, can be solved in most programming languages, in memory, or on a database, on a single node or across a distributed cluster, given adequate CPU, memory, and bandwidth.

Large scale solutions lend themselves very well to distributed memory architectures, in particular, Java Spaces (ala GigaSpaces), Distributed HashMaps (ala Oracle Coherence), even database clusters. Why? Here is the problem- n-Way exchanges are essentially large matching engines; more so, they are large multi-way matching engines. Simple matching engines, like a reconciliation system, perform 1->1 matching. N-Way exchanges may perform n->n matching, or set matching. This is far more computationally intensive.

Essentially, set matching is a combination problem. In mathematics, a combination is an un-ordered collection of unique sizes. For example, given a set of integers, [1, 2], all combinations include [1],[2], [1,2]. [1,2] and [2,1] are equivalent here. A permutation is an ordered collection. For the same set of integers, all permutations include [1],[2], [1,2] and [2,1]. Here the ordering is significant and the last two sets are considered unique. The optimal solution to matching on an n-Way exchanges involves examining combinations for the optimal conditions.

Problems of this nature are considered by Computational Complexity Theory to be NP-HARD. That is, they take non-deterministic polynomial time to compute, a potentially long time depending on the size of the problem, but are fairly rapid to prove. In our case, the size is the size of input sets (the buy side set and the sell side set). For other algorithms, like quicksort, the compute time is mainly driven by the size of sort input. It's called Polynomial Time because the runtime can be expressed as a polynomial function where the input is the size of the problem. For quicksort it is on average, n Log n comparisons where n is the number of items to sort, and at most n^2 comparisons.

Whether the answer to a match request is optimal is rapid to prove relative to compute, which is required for NP-Hard problems. Once all the combinations are computed, a proof is simply checking each set for the criterion established to be optimum. In our case, the criterion might be minimizing the cost of shipping to the buyers or something more complex like effect on inventory, or a combination of factors. However, the cost of computing the cost each set is considered to be baked into the cost of computing the set - Yes, you may want to read that again :) - which is a rare convenience for our definition of NP-Hard.

Let's look at a simple but practical example, an aggregating exchange where sellers are looking to sell to a pool of buyers. In this example a seller offers 10 HDTV sets (units) for $1000 each, a great deal. This offer is all-or-nothing, that is, exactly 10 units, not less or more. This somewhat realistic, since the units may come in pallets of 10 that the seller will not break if it results in a remainder. This is the state of the exchange at this moment:

Without optimization there are three solutions (combinations) that work, (501, 1001), (501, 320, 321), and (1001, 320, 321). Each combination results in 10 units sold. The exchange selects the winning set by selecting the optimal set. Again, this might be the set that minimizes shipping costs.

A bit about exchanges as business entities- in almost all cases exchanges fulfill matches at the lowest possible price, defined as the least the buyer is willing to take. In this example the seller is willing to take $1000. All matches will be fulfilled at that price regardless of a higher bid. Now, that doesn't mean the exchange will ignore the bid price. The exchange may want to reward a buyer for being willing to pay more even he doesn't.

However, in most cases where physical goods are involved shipping is a concern. Assuming that all the buyers are relatively the same distance/cost away from the fulfillment center, the next logical optimization is to minimize the shipping destinations. In this case that often means choosing the smallest set, (501, 1001), only two shipping destinations. The pallet is shipped to a fulfillment center, the pallet is broken down by a 3rd party fulfillment service, and two shipments are sent out.

This is a simple example. A real example could have computed a whole set of costs for each set, shipping, fees, even probability of rejection at the destination, for instance, for damage, based on previous deliveries to that buyer or region. Some algorithms may not consider the smallest set optimal because it put too many eggs in each delivery basket in case of a rejection or payment problem. If two bids are exactly the same, but only one can be used, timestamp is usually important, first come, first serve. What is important is that once (or as) the possible combinations are generated each exchange will use a set of arbitrary tests to pick the optimal combination.

So what is the hard computational part? To demonstrate, just take this example and increase the size of offer to 100 @ some price, all-or-nothing, and increase the number of bids to maybe 100 viable bids (over, or at, the ask price) at various sizes, and try crunching that on single node. It can take a while. Without algorithmic optimization, the system will have to generate many combinations and examine each one.

How many combinations will the system have to look at? The number of possible combinations of a system n values is defined as (n! +1). Where "!" indicates a factorial. That is 3! = 1x2x3 and 5! = 1x2x3x4x5. 0! = 1. For us n is 100, because the total number of viable bids is 100. That is 100! + 1 or 9.33262154439441E+157 combinations.

Next: Algorithmic Optimization

What is an N-Way Exchange?

N-Way, M-Way, & Aggregating Exchanges - Slick Technology with the Ability to Dramatically Increase Market Efficiency

N-way, multi-way (m-way), and aggregating exchanges are exchanges where there is a one-to-many, many-to-one, or many-to-many relationship between the counterparties on both sides of the transaction. This is in contrast to simple exchanges like e-Bay, where transactions are one-to-one, one seller, one buyer. The term "aggregating exchanges" is often used because these exchanges aggregate the buying and/or selling intent of multiple parties on each side of the transaction.

Sellers typically use n-way exchanges to sell large lots of products to multiple buyers who would be unable to buy the lots themselves individually, and to do so in a cost effective manner. For instance, a large seller, with 100,000 tons of recycled Aluminum may not be able to find a large enough buyer who can make a single buy. An n-way exchange can be an efficient way to sell in smaller lots. Buyers post their interest, this may include delivery, quality, and scheduling parameters as well pricing. The seller inputs his own criterion which will probably also include minimum purchase size and pricing so he's not hit with more small purchases than he can handle efficiently or opportunistic buy attempts. The exchange aggregates buy interest with compatible criterion on the sell side and creates a binding optimal transaction. For instance, higher price per ton and bigger lot sizes might be fulfilled first regardless of the order of input. The deals are sealed; product is shipped and payments are processed.

Buyers often use n-way exchanges to get better terms. Sellers are often willing to lower pricing on volume buys. Buyers essentially collude, without necessarily knowing each other or making specific arrangements, to get better pricing. This is often amenable to Sellers because of the higher total volumes transacted (the cost of the sale is reduced).

It's important to note that n some exchanges buyers have more power to set terms and on some exchanges sellers have that power. Who has more power on an exchange? Generally it depends on who built or owns the exchange, since they set the ground rules, and on the ratio of supply to demand. If supply is very high relative to demand (and not all from the same place), the buyers typically have an advantage. If supply is low relative to demand, then sellers have an advantage. Exchanges with high multi-channel supply and high multi-party demand are considered efficient because the exchange drives up efficiency and volume and drives down pricing. Exchanges therefore do not typically upset the balance of power in a mature industry (unless players are excluded or decline to join) but they do make the transactions more efficient.

Truly neutral exchanges are exchanges where buyers and sellers are on relatively equal footing in terms of ground rules, and the exchange itself has no more interest in one versus the other, are typically built and maintained by third parties. These typically offer a good deal of transparency; that is both sellers and buyers can monitor the state of the exchange in real or near-time, can see buys and sells, watch trends, and see history. Typically, neutral exchanges make their money in things like membership and transaction fees.

Many-to-Many transactions have multiple counterparties on each side of the transaction at completion. Many-to-Many transactions can get very complicated. However, providing there is sufficient compatible supply and demand, they allow the exchange to “jigsaw” together complicated transactions that would not be executable in a one-to-many or many-to-one scenario. Here is an example -

Two sellers (s1 and s2) have the following registered intent – s1: 200 units/min order: 200 units/all or nothing, s2: 100 units/min order: 100 units/a;; or nothing.

Three buyers (b1, b2, and b3) have the following registered intent – b1: 100 units, b2: 150 units, b3: 50 units.

Notice, the totals are compatible - 300 to sell, 300 to buy - but not the lot sizes. Neither S1 or S2 wish to split their volumes. The pieces do not fit. So, how does the exchange execute this? By providing a fulfillment service in between. The exchange in effect buys the 300 units, takes delivery, breaks the lots up and then ships direct to the buyers itself. There is usually a charge involved, which the buyers and sellers are often happy to pay because it creates a sale where there would be no sale. Why would a seller not break up his own order if the total buy size met his total volume criterion? He might and that could be handled as straight multiple one-to-many and many-to-one transactions, but often the case is that the seller cannot handle small orders or changes to inventory easily. He might not even have any dedicated staff of his own. He might just need to get arriving pallets off a lot or a dock or existing pallets out of storage as fast as possible.

Next: Computational Requirements for an N-Way Exchange

TWING! is going away? I've heard of large scale layoffs at TWING! and that they are "wrapping things up". Too bad; TWING! is good technology, great design and a useful tool, and it was many people's livelihood.

Here is the original post from launch-

TWING, (www.twing.com), a brand spanking new community search, is up in beta. Today is TWING’s first day up and thanks to some well placed “leaking” it’s already being utilized from the outside. Apparently people are finding it useful and/or neat to explore. There have been clicks indicating people added it to their toolbar, which is very promising.

TWING is the product of months of the TWING Team’s hard work. I’m proud to say that LAB09 is that part of that team, having built the Oracle RAC related data architecture from the ground up from functional and performance requirements.

If you are interested, the underlying data platform is Oracle RAC, running on x86 LINUX for the heavy statistical lifting, and MySQL running on same for personalization. The RAC is designed for several billion updates per day. The site is an AJAX & JAVA/SPRING/HIBERNATE/STRUTS application. The crawler architecture is a bit of a secret J.

You can find our case study here:

www.lab09.com/docs/cases/twing.pdf
www.lab09.com/docs/cases/twing.xps

We hope you find TWING as cool to use as we did to build! Enjoy.

You may have seen this already but I think this is a great idea. Time to tell the GPU manufacturers to get another job if they don’t keep price, quality, and RELIABILITY inline. Driver reliability has been a big issue lately, especially at NVIDIA, which purportedly caused over 50% of all automatically reported VISTA lockups in the first few month after VISTA was released. At the current rate of price deflation it may be more price/quality sensible to run a game or CAD system on a system with more cores and less graphics card. At the very least it will easier to update the software if a fix is needed. I wouldn’t be surprised if X-BOX Next comes with Windows 7, allot of cores and little GPU support. That might be better for ray tracing and physics work since most games cap at 3 threads. Any additional CPU cores (especially if they are on different CPUs with different LVL 1 caches) would be available to generate display images. Add additional GPU like CPU commands in the future, like the existing Intel MMX set, the story sounds better and better. 

http://www.custompc.co.uk/news/605271/windows-7-allows-directx-10-acceleration-on-the-cpu.html (lifted from Slashdot)

This is a reprint, but worth repeating.

Data Grids are the way to build highly distributed and scalable applications.

Here's a small piece from Cameron Purdy's Blog on the subject of Data Grids. Cameron was the CEO of Tangosol before it was purchased by Oracle. Tangosol's product is now called Oracle Coherence. This is a pretty good place to start.

During Thomas Kurian's keynote at JavaOne this year, I gave a three-minute demonstration of an application running on a Oracle Coherence data grid, but I didn't have a lot of time to talk about how or why it worked, and more importantly, how or why we are so certain that it is going to work. Recently, I found some notes I had jotted down before the presentation, describing what a data grid is. This is probably the most concise way I've ever found to describe data grid technology:

A data grid allows an application to manage large amounts of live, transactional information in the middle-tier, benefiting from locality of information available at in-memory speed.

Using synchronous replication of information, the data grid achieves both data reliability and continuous availability, and provides consistency through transactions.

A data grid can obtain information from multiple data sources, collecting and transforming that information into the application’s domain object model, which the data grid then manages in that form.

The data grid provides a single, holistic view of the information -- a "single system image" -- to all the servers in the data grid, and out to all of the clients of the data grid.

To take advantage of the horizontal scalability of the grid, the information is automatically and dynamically partitioned across the grid. By reliably partitioning the information, the data grid can search, analyze and process the information in parallel, automatically utilizing the full extent of the grid infrastructure.

For more go to http://www.jroller.com/page/cpurdy