Profile

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

Stream

David Andersen

Shared publicly  - 
 
+Wyatt Lloyd strikes again with a reader-friendly summary of his/our COPS and EIGER work on providing causal consistency in low-latency wide-area replicated key value storage systems.
5
3
Alexander Gallego's profile photogeorge oloo's profile photo
Add a comment...

David Andersen

Shared publicly  - 
 
Behind USENIX paywall for now (I assume half of the people who read this post are members or have institutional access), but +Todd Underwood 's opening paragraphs on "The Death of System Administration" are the most amazing trip down memory lane ever for anyone involved in mid-to-late-90s ISP/systems administration.  Thanks for capturing it so perfectly -- and good riddance!
3
Mark Foltz's profile photoTodd Underwood's profile photoDavid Andersen's profile photo
3 comments
 
+Mark Foltz - "I haven't read the article, but" -- shouldn't such sentences usually have a period after "article"?  *grins*  It's a standard 2014 linkbait title with good content underneath it about the future we should be moving towards in terms of near-zero-management systems, using the Google SRE system as a midpoint example (compared to the standard sysadmin practice of a decade ago) towards reaching that future.
Add a comment...

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...
Have him in circles
2,110 people
David Gay's profile photo
Stephanie Federwisch's profile photo
Christos Faloutsos's profile photo

David Andersen

Shared publicly  - 
 
Random ethics question of the day:  When studying a proof-of-work function proposed for use in a cryptocurrency, a researcher finds a way to solve it faster and using less memory than its authors believe possible.  Say, 4x.

Hypothetically speaking, of course.  grin.

(a)  Make the information public (or to the authors) before the system goes live.
(b)  Write a probably-destined-for-arxiv paper about it that may or may not be published before the system goes live.
(c)  Mine like crazy using a 4x competitive advantage over the rest of the participants in the system until getting bored of it, and then mention it publicly.

If this were a classic security vulnerability that left systems exposed to compromise, the ethical path of responsible disclosure is clear.  But with a proof-of-work function and a mere numerical / efficiency advantage -- is there an ethical problem with (c) vs (a) or (b)?
2
Brian Demsky's profile photoGlenn Willen's profile photoDavid Crawshaw's profile photoDavid Andersen's profile photo
11 comments
 
I vote for option (c).  Mainly because large scale adoption of crypto currency systems would be pretty carbon unfriendly...
Add a comment...

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...
People
Have him in circles
2,110 people
David Gay's profile photo
Stephanie Federwisch's profile photo
Christos Faloutsos'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