How does FDS (flat datacenter storage) make optimizations around locality unnecessary?
The paper you cited is exploring the consequences of the question "what if datacenter network bandwidth was free?"  There are two reasons you might care about data locality.  One is latency and the other is bandwidth.  The workloads they are looking at (mostly) don't care about latency, and they've made bandwidth irrelevant, hence locality doesn't matter.  (Note however that at the end of Section 6.2 (on Page 12) they discuss how the inefficiency of non-local accesses forced them to use more compute nodes for their sorting algorithm.)

They also aren't completely eliminating locality optimizations.  Each compute node is still caching/buffering reads and writes in its local DRAM.  The rule of "avoid unnecessary I/O" still stands.  It's just that you don't make a distinction when you do a disk access of whether the disk is near or far from your compute node.  All disk accesses are assumed to include the extra latency of a round-trip network traversal.

Here's a picture to show the difference. The authors' "flat" storage model is on the left, the traditional "distributed" storage model is on the right:



In the distributed model (on the right) data is either on a local disk or a remote disk.  In the flat model (on the left) data is all remote.  But since the network bandwidth is (effectively) infinite, this doesn't reduce your maximum data bandwidth.