//No Comment - Is Parallel Programming Hard; Column Subset Selection Is NP-complete & The Balance Attack Against Proof-Of-Work Blockchains
Written by Alex Armstrong   
Monday, 16 January 2017

Is Parallel Programming Hard, And, If So, What Can You Do About It?  

Column Subset Selection Is NP-complete

The Balance Attack Against Proof-Of-Work Blockchains: The R3 Testbed as an Example

nocomment

Sometimes the news is reported well enough elsewhere and we have little to add other than to bring it to your attention.

No Comment is a format where we present original source information, lightly edited, so that you can decide if you want to follow it up. 

 

Is Parallel Programming Hard, And, If So, What Can You Do About It?

par

Parallel programming is important. Now and in the future it is the only way we are going to make anything go faster. Every programmer is told that parallel programming is difficult, so difficult that you really should avoid it at all costs.Then there is the little voice inside of most of us which says "go on, it can't be that hard". Before you give in you probably should read this survey:

The purpose of this book is to help you program shared-memory parallel machines without risking your sanity. We hope that this book's design principles will help you avoid at least some parallel-programming pitfalls. That said, you should think of this book as a foundation on which to build, rather than as a completed cathedral.

Your mission, if you choose to accept, is to help make further progress in the exciting field of parallel programming--progress that will in time render this book obsolete. Parallel programming is not as hard as some say, and we hope that this book makes your parallel-programming projects easier and more fun. 

In short, where parallel programming once focused on science, research, and grand-challenge projects, it is quickly becoming an engineering discipline. We therefore examine specific parallel-programming tasks and describe how to approach them. In some surprisingly common cases, they can even be automated. 

This book is written in the hope that presenting the engineering discipline underlying successful parallel-programming projects will free a new generation of parallel hackers from the need to slowly and painstakingly reinvent old wheels, enabling them to instead focus their energy and creativity on new frontiers. We sincerely hope that parallel programming brings you at least as much fun, excitement, and challenge that it has brought to us!

 

Column subset selection is NP-complete

The problem of selecting a sub matrix S of a a given matrix M which optimizes the approximation AS of M is important in many practical applications. Put another way, how close can a matrix get to a space spanned by just k of its columns.

If you fix S then A that optimizes the approximation is easily worked out, but how hard is it to find an optimal sub-matrix. About as hard as it gets, it seems:

Let M be a real r×c matrix and let k be a positive integer. In the column subset selection problem (CSSP), we need to minimize the quantity ∥M−SA∥, where can be an arbitrary k×c matrix, and S runs over all r×k submatrices of M.

This problem and its applications in numerical linear algebra are being discussed for several decades, but its algorithmic complexity remained an open issue. We show that CSSP is NP-complete.


What is more the paper proves that for rational matrices the problem is NP-complete.  

nocomment

The Balance Attack Against Proof-Of-Work Blockchains: The R3 Testbed as an Example

The blockchain is a great hope for the future of many application that would otherwise require a central trusted authority, but this only works if you can trust the blockchain. This makes research into security and attacks on the blockchain very important:

In this paper, we identify a new form of attack, called the Balance attack, against proof-of-work blockchain systems. The novelty of this attack consists of delaying network communications between multiple subgroups of nodes with balanced mining power.

Our theoretical analysis captures the precise tradeoff between the network delay and the mining power of the attacker needed to double spend in Ethereum with high probability. 

We quantify our probabilistic analysis with statistics taken from the R3 consortium, and show that a single machine needs 20 minutes to attack the consortium. Finally, we run an Ethereum private chain in a distributed system with similar settings as R3 to demonstrate the feasibility of the approach, and discuss the application of the Balance attack to Bitcoin.

Our results clearly confirm that main proof-of-work blockchain protocols can be badly suited for consortium blockchains.

nocomment

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter,subscribe to the RSS feed and follow us on, Twitter, FacebookGoogle+ or Linkedin.

Banner

nocommentTheory


Amazon Adds AWS Lambda Code Editing Tool
04/11/2024

Amazon has added a new code editing option for AWS Lambda in the AWS console based on the Code-OSS, Visual Studio Code Open Source code editor.



Zitadel Announces Funding And Future Plans
21/11/2024

Zitadel has announced a major funding round that will be used to expand technical teams and fund further product development. The company is the creator of an open source project for cloud-native iden [ ... ]


More News

espbook

 

Comments




or email your comment to: comments@i-programmer.info

 

Last Updated ( Tuesday, 25 September 2018 )