Optimizing Mathematical Programs using Peer-to-Peer Networks

Description and application

Would you like to harness the exponential computational power of peer-to-peer (P2P) networks to solve demanding mathematical optimization problems, but are concerned about security? This innovation delivers the speed and scalability of P2P networks while not disseminating any executable files. It also disguises all processes from participants. It harnesses the computational power of P2P networks to process Integer Linear Programs (ILPs).

ILPs are complex mathematical programs that can be solved with branch-and-bound and branch-and-cut algorithms. Known for their capacity to solve a wide variety of algorithmic problems, including extremely demanding NP-complete (intractable) problems, ILP solvers require enormous amounts of runtime. In current parallel processing networks complete processes are exchanged. This puts users at risk of exposing private data. 

However, in the present model processes are broken down into abstract sub-problems with scrambled decision variables and constraints before they are disseminated through the peer network. Peers join the network by installing a simple application, and are able to earn, use, buy, and sell credit for their computer’s processing time. Peers distinguish between friends, who are provided access free-of-charge, and business partners, who require extra fraud protection and for which all exchanges result in financial reimbursement. Participants are monitored and any malicious users are banned. In addition, less-than-optimal performance is penalized in the form of diminished earning power, while excellent performance is rewarded with a raise.

Potential applications

  • Commercialize the exchange of computational processing power over the internet
  • Useful for train or airplane scheduling, production plans, telecommunications, VLSI design, or any algorithmic problem which ILPs can solve
  • Has the potential to utilize the idle time of any computer on the Internet

Printable PDF

Reference

8810-7219

Inventors

Pin-Han Ho
Janos Tapolcai

Patent status

Issued U.S. patents 8,589,490 and 8,527,590

Canadian 2,618,180 application pending

Stage of development

Presently a beta test has been designed and is running that demonstrates this novel P2P computational method

Contact

Scott Inwood
Director of Commercialization
Waterloo Commercialization Office
519-888-4567, ext. 33728
sinwood@uwaterloo.ca
uwaterloo.ca/research