Profile

Cover photo
David Andersen
Works at Carnegie Mellon University
Attended Massachusetts Institute of Technology
Lives in Pittsburgh, PA
2,100 followers|1,031,745 views
AboutPostsPhotosYouTubeReviews

Stream

David Andersen

Shared publicly  - 
 
What an inspired choice!  Though I'm sorry there aren't two of him for us to share, Google-Pittsburgh-friends.
17
2
Toby Smith's profile photoRandy Tobias's profile photogeorge oloo's profile photoPat Gunn's profile photo
4 comments
 
+David Andersen Too bad there aren't two: the Moore the merrier. We'll miss you, Andrew!
Add a comment...

David Andersen

Shared publicly  - 
 
Go has corrupted me.  I wanted to parallelize something in a more fine-grained way in C++.  I didn't want to bring in C++11-ish stuff, so I wrote a channel class first.

Which made the whole exercise a lot more fun. :-)

#golang  
13
1
Gu Yifan's profile photoDavid Andersen's profile photoBryan Mills's profile photoPat Gunn's profile photo
5 comments
 
+Bryan Mills - I concur.  The problems are the usual ugliness - I'm trying to make sure I can still cross-compile the binary for Windows using mingw.  The version of mingw that installs out of the box for Ubuntu uses gcc version 4.6.3.

Beyond that, using some things like std::mutex was causing problems when I tried to do a statically linked build for other Linux platforms.  I'm sure I could solve it with the right linker magic, but it was easy enough to just have some ugly pthread_* calls in the 68 lines of the queue/channel implementation, and then not worry about it.
Add a comment...

David Andersen

commented on a post on Blogger.
Shared publicly  - 
 
As a brief followup - I implemented a very quick and dirty proof-of-concept of this.  For 2^25 nodes (2^24 edges), it uses 2^26 + 2^25 bits of memory to reduce the problem down to 10,000 remaining nodes in about 5.5 seconds.  It's not very optimized.  That's about 12MB, compared to the 128MB needed by the authors' original implementation, and takes only twice as long.  It could probably be sped up considerably.  It can also run comfortably in 2^25 bits (6MB) of memory, but it takes 15 seconds.  The latter is that O(N).  Running in 1/2N would take about 4x longer.

The more I think about it, the more I'm nervous about the sampling approach.

At this point, I conclude that I would not use this PoW in a cryptocurrency until more time has passed and it's been subject to much more intense review.
2
Add a comment...

David Andersen

Shared publicly  - 
 
I've been doing a little bit more crypto miner engineering on Riecoin, a prime finding crypto-currency.  Here's my promised post (part #1 of 2) explaining some of the algorithmic basis for speeding up such a miner.  It's basic sieve stuff extended to k-tuples.  Well known among people who are interested in finding big prime numbers, but it was fun to get into it.  Part #2 will be about extending these ideas upwards into 1600-bit integers.

This coincides with open sourcing my miner code, and the Python examples in this blog post, at https://github.com/dave-andersen/fastrie  

As you can see from the latest graph, the releases have had a bit of an effect on mining this currency. :)
10
1
Narendra Bharathi's profile photo
Add a comment...
 
Writing fast prime sieves is fun.  In the screenshot below, user 'ric1' is using my Riecoin miner as a test on a lot of Amazon instances for a few hours.  The interesting thing hiding in there are the gaps in the sequence number space -- that's where the real competition is:  blocks 21135, 21136, 21138, and 21148 were found by other advanced miner developers running their miners solo, despite this somewhat insane experiment.  (N.b. - I'm not 'ric1').

But it's interesting that a young cryptocurrency could actually be controlled by one person with the help from Amazon.  Fortunately, we're doing this for fun, not evil, and I'll be releasing the code to the fast miner once the pool fairness issues are worked out.  And we haven't even tried any of +Emin Gün Sirer 's and Ittay Eyal's selfish tricks. :p

#bitcoin   #riecoin  
5
Add a comment...
Have him in circles
2,100 people
John Byers's profile photo
Patrick Wendell's profile photo

David Andersen

Shared publicly  - 
 
Code release and paper available for +Hyeontaek Lim , +Dongsu Han , +Michael Kaminsky and my super-fast bare metal key-value store, MICA, just presented at NSDI:

Code linked below, released on github,
Paper here:  http://www.cs.cmu.edu/~hl/papers/mica-nsdi2014.pdf

We're looking for practical-ish applications and uses.  Prototype has some limitations and hardcoded stuff, but should be usable (and we're happy to help improve it if people are actually interested in using it).

Congrats, +Hyeontaek Lim, on another fun paper!
11
2
Mykola Aleshchanov's profile photoEric Casteleijn's profile photo
Add a comment...

David Andersen

Shared publicly  - 
 
It's disappointing - and somewhat scary - to see a company that's entrusted with financial responsibility and access to users' bank accounts respond to an actual security problem in such a head-in-the-sand way.  I've flushed out my (small) holding of bitcoin on coinbase, as a start.

+Coinbase, you're wrong:  It's not about the spam, it's phishing, and it's possibly one of the most serious threats that your users will face as they become increasingly "normal" people.  Providing an easy way for an attacker to find the real name associated with a coinbase-using email address lowers the bar and will expose your users to more such activity.
2
Wolfgang Richter's profile photo
 
And +David Andersen we have another example with Heartbleed: http://blog.coinbase.com/post/82166525514/heartbleed-and-coinbase

They just link to Cloudflare's article which says it was fixed last week, but don't seem to care that this exploit was in place for quite a long time (years?)?

I'd be more concerned now with people presenting certs pretending to be Coinbase to unsuspecting users; users who's software/web browser might not even check revocations by default :-(
Add a comment...

David Andersen

Shared publicly  - 
 
Analyzing the asymptotic complexity of this is a little out of my league, but I've taken a first cut at picking on a new proposed proof-of-work called Cuckoo Cycle.  I think there's more that can be done to reduce its complexity - my personal reaction is that I'd avoid it until someone manages a more firm proof of hardness, but I'm conservative and boring.  Comments welcome - this is very much a work-in-progress, and I'm definitely not a complexity theorist!  Warning:  This is not the most polished of my posts - I'm kind of dumping big-ohs on paper and thinking in realtime.
1
1
Benoit Hudson's profile photoRasmus Pagh's profile photoDavid Andersen's profile photo
4 comments
 
+Rasmus Pagh -  I concur.  I'm not convinced that this one isn't actually worse than a straightforward partial hash collision.  The scheme that implements that is called Momentum - http://www.hashcash.org/papers/momentum.pdf - and while it initially had some overstated claims about GPU / ASIC resistance, it does require more memory/memory bandwidth than most other schemes in relation to the amount of processing it does.  Its biggest drawback was the choice of SHA512 as the way to generate the random data, because in practical implementations, SHA is the bottleneck, not the rest of the system.  I like the use of SipHash in 'cuckoo cycle' as a way to further reduce the CPU consumption.  k-sum might present a really interesting basis for a PoW, though.  Hadn't thought about that one.
Add a comment...

David Andersen

Shared publicly  - 
 
Go go distributed systems turing awards. :)  And many well-deserved congratulations to Lamport.  I'm teaching Paxos in my class today -- what a great way to be able to introduce it!
33
6
Úlfar Erlingsson's profile photojinyang li's profile photo
Add a comment...

David Andersen

Shared publicly  - 
 
Ok, now I get the seductive appeal of cloud computing.  I noticed some latency spikes on the pi searcher.  Normally, that would send me scrambling to improve the code.  But today, I just... clicked.  Twice.  And now the Pi searcher is backed by 3 c3.large AWS instances (plus its usual m1.small).  Internal response time (not counting network latency) is back under 10ms.  And now I'm paying Amazon $0.45/hour.  Only thing I had to tweak was setting GOMAXPROCS=2 to be able to use the extra core.

Zowie, that's cool.  Though I hope it doesn't make me forget that it's always nice to have high-performance code so I don't have to use as many resources. :)

Happy #piday  , all!
14
1
Narendra Bharathi's profile photoTodd Underwood's profile photoDavid Andersen's profile photo
2 comments
 
It's great - you wouldn't believe how many of these servers I can stuff in a car!

... now I'm up to 10 cores on aws.  can't stop!  drunk with scaling!
Add a comment...
People
Have him in circles
2,100 people
John Byers's profile photo
Patrick Wendell's profile photo
Work
Occupation
Computer Science Professor
Employment
  • Carnegie Mellon University
    Computer Science Professor, present
    Warping the minds of tomorrow's awesome engineers, researchers, and teachers.
Places
Map of the places this user has livedMap of the places this user has livedMap of the places this user has lived
Currently
Pittsburgh, PA
Previously
Salt Lake City, UT - Boston, MA
Contact Information
Work
Phone
412-268-3064
Email
Story
Tagline
Computer science professor at Carnegie Mellon University
Introduction
Associate Professor of Computer Science at Carnegie Mellon University.  Geek, runner, sometimes climber, avid mostly-vegan cook.
Education
  • Massachusetts Institute of Technology
    Computer Science, 1999 - 2005
  • University of Utah
    Computer Science, Biology, 1993 - 1998
Basic Information
Gender
Male
Other names
Dave
Emailed near Christmas on the off chance that a local store would have a video card hanging around. Steven responded promptly and had a used one at a good price that exactly met my needs. Worked as promised. I'm happy.
Public - 3 months ago
reviewed 3 months ago
1 review
Map
Map
Map