diff --git a/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/NativeScanHandler.java b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/NativeScanHandler.java
new file mode 100644
index 0000000..c1b62da
--- /dev/null
+++ b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/NativeScanHandler.java
@@ -0,0 +1,38 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.android.impl.google.discovery.plugins;
+
+import io.v.x.ref.lib.discovery.AdInfo;
+
+import io.v.impl.google.lib.discovery.Plugin;
+
+/**
+ * An implementation of the {@link Plugin.ScanHandler} for use by the discovery framework.
+ * <p>
+ * This handler is used to pass results from a Java plugin to the Go wrapper to passed
+ * on to the discovery instance.
+ */
+class NativeScanHandler implements Plugin.ScanHandler {
+    // A pointer to the the native channel.
+    private final long nativeChan;
+
+    private NativeScanHandler(long nativeChan) {
+        this.nativeChan = nativeChan;
+    }
+
+    private native void nativeHandleUpdate(long chan, AdInfo adinfo);
+
+    private native void nativeFinalize(long chan);
+
+    @Override
+    public void handleUpdate(AdInfo adinfo) {
+        nativeHandleUpdate(nativeChan, adinfo);
+    }
+
+    @Override
+    protected void finalize() throws Throwable {
+        nativeFinalize(nativeChan);
+    }
+}
diff --git a/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/BlePlugin.java b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/BlePlugin.java
new file mode 100644
index 0000000..28b793d
--- /dev/null
+++ b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/BlePlugin.java
@@ -0,0 +1,354 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.android.impl.google.discovery.plugins.ble;
+
+import android.Manifest;
+import android.bluetooth.BluetoothAdapter;
+import android.bluetooth.BluetoothDevice;
+import android.bluetooth.BluetoothGatt;
+import android.bluetooth.BluetoothGattCharacteristic;
+import android.bluetooth.BluetoothGattServer;
+import android.bluetooth.BluetoothGattServerCallback;
+import android.bluetooth.BluetoothGattService;
+import android.bluetooth.BluetoothManager;
+import android.bluetooth.le.AdvertiseCallback;
+import android.bluetooth.le.AdvertiseData;
+import android.bluetooth.le.AdvertiseSettings;
+import android.bluetooth.le.BluetoothLeAdvertiser;
+import android.bluetooth.le.BluetoothLeScanner;
+import android.bluetooth.le.ScanCallback;
+import android.bluetooth.le.ScanFilter;
+import android.bluetooth.le.ScanResult;
+import android.bluetooth.le.ScanRecord;
+import android.bluetooth.le.ScanSettings;
+import android.content.Context;
+import android.content.pm.PackageManager;
+import android.support.v4.content.ContextCompat;
+import android.util.Log;
+
+import com.google.common.collect.ImmutableList;
+
+import java.io.IOException;
+import java.math.BigInteger;
+import java.nio.ByteBuffer;
+import java.security.SecureRandom;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.UUID;
+
+import org.joda.time.Duration;
+
+import io.v.v23.context.VContext;
+import io.v.v23.discovery.AdId;
+
+import io.v.x.ref.lib.discovery.AdInfo;
+
+import io.v.impl.google.lib.discovery.UUIDUtil;
+import io.v.impl.google.lib.discovery.Plugin;
+
+/**
+ * The discovery plugin interface for BLE.
+ */
+public class BlePlugin implements Plugin {
+    private static final String TAG = "BlePlugin";
+
+    // We are using a constant for the MTU because Android and paypal/gatt don't get along
+    // when the paypal gatt client sends a setMTU message.  The Android server seems to send
+    // a malformed L2CAP message.
+    private static final int MTU = 23;
+
+    // Default device cache expiration timeout.
+    private static final Duration defaultCacheDuration = Duration.standardSeconds(90);
+
+    // Random generator for stamp.
+    private final SecureRandom random = new SecureRandom();
+
+    private final Context androidContext;
+
+    // Set of Ble objects that will be interacted with to perform operations.
+    private BluetoothLeAdvertiser bluetoothLeAdvertise;
+    private BluetoothLeScanner bluetoothLeScanner;
+    private BluetoothGattServer bluetoothGattServer;
+
+    private Map<AdId, BluetoothGattService> advertisements;
+    private AdvertiseCallback advertiseCallback;
+
+    private Set<Plugin.ScanHandler> scanners;
+    private Set<String> pendingConnections;
+    private DeviceCache deviceCache;
+    private ScanCallback scanCallback;
+
+    // If isEnabled is false, then all operations on the ble plugin are no-oped. This will only
+    // be false if the ble hardware is inaccessible.
+    private boolean isEnabled = false;
+
+    private boolean hasPermission(String perm) {
+        return ContextCompat.checkSelfPermission(androidContext, perm)
+                == PackageManager.PERMISSION_GRANTED;
+    }
+
+    public BlePlugin(String host, Context androidContext) {
+        this.androidContext = androidContext;
+        BluetoothAdapter bluetoothAdapter = BluetoothAdapter.getDefaultAdapter();
+        if (bluetoothAdapter == null || !bluetoothAdapter.isEnabled()) {
+            return;
+        }
+        if (!hasPermission(Manifest.permission.ACCESS_COARSE_LOCATION)
+                && !hasPermission(Manifest.permission.ACCESS_FINE_LOCATION)) {
+            return;
+        }
+
+        bluetoothLeAdvertise = bluetoothAdapter.getBluetoothLeAdvertiser();
+        bluetoothLeScanner = bluetoothAdapter.getBluetoothLeScanner();
+        BluetoothManager manager =
+                (BluetoothManager) androidContext.getSystemService(Context.BLUETOOTH_SERVICE);
+        bluetoothGattServer =
+                manager.openGattServer(
+                        androidContext,
+                        new BluetoothGattServerCallback() {
+                            @Override
+                            public void onConnectionStateChange(
+                                    BluetoothDevice device, int status, int newState) {
+                                super.onConnectionStateChange(device, status, newState);
+                            }
+
+                            @Override
+                            public void onCharacteristicReadRequest(
+                                    BluetoothDevice device,
+                                    int requestId,
+                                    int offset,
+                                    BluetoothGattCharacteristic characteristic) {
+                                super.onCharacteristicReadRequest(
+                                        device, requestId, offset, characteristic);
+                                byte[] total = characteristic.getValue();
+                                byte[] res = {};
+                                // Only send MTU - 1 bytes. The first byte of all packets is the op code.
+                                if (offset < total.length) {
+                                    int finalByte = offset + MTU - 1;
+                                    if (finalByte > total.length) {
+                                        finalByte = total.length;
+                                    }
+                                    res = Arrays.copyOfRange(total, offset, finalByte);
+                                    bluetoothGattServer.sendResponse(
+                                            device, requestId, BluetoothGatt.GATT_SUCCESS, 0, res);
+                                } else {
+                                    // This should probably be an error, but a bug in the paypal/gatt code causes an
+                                    // infinite loop if this returns an error rather than the empty value.
+                                    bluetoothGattServer.sendResponse(
+                                            device, requestId, BluetoothGatt.GATT_SUCCESS, 0, res);
+                                }
+                            }
+                        });
+
+        advertisements = new HashMap<>();
+        scanners = new HashSet<>();
+        pendingConnections = new HashSet<>();
+        deviceCache = new DeviceCache(defaultCacheDuration);
+        isEnabled = true;
+    }
+
+    public void startAdvertising(AdInfo adInfo) throws Exception {
+        if (!isEnabled) {
+            throw new IllegalStateException("BlePlugin not enabled");
+        }
+
+        BluetoothGattService service =
+                new BluetoothGattService(
+                        UUIDUtil.serviceUUID(adInfo.getAd().getInterfaceName()),
+                        BluetoothGattService.SERVICE_TYPE_PRIMARY);
+        for (Map.Entry<UUID, byte[]> entry : ConvertUtil.toGattAttrs(adInfo).entrySet()) {
+            BluetoothGattCharacteristic c =
+                    new BluetoothGattCharacteristic(
+                            entry.getKey(),
+                            BluetoothGattCharacteristic.PROPERTY_READ,
+                            BluetoothGattCharacteristic.PERMISSION_READ);
+            c.setValue(entry.getValue());
+            service.addCharacteristic(c);
+        }
+
+        synchronized (advertisements) {
+            advertisements.put(adInfo.getAd().getId(), service);
+            bluetoothGattServer.addService(service);
+            updateAdvertising();
+        }
+    }
+
+    public void stopAdvertising(AdInfo adInfo) {
+        synchronized (advertisements) {
+            BluetoothGattService service = advertisements.remove(adInfo.getAd().getId());
+            if (service != null) {
+                bluetoothGattServer.removeService(service);
+                updateAdvertising();
+            }
+        }
+    }
+
+    private long genStamp() {
+        // We use 8-byte stamp to reflect the current services of the current device.
+        //
+        // TODO(bjornick): 8-byte random number might not be good enough for
+        // global uniqueness. We might want to consider a better way to generate
+        // stamp like using a unique device id with sequence number.
+        return new BigInteger(64, random).longValue();
+    }
+
+    private void updateAdvertising() {
+        if (advertiseCallback != null) {
+            bluetoothLeAdvertise.stopAdvertising(advertiseCallback);
+            advertiseCallback = null;
+        }
+        if (advertisements.size() == 0) {
+            return;
+        }
+
+        AdvertiseData.Builder builder = new AdvertiseData.Builder();
+        ByteBuffer buf = ByteBuffer.allocate(9);
+        buf.put((byte) 8);
+        buf.putLong(genStamp());
+        builder.addManufacturerData(1001, buf.array());
+        AdvertiseSettings.Builder settingsBuilder = new AdvertiseSettings.Builder();
+        settingsBuilder.setAdvertiseMode(AdvertiseSettings.ADVERTISE_MODE_LOW_LATENCY);
+        settingsBuilder.setConnectable(true);
+        advertiseCallback =
+                new AdvertiseCallback() {
+                    @Override
+                    public void onStartSuccess(AdvertiseSettings settingsInEffect) {
+                        Log.d(TAG, "started " + settingsInEffect);
+                    }
+
+                    @Override
+                    public void onStartFailure(int errorCode) {
+                        Log.e(TAG, "failed to start advertising " + errorCode);
+                    }
+                };
+        bluetoothLeAdvertise.startAdvertising(
+                settingsBuilder.build(), builder.build(), advertiseCallback);
+    }
+
+    public void startScan(String interfaceName, Plugin.ScanHandler handler) throws Exception {
+        if (!isEnabled) {
+            throw new IllegalStateException("BlePlugin not enabled");
+        }
+
+        synchronized (scanners) {
+            if (!scanners.add(handler)) {
+                throw new IllegalArgumentException("handler already registered");
+            }
+            deviceCache.addScanner(interfaceName, handler);
+            updateScan();
+        }
+    }
+
+    public void stopScan(Plugin.ScanHandler handler) {
+        synchronized (scanners) {
+            if (!scanners.remove(handler)) {
+                return;
+            }
+            deviceCache.removeScanner(handler);
+            updateScan();
+        }
+    }
+
+    private void updateScan() {
+        // TODO(jhahn): Verify whether we need to stop scanning while connect to remote GATT servers.
+        if (scanners.isEmpty()) {
+            if (pendingConnections.isEmpty()) {
+                bluetoothLeScanner.stopScan(scanCallback);
+                scanCallback = null;
+            }
+            return;
+        }
+        if (scanCallback != null) {
+            return;
+        }
+
+        final List<ScanFilter> scanFilters =
+                ImmutableList.of(
+                        new ScanFilter.Builder()
+                                .setManufacturerData(1001, new byte[0], new byte[0])
+                                .build());
+        final ScanSettings scanSettings =
+                new ScanSettings.Builder()
+                        .setCallbackType(ScanSettings.CALLBACK_TYPE_ALL_MATCHES)
+                        .setScanMode(ScanSettings.SCAN_MODE_BALANCED)
+                        .build();
+        scanCallback =
+                new ScanCallback() {
+                    @Override
+                    public void onScanResult(int callbackType, ScanResult result) {
+                        ScanRecord record = result.getScanRecord();
+                        // Use 1001 to denote that this is a Vanadium device.  We picked an id that is
+                        // currently not in use.
+                        byte[] data = record.getManufacturerSpecificData(1001);
+                        ByteBuffer buffer = ByteBuffer.wrap(data);
+                        final long stamp = buffer.getLong();
+                        final String deviceId = result.getDevice().getAddress();
+                        if (deviceCache.haveSeenStamp(stamp, deviceId)) {
+                            return;
+                        }
+
+                        BluetoothGattReader.Handler handler =
+                                new BluetoothGattReader.Handler() {
+                                    @Override
+                                    public void handle(Map<UUID, Map<UUID, byte[]>> services) {
+                                        if (services != null) {
+                                            List<AdInfo> adInfos = new ArrayList<>();
+                                            for (Map.Entry<UUID, Map<UUID, byte[]>> entry :
+                                                    services.entrySet()) {
+                                                try {
+                                                    AdInfo adInfo =
+                                                            ConvertUtil.toAdInfo(entry.getValue());
+                                                    adInfos.add(adInfo);
+                                                } catch (IOException e) {
+                                                    Log.e(
+                                                            TAG,
+                                                            "failed to convert advertisement" + e);
+                                                }
+                                            }
+                                            deviceCache.saveDevice(stamp, deviceId, adInfos);
+                                        }
+                                        synchronized (scanners) {
+                                            pendingConnections.remove(deviceId);
+                                            if (pendingConnections.isEmpty()) {
+                                                if (scanners.isEmpty()) {
+                                                    scanCallback = null;
+                                                    return;
+                                                }
+                                                bluetoothLeScanner.startScan(
+                                                        scanFilters, scanSettings, scanCallback);
+                                            }
+                                        }
+                                    }
+                                };
+                        BluetoothGattReader cb = new BluetoothGattReader(handler);
+                        synchronized (scanners) {
+                            if (scanners.isEmpty()) {
+                                return;
+                            }
+                            if (!pendingConnections.add(deviceId)) {
+                                return;
+                            }
+                            if (pendingConnections.size() == 1) {
+                                bluetoothLeScanner.stopScan(scanCallback);
+                            }
+                        }
+                        Log.d(TAG, "connecting to " + result.getDevice());
+                        result.getDevice().connectGatt(androidContext, false, cb);
+                    }
+
+                    @Override
+                    public void onBatchScanResults(List<ScanResult> results) {}
+
+                    @Override
+                    public void onScanFailed(int errorCode) {}
+                };
+        bluetoothLeScanner.startScan(scanFilters, scanSettings, scanCallback);
+    }
+}
diff --git a/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/BluetoothGattReader.java b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/BluetoothGattReader.java
new file mode 100644
index 0000000..b73a8a2
--- /dev/null
+++ b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/BluetoothGattReader.java
@@ -0,0 +1,113 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.android.impl.google.discovery.plugins.ble;
+
+import android.bluetooth.BluetoothGatt;
+import android.bluetooth.BluetoothGattCallback;
+import android.bluetooth.BluetoothGattCharacteristic;
+import android.bluetooth.BluetoothGattService;
+import android.util.Log;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Hashtable;
+import java.util.List;
+import java.util.Map;
+import java.util.UUID;
+
+/**
+ * A handler for responses from a GattServer.
+ */
+class BluetoothGattReader extends BluetoothGattCallback {
+    private static final String TAG = "BluetoothGattClientCallback";
+
+    // A handler that will get called when all the services from a GATT service are read.
+    interface Handler {
+        /**
+         * Called with the map of service ids to their attributes.
+         *
+         * @param services A map from service id to (characteristics uuid to values).
+         */
+        void handle(Map<UUID, Map<UUID, byte[]>> services);
+    }
+
+    // We want to ignore the GATT and GAP services, which are 1800 and 1801 respectively.
+    static final String GATT_AND_GAP_PREFIX = "0000180";
+
+    private final Handler handler;
+    private final Map<UUID, Map<UUID, byte[]>> services = new HashMap<>();
+
+    private BluetoothGatt gatt;
+
+    private final List<BluetoothGattCharacteristic> characteristics = new ArrayList<>();
+    private int characteristicsIndex;
+
+    BluetoothGattReader(Handler handler) {
+        this.handler = handler;
+    }
+
+    @Override
+    public void onServicesDiscovered(BluetoothGatt gatt, int status) {
+        for (BluetoothGattService service : gatt.getServices()) {
+            Log.d(TAG, "found service" + service.getUuid().toString());
+            // Skip the GATT AND GAP Services.
+            if (service.getUuid().toString().startsWith(GATT_AND_GAP_PREFIX)) {
+                continue;
+            }
+
+            services.put(service.getUuid(), new HashMap<UUID, byte[]>());
+            // We only keep track of the characteristics that can be read.
+            for (BluetoothGattCharacteristic c : service.getCharacteristics()) {
+                if ((c.getProperties() & BluetoothGattCharacteristic.PROPERTY_READ) != 0) {
+                    characteristics.add(c);
+                } else {
+                    Log.d(TAG, "skipping non read property");
+                }
+            }
+        }
+        characteristicsIndex = 0;
+        maybeReadNextCharacteristic();
+    }
+
+    // Reads the next characteristic if there is one. Otherwise calls handler and
+    // closes the GATT connection.
+    private void maybeReadNextCharacteristic() {
+        if (characteristicsIndex >= characteristics.size()) {
+            gatt.disconnect();
+            gatt.close();
+            handler.handle(services);
+            return;
+        }
+        BluetoothGattCharacteristic c = characteristics.get(characteristicsIndex++);
+        if (!gatt.readCharacteristic(c)) {
+            Log.w(TAG, "failed to read characteristic " + c.getUuid());
+            maybeReadNextCharacteristic();
+        }
+    }
+
+    @Override
+    public void onCharacteristicRead(
+            BluetoothGatt gatt, BluetoothGattCharacteristic c, int status) {
+        UUID serviceUuid = c.getService().getUuid();
+        Log.d(TAG, "got characteristic [" + serviceUuid + "]" + c.getUuid() + "=" + c.getValue());
+
+        services.get(serviceUuid).put(c.getUuid(), c.getValue());
+        maybeReadNextCharacteristic();
+    }
+
+    @Override
+    public void onConnectionStateChange(BluetoothGatt gatt, int status, int newState) {
+        Log.d(TAG, "new connections state is " + newState);
+
+        this.gatt = gatt;
+        if (status != BluetoothGatt.GATT_SUCCESS || newState != BluetoothGatt.STATE_CONNECTED) {
+            Log.w(TAG, "failed to connect with status " + status + " state" + newState);
+            gatt.close();
+            handler.handle(null);
+            return;
+        }
+        gatt.discoverServices();
+    }
+}
diff --git a/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/ConvertUtil.java b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/ConvertUtil.java
new file mode 100644
index 0000000..5ba958b
--- /dev/null
+++ b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/ConvertUtil.java
@@ -0,0 +1,144 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.android.impl.google.discovery.plugins.ble;
+
+import com.google.common.primitives.Bytes;
+
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.nio.charset.Charset;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.UUID;
+import java.util.logging.Logger;
+
+import io.v.v23.discovery.Advertisement;
+import io.v.v23.discovery.AdId;
+
+import io.v.x.ref.lib.discovery.AdInfo;
+import io.v.x.ref.lib.discovery.AdHash;
+import io.v.x.ref.lib.discovery.EncryptionAlgorithm;
+import io.v.x.ref.lib.discovery.EncryptionKey;
+import io.v.x.ref.lib.discovery.plugins.ble.Constants;
+
+import io.v.impl.google.lib.discovery.EncodingUtil;
+import io.v.impl.google.lib.discovery.UUIDUtil;
+
+/**
+ * Converts from {@link AdInfo} to GATT characteristics and vice-versa.
+ */
+class ConvertUtil {
+    private static final Logger logger = Logger.getLogger(ConvertUtil.class.getName());
+
+    // We use "ISO8859-1" to preserve data in a string without any interpretation.
+    private static final Charset ENC = Charset.forName("ISO8859-1");
+
+    private static final UUID UUID_ID = UUID.fromString(Constants.ID_UUID);
+    private static final UUID UUID_INTERFACE_NAME = UUID.fromString(Constants.INTERFACE_NAME_UUID);
+    private static final UUID UUID_ADDRESSES = UUID.fromString(Constants.ADDRESSES_UUID);
+    private static final UUID UUID_ENCRYPTION = UUID.fromString(Constants.ENCRYPTION_UUID);
+    private static final UUID UUID_HASH = UUID.fromString(Constants.HASH_UUID);
+    private static final UUID UUID_DIR_ADDRS = UUID.fromString(Constants.DIR_ADDRS_UUID);
+
+    /**
+     * Converts from {@link AdInfo} to GATT characteristics.
+     *
+     * @param adinfo        an advertisement information to convert
+     * @return              a map of GATT characteristics corresponding to the {@link adinfo}
+     * @throws IOException  if the advertisement can't be converted
+     */
+    static Map<UUID, byte[]> toGattAttrs(AdInfo adinfo) throws IOException {
+        Map<UUID, byte[]> gatt = new HashMap<>();
+        Advertisement ad = adinfo.getAd();
+        gatt.put(UUID_ID, ad.getId().toPrimitiveArray());
+        gatt.put(UUID_INTERFACE_NAME, ad.getInterfaceName().getBytes(ENC));
+        gatt.put(UUID_ADDRESSES, EncodingUtil.packAddresses(ad.getAddresses()));
+
+        Map<String, String> attributes = ad.getAttributes();
+        if (attributes != null && attributes.size() > 0) {
+            for (Map.Entry<String, String> entry : attributes.entrySet()) {
+                String key = entry.getKey();
+                String data = key + "=" + entry.getValue();
+                gatt.put(UUIDUtil.attributeUUID(key), data.getBytes(ENC));
+            }
+        }
+
+        Map<String, byte[]> attachments = ad.getAttachments();
+        if (attachments != null && attachments.size() > 0) {
+            for (Map.Entry<String, byte[]> entry : attachments.entrySet()) {
+                String key = Constants.ATTACHMENT_NAME_PREFIX + entry.getKey();
+                ByteArrayOutputStream buf = new ByteArrayOutputStream();
+                buf.write(key.getBytes(ENC));
+                buf.write((byte) '=');
+                buf.write(entry.getValue());
+                gatt.put(UUIDUtil.attributeUUID(key), buf.toByteArray());
+            }
+        }
+        if (adinfo.getEncryptionAlgorithm() != io.v.x.ref.lib.discovery.Constants.NO_ENCRYPTION) {
+            gatt.put(
+                    UUID_ENCRYPTION,
+                    EncodingUtil.packEncryptionKeys(
+                            adinfo.getEncryptionAlgorithm(), adinfo.getEncryptionKeys()));
+        }
+        List<String> dirAddrs = adinfo.getDirAddrs();
+        if (dirAddrs != null && !dirAddrs.isEmpty()) {
+            gatt.put(UUID_DIR_ADDRS, EncodingUtil.packAddresses(dirAddrs));
+        }
+        gatt.put(UUID_HASH, adinfo.getHash().toPrimitiveArray());
+        return gatt;
+    }
+
+    /**
+     * Converts from GATT characteristics to {@link AdInfo}.
+     *
+     * @param attrs         a map of GATT characteristics
+     * @return              an advertisement information corresponding to the {@link attrs}
+     * @throws IOException  if the GATT characteristics can't be converted
+     */
+    static AdInfo toAdInfo(Map<UUID, byte[]> attrs) throws IOException {
+        AdInfo adinfo = new AdInfo();
+        Advertisement ad = adinfo.getAd();
+        for (Map.Entry<UUID, byte[]> entry : attrs.entrySet()) {
+            UUID uuid = entry.getKey();
+            byte[] data = entry.getValue();
+
+            if (uuid.equals(UUID_ID)) {
+                ad.setId(new AdId(data));
+            } else if (uuid.equals(UUID_INTERFACE_NAME)) {
+                ad.setInterfaceName(new String(data, ENC));
+            } else if (uuid.equals(UUID_ADDRESSES)) {
+                ad.setAddresses(EncodingUtil.unpackAddresses(data));
+            } else if (uuid.equals(UUID_ENCRYPTION)) {
+                List<EncryptionKey> keys = new ArrayList<>();
+                EncryptionAlgorithm algo = EncodingUtil.unpackEncryptionKeys(data, keys);
+                adinfo.setEncryptionAlgorithm(algo);
+                adinfo.setEncryptionKeys(keys);
+            } else if (uuid.equals(UUID_DIR_ADDRS)) {
+                adinfo.setDirAddrs(EncodingUtil.unpackAddresses(data));
+            } else if (uuid.equals(UUID_HASH)) {
+                adinfo.setHash(new AdHash(data));
+            } else {
+                int index = Bytes.indexOf(data, (byte) '=');
+                if (index < 0) {
+                    logger.severe("Failed to parse data for " + uuid);
+                    continue;
+                }
+                String key = new String(data, 0, index, ENC);
+                if (key.startsWith(Constants.ATTACHMENT_NAME_PREFIX)) {
+                    key = key.substring(Constants.ATTACHMENT_NAME_PREFIX.length());
+                    byte[] value = Arrays.copyOfRange(data, index + 1, data.length);
+                    ad.getAttachments().put(key, value);
+                } else {
+                    String value = new String(data, index + 1, data.length - index - 1, ENC);
+                    ad.getAttributes().put(key, value);
+                }
+            }
+        }
+        return adinfo;
+    }
+}
diff --git a/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/DeviceCache.java b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/DeviceCache.java
new file mode 100644
index 0000000..6e9ab59
--- /dev/null
+++ b/android-lib/src/main/java/io/v/android/impl/google/discovery/plugins/ble/DeviceCache.java
@@ -0,0 +1,254 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.android.impl.google.discovery.plugins.ble;
+
+import com.google.common.base.Equivalence;
+import com.google.common.base.Function;
+import com.google.common.base.Objects;
+import com.google.common.collect.FluentIterable;
+import com.google.common.collect.HashMultimap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.SetMultimap;
+import com.google.common.collect.Sets;
+
+import org.joda.time.Duration;
+import org.joda.time.Instant;
+
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.Executors;
+import java.util.concurrent.ScheduledExecutorService;
+import java.util.concurrent.TimeUnit;
+
+import io.v.x.ref.lib.discovery.AdInfo;
+
+import io.v.impl.google.lib.discovery.Plugin;
+
+/**
+ * A cache of ble devices that were seen recently.
+ * <p>
+ * The current Vanadium BLE protocol requires connecting to the advertiser
+ * to grab the attributes and the addrs. This can be expensive so we only
+ * refetch the data if its stamp changed.
+ */
+class DeviceCache {
+    // Stores an interface name and a {@link Plugin.ScanHandler}.
+    private static class Scanner {
+        private final String interfaceName;
+        private final Plugin.ScanHandler handler;
+
+        private Scanner(String interfaceName, Plugin.ScanHandler handler) {
+            this.interfaceName = interfaceName;
+            this.handler = handler;
+        }
+    }
+
+    // Stores advertisements from a device with a stamp.
+    private static class CacheEntry {
+        private final long stamp;
+        private String deviceId;
+        private Set<Equivalence.Wrapper<AdInfo>> adInfos;
+        private Instant lastSeen;
+
+        private CacheEntry(long stamp, String deviceId, Set<Equivalence.Wrapper<AdInfo>> adInfos) {
+            this.stamp = stamp;
+            this.deviceId = deviceId;
+            this.adInfos = adInfos;
+            this.lastSeen = new Instant();
+        }
+    }
+
+    private static final Equivalence<AdInfo> ADINFO_EQUIVALENCE =
+            new Equivalence<AdInfo>() {
+                @Override
+                protected boolean doEquivalent(AdInfo a, AdInfo b) {
+                    return a.getAd().getId().equals(b.getAd().getId())
+                            && a.getHash().equals(b.getHash());
+                }
+
+                @Override
+                protected int doHash(AdInfo adinfo) {
+                    return Objects.hashCode(adinfo.getAd().getId(), adinfo.getHash());
+                }
+            };
+    private static final Function<AdInfo, Equivalence.Wrapper<AdInfo>> ADINFO_WRAPPER =
+            new Function<AdInfo, Equivalence.Wrapper<AdInfo>>() {
+                @Override
+                public Equivalence.Wrapper<AdInfo> apply(AdInfo adinfo) {
+                    return ADINFO_EQUIVALENCE.wrap(adinfo);
+                }
+            };
+
+    private final Map<Long, CacheEntry> cacheByStamp = new HashMap<>();
+    private final Map<String, CacheEntry> cacheByDeviceId = new HashMap<>();
+
+    private final SetMultimap<String, Equivalence.Wrapper<AdInfo>> adInfosByInterfaceName =
+            HashMultimap.create();
+
+    private final SetMultimap<String, Scanner> scannersByInterfaceName = HashMultimap.create();
+    private final Map<Plugin.ScanHandler, Scanner> scannersByHandler = new HashMap<>();
+
+    private final Duration maxAge;
+    private ScheduledExecutorService timer;
+
+    DeviceCache(Duration maxAge) {
+        this.maxAge = maxAge;
+        this.timer = Executors.newSingleThreadScheduledExecutor();
+        long periodicity = maxAge.getMillis() / 2;
+        timer.scheduleAtFixedRate(
+                new Runnable() {
+                    @Override
+                    public void run() {
+                        removeStaleEntries();
+                    }
+                },
+                periodicity,
+                periodicity,
+                TimeUnit.MILLISECONDS);
+    }
+
+    private void removeStaleEntries() {
+        synchronized (this) {
+            Iterator<Map.Entry<Long, CacheEntry>> it = cacheByStamp.entrySet().iterator();
+            while (it.hasNext()) {
+                CacheEntry entry = it.next().getValue();
+                if (entry.lastSeen.plus(maxAge).isBeforeNow()) {
+                    it.remove();
+                    cacheByDeviceId.remove(entry.deviceId);
+                    for (Equivalence.Wrapper<AdInfo> wrapper : entry.adInfos) {
+                        AdInfo adinfo = wrapper.get();
+                        adInfosByInterfaceName.remove(adinfo.getAd().getInterfaceName(), wrapper);
+                        adinfo.setLost(true);
+                        handleUpdate(adinfo);
+                    }
+                }
+            }
+        }
+    }
+
+    /**
+     * Cleans up the cache's state and shutdowns the eviction thread.
+     */
+    void shutdownCache() {
+        timer.shutdown();
+    }
+
+    /**
+     * Returns whether this stamp has been seen before.
+     *
+     * @param stamp     the stamp of the advertisement
+     * @param deviceId  the deviceId of the advertisement (used to handle rotating ids)
+     * @return          true iff this stamp is in the cache
+     */
+    boolean haveSeenStamp(long stamp, String deviceId) {
+        synchronized (this) {
+            CacheEntry entry = cacheByStamp.get(stamp);
+            if (entry != null) {
+                entry.lastSeen = new Instant();
+                if (!entry.deviceId.equals(deviceId)) {
+                    // This probably happened because a device has changed it's ble mac address.
+                    // We need to update the mac address for this entry.
+                    cacheByDeviceId.remove(entry.deviceId);
+                    entry.deviceId = deviceId;
+                    cacheByDeviceId.put(deviceId, entry);
+                }
+            }
+            return entry != null;
+        }
+    }
+
+    /**
+     * Saves the set of advertisements and stamp for this device.
+     *
+     * @param stamp     the stamp provided by the device
+     * @param deviceId  the id of the device
+     * @param adinfos   the advertisements exposed by the device
+     */
+    void saveDevice(long stamp, String deviceId, Iterable<AdInfo> adInfos) {
+        Set<Equivalence.Wrapper<AdInfo>> newAdInfos =
+                FluentIterable.from(adInfos).transform(ADINFO_WRAPPER).toSet();
+        CacheEntry entry = new CacheEntry(stamp, deviceId, newAdInfos);
+        synchronized (this) {
+            Set<Equivalence.Wrapper<AdInfo>> oldAdInfos;
+            CacheEntry oldEntry = cacheByDeviceId.remove(deviceId);
+            if (oldEntry != null) {
+                cacheByStamp.remove(oldEntry.stamp);
+                oldAdInfos = oldEntry.adInfos;
+            } else {
+                oldAdInfos = ImmutableSet.of();
+            }
+
+            Set<Equivalence.Wrapper<AdInfo>> removed = Sets.difference(oldAdInfos, newAdInfos);
+            for (Equivalence.Wrapper<AdInfo> wrapped : removed) {
+                AdInfo adInfo = wrapped.get();
+                adInfosByInterfaceName.remove(adInfo.getAd().getInterfaceName(), wrapped);
+                adInfo.setLost(true);
+                handleUpdate(adInfo);
+            }
+            Set<Equivalence.Wrapper<AdInfo>> added = Sets.difference(newAdInfos, oldAdInfos);
+            for (Equivalence.Wrapper<AdInfo> wrapped : added) {
+                AdInfo adInfo = wrapped.get();
+                adInfosByInterfaceName.put(adInfo.getAd().getInterfaceName(), wrapped);
+                handleUpdate(adInfo);
+            }
+            cacheByStamp.put(stamp, entry);
+            cacheByDeviceId.put(deviceId, entry);
+        }
+    }
+
+    private void handleUpdate(AdInfo adinfo) {
+        Set<Scanner> scanners = scannersByInterfaceName.get("");
+        if (scanners != null) {
+            for (Scanner scanner : scanners) {
+                scanner.handler.handleUpdate(adinfo);
+            }
+        }
+        scanners = scannersByInterfaceName.get(adinfo.getAd().getInterfaceName());
+        if (scanners != null) {
+            for (Scanner scanner : scanners) {
+                scanner.handler.handleUpdate(adinfo);
+            }
+        }
+    }
+
+    /**
+     * Adds a scan handler for advertisements that match {@link interfaceName}.
+     * <p>
+     * If {@link handler} already exists, the old handler is replaced.
+     */
+    void addScanner(String interfaceName, Plugin.ScanHandler handler) {
+        Scanner scanner = new Scanner(interfaceName, handler);
+        synchronized (this) {
+            scannersByHandler.put(handler, scanner);
+            scannersByInterfaceName.put(interfaceName, scanner);
+
+            Iterable<Equivalence.Wrapper<AdInfo>> adinfos;
+            if (interfaceName.isEmpty()) {
+                adinfos = adInfosByInterfaceName.values();
+            } else {
+                adinfos = adInfosByInterfaceName.get(interfaceName);
+            }
+            if (adinfos != null) {
+                for (Equivalence.Wrapper<AdInfo> wrapper : adinfos) {
+                    scanner.handler.handleUpdate(wrapper.get());
+                }
+            }
+        }
+    }
+
+    /**
+     * Removes the scan handler.
+     */
+    void removeScanner(Plugin.ScanHandler handler) {
+        synchronized (this) {
+            Scanner scanner = scannersByHandler.remove(handler);
+            if (scanner != null) {
+                scannersByInterfaceName.remove(scanner.interfaceName, scanner);
+            }
+        }
+    }
+}
diff --git a/android-lib/src/main/java/io/v/android/libs/discovery/ble/BlePlugin.java b/android-lib/src/main/java/io/v/android/libs/discovery/ble/BlePlugin.java
deleted file mode 100644
index f85de26..0000000
--- a/android-lib/src/main/java/io/v/android/libs/discovery/ble/BlePlugin.java
+++ /dev/null
@@ -1,395 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.android.libs.discovery.ble;
-
-import android.bluetooth.BluetoothAdapter;
-import android.bluetooth.BluetoothDevice;
-import android.bluetooth.BluetoothGatt;
-import android.bluetooth.BluetoothGattCharacteristic;
-import android.bluetooth.BluetoothGattServer;
-import android.bluetooth.BluetoothGattServerCallback;
-import android.bluetooth.BluetoothGattService;
-import android.bluetooth.BluetoothManager;
-import android.bluetooth.le.AdvertiseCallback;
-import android.bluetooth.le.AdvertiseData;
-import android.bluetooth.le.AdvertiseSettings;
-import android.bluetooth.le.BluetoothLeAdvertiser;
-import android.bluetooth.le.BluetoothLeScanner;
-import android.bluetooth.le.ScanCallback;
-import android.bluetooth.le.ScanFilter;
-import android.bluetooth.le.ScanResult;
-import android.bluetooth.le.ScanRecord;
-import android.bluetooth.le.ScanSettings;
-import android.content.Context;
-import android.content.pm.PackageManager;
-import android.util.Log;
-import android.support.v4.content.ContextCompat;
-import android.Manifest;
-
-import org.joda.time.Duration;
-
-import java.io.IOException;
-import java.math.BigInteger;
-import java.nio.ByteBuffer;
-import java.security.SecureRandom;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-import java.util.UUID;
-
-import io.v.impl.google.lib.discovery.DeviceCache;
-import io.v.impl.google.lib.discovery.UUIDUtil;
-import io.v.impl.google.lib.discovery.VScanner;
-import io.v.impl.google.lib.discovery.ble.BleAdvertisementConverter;
-import io.v.v23.context.VContext;
-import io.v.impl.google.lib.discovery.ScanHandler;
-import io.v.v23.verror.VException;
-import io.v.x.ref.lib.discovery.Advertisement;
-
-import static io.v.v23.VFutures.sync;
-/**
- * The discovery plugin interface for Bluetooth.
- */
-public class BlePlugin {
-    private static final String TAG = "BlePlugin";
-
-    // We are using a constant for the MTU because Android and paypal/gatt don't get along
-    // when the paypal gatt client sends a setMTU message.  The Android server seems to send
-    // a malformed L2CAP message.
-    private static final int MTU = 23;
-
-    // Object used to lock advertisement objects.
-    private final Object advertisementLock = new Object();
-
-    // Random generator for stamp.
-    private SecureRandom random = new SecureRandom();
-
-    // The id to assign to the next advertisment.
-    private int nextAdv;
-    // A map of advertisement ids to the advertisement that corresponds to them.
-    private final Map<Integer, BluetoothGattService> advertisements = new HashMap<>();
-    // A map of advertisement ids to the thread waiting for cancellation of the context.
-    private final Map<Integer, Thread> advCancellationThreads = new HashMap<>();
-
-    // Object used to lock scanner objects
-    private final Object scannerLock = new Object();
-    // A map of scanner ids to the thread waiting for cancellation of the context.
-    private final Map<Integer, Thread> scanCancellationThreads = new HashMap<>();
-    private final DeviceCache cachedDevices;
-    // Used to track the set of devices we currently talking to.
-    private final Set<String> pendingCalls = new HashSet<>();
-
-    // Set of Ble objects that will be interacted with to perform operations.
-    private BluetoothLeAdvertiser bluetoothLeAdvertise;
-    private BluetoothLeScanner bluetoothLeScanner;
-    private BluetoothGattServer bluetoothGattServer;
-
-    // We need to hold onto the callbacks for scan an advertise because that is what is used
-    // to stop the operation.
-    private ScanCallback scanCallback;
-    private AdvertiseCallback advertiseCallback;
-
-    private boolean isScanning;
-
-    private final Context androidContext;
-
-    // If isEnabled is false, then all operations on the ble plugin are no-oped.  This wil only
-    // be false if the ble hardware is inaccessible.
-    private boolean isEnabled = false;
-
-    // A thread to wait for the cancellation of a particular advertisement.
-    // TODO(spetrovic): remove this thread and replace with a callback on ctx.onDone().
-    private class AdvertisementCancellationRunner implements Runnable{
-        private final VContext ctx;
-
-        private final int id;
-        AdvertisementCancellationRunner(VContext ctx, int id) {
-            this.id = id;
-            this.ctx = ctx;
-        }
-
-        @Override
-        public void run() {
-            try {
-                sync(ctx.onDone());
-            } catch (VException e) {
-                Log.e(TAG, "Error waiting for context to be done: " + e);
-            }
-            finally {
-                BlePlugin.this.removeAdvertisement(id);
-            }
-        }
-    }
-
-    // Similar to AdvertisementCancellationRunner except for scanning.
-    // TODO(spetrovic): Remove this thread and replace with a callback on ctx.onDone().
-    private class ScannerCancellationRunner implements Runnable{
-        private VContext ctx;
-
-        private int id;
-        ScannerCancellationRunner(VContext ctx, int id) {
-            this.id = id;
-            this.ctx = ctx;
-        }
-
-        @Override
-        public void run() {
-            try {
-                sync(ctx.onDone());
-            } catch (VException e) {
-                Log.e(TAG, "Error waiting for context to be done: " + e);
-            }
-            finally {
-                BlePlugin.this.removeScanner(id);
-            }
-        }
-    }
-
-    private boolean hasPermission(String perm) {
-        return ContextCompat.checkSelfPermission(androidContext, perm) ==
-                PackageManager.PERMISSION_GRANTED;
-    }
-    public BlePlugin(Context androidContext) {
-        this.androidContext = androidContext;
-        cachedDevices = new DeviceCache(Duration.standardMinutes(1));
-        BluetoothAdapter bluetoothAdapter = BluetoothAdapter.getDefaultAdapter();
-        if (bluetoothAdapter == null || !bluetoothAdapter.isEnabled()) {
-            return;
-        }
-
-        if (!hasPermission(Manifest.permission.ACCESS_COARSE_LOCATION) &&
-                !hasPermission(Manifest.permission.ACCESS_FINE_LOCATION)) {
-            return;
-        }
-        isEnabled = true;
-        bluetoothLeAdvertise = BluetoothAdapter.getDefaultAdapter().getBluetoothLeAdvertiser();
-        bluetoothLeScanner = BluetoothAdapter.getDefaultAdapter().getBluetoothLeScanner();
-        BluetoothManager manager = (BluetoothManager) androidContext.getSystemService(
-                Context.BLUETOOTH_SERVICE);
-        bluetoothGattServer = manager.openGattServer(androidContext,
-                new BluetoothGattServerCallback() {
-            @Override
-            public void onConnectionStateChange(BluetoothDevice device, int status, int newState) {
-                super.onConnectionStateChange(device, status, newState);
-            }
-
-            @Override
-            public void onCharacteristicReadRequest(BluetoothDevice device, int requestId,
-                                                    int offset,
-                                                    BluetoothGattCharacteristic characteristic) {
-                super.onCharacteristicReadRequest(device, requestId, offset, characteristic);
-                byte[] total =characteristic.getValue();
-                byte[] res = {};
-                // Only send MTU - 1 bytes. The first byte of all packets is the op code.
-                if (offset < total.length) {
-                    int finalByte = offset + MTU - 1;
-                    if (finalByte > total.length) {
-                        finalByte = total.length;
-                    }
-                    res = Arrays.copyOfRange(total, offset, finalByte);
-                    bluetoothGattServer.sendResponse(device, requestId, BluetoothGatt.GATT_SUCCESS, 0, res);
-                } else {
-                    // This should probably be an error, but a bug in the paypal/gatt code causes an
-                    // infinite loop if this returns an error rather than the empty value.
-                    bluetoothGattServer.sendResponse(device, requestId, BluetoothGatt.GATT_SUCCESS, 0,  res);
-                }
-            }
-        });
-    }
-
-
-    // Converts a Vanadium Advertisement to a Bluetooth gatt service.
-    private BluetoothGattService convertToService(Advertisement adv) throws IOException {
-        Map<UUID, byte[]> attributes = BleAdvertisementConverter.vAdvertismentToBleAttr(adv);
-        BluetoothGattService service = new BluetoothGattService(
-                UUIDUtil.UUIDForInterfaceName(adv.getService().getInterfaceName()),
-                BluetoothGattService.SERVICE_TYPE_PRIMARY);
-        for (Map.Entry<UUID, byte[]> entry : attributes.entrySet()) {
-            BluetoothGattCharacteristic ch = new BluetoothGattCharacteristic(
-                    entry.getKey(),
-                    BluetoothGattCharacteristic.PROPERTY_READ,
-                    BluetoothGattCharacteristic.PERMISSION_READ);
-            ch.setValue(entry.getValue());
-            service.addCharacteristic(ch);
-        }
-        return service;
-    }
-
-    public void addAdvertisement(VContext ctx, Advertisement advertisement) throws IOException {
-        if (!isEnabled) {
-            return;
-        }
-        BluetoothGattService service = convertToService(advertisement);
-        synchronized (advertisementLock) {
-            int currentId = nextAdv++;
-            advertisements.put(currentId, service);
-            Thread t = new Thread(new AdvertisementCancellationRunner(ctx, currentId));
-            t.start();
-            advCancellationThreads.put(currentId, t);
-            bluetoothGattServer.addService(service);
-            readvertise();
-        }
-    }
-
-    private void removeAdvertisement(int id) {
-        synchronized (advertisements) {
-            BluetoothGattService s = advertisements.get(id);
-            if (s != null) {
-                bluetoothGattServer.removeService(s);
-            }
-            advertisements.remove(id);
-            advCancellationThreads.remove(id);
-            readvertise();
-        }
-    }
-
-    public void addScanner(VContext ctx, String interfaceName,  ScanHandler handler) {
-        if (!isEnabled) {
-            return;
-        }
-        VScanner scanner = new VScanner(interfaceName, handler);
-        int currentId = cachedDevices.addScanner(scanner);
-        synchronized (scannerLock) {
-            Thread t = new Thread(new ScannerCancellationRunner(ctx, currentId));
-            t.start();
-            scanCancellationThreads.put(currentId, t);
-            updateScanning();
-        }
-    }
-
-    private void removeScanner(int id) {
-        cachedDevices.removeScanner(id);
-        synchronized (scannerLock) {
-            scanCancellationThreads.remove(id);
-            updateScanning();
-        }
-    }
-
-    private void updateScanning() {
-        if (isScanning && scanCancellationThreads.size() == 0) {
-            isScanning = false;
-            bluetoothLeScanner.stopScan(scanCallback);
-            return;
-        }
-
-        if (!isScanning && scanCancellationThreads.size() > 0) {
-            isScanning = true;
-            ScanFilter.Builder builder = new ScanFilter.Builder();
-            byte[] manufacturerData = {};
-            byte[] manufacturerMask = {};
-
-            builder.setManufacturerData(1001, manufacturerData, manufacturerMask);
-            final List<ScanFilter> scanFilter = new ArrayList<>();
-            scanFilter.add(builder.build());
-
-
-            scanCallback = new ScanCallback() {
-                @Override
-                public void onScanResult(int callbackType, ScanResult result) {
-                    // in L the only value for callbackType is CALLBACK_TYPE_ALL_MATCHES, so
-                    // we don't look at its value.
-                    ScanRecord record = result.getScanRecord();
-                    // Use 1001 to denote that this is a Vanadium device.  We picked an id that is
-                    // currently not in use.
-                    byte[] data = record.getManufacturerSpecificData(1001);
-                    ByteBuffer buffer = ByteBuffer.wrap(data);
-                    final long stamp = buffer.getLong();
-                    final String deviceId = result.getDevice().getAddress();
-                    if (cachedDevices.haveSeenStamp(stamp, deviceId)) {
-                        return;
-                    }
-                    synchronized (scannerLock) {
-                        if (pendingCalls.contains(deviceId)) {
-                            Log.d("vanadium", "not connecting to " + deviceId + " because of pending connection");
-                            return;
-                        }
-                        pendingCalls.add(deviceId);
-                    }
-                    BluetoothGattClientCallback.Callback ccb = new BluetoothGattClientCallback.Callback() {
-                        @Override
-                        public void handle(Map<UUID, Map<UUID, byte[]>> services) {
-                            Set<Advertisement> advs = new HashSet<>();
-                            for (Map.Entry<UUID, Map<UUID, byte[]>> entry : services.entrySet()) {
-                                try {
-                                    Advertisement adv =
-                                            BleAdvertisementConverter.
-                                                    bleAttrToVAdvertisement(entry.getValue());
-                                    advs.add(adv);
-                                } catch (IOException e) {
-                                    Log.e("vanadium","Failed to convert advertisement" + e);
-                                }
-                            }
-                            cachedDevices.saveDevice(stamp, advs, deviceId);
-                            synchronized (scannerLock) {
-                                pendingCalls.remove(deviceId);
-                            }
-                            bluetoothLeScanner.startScan(scanFilter, new ScanSettings.Builder().
-                                    setScanMode(ScanSettings.SCAN_MODE_BALANCED).build(), scanCallback);
-                        }
-                    };
-                    BluetoothGattClientCallback cb = new BluetoothGattClientCallback(ccb);
-                    bluetoothLeScanner.stopScan(scanCallback);
-                    Log.d("vanadium", "connecting to " + result.getDevice());
-                    result.getDevice().connectGatt(androidContext, false, cb);
-                }
-
-                @Override
-                public void onBatchScanResults(List<ScanResult> results) {
-                }
-
-                @Override
-                public void onScanFailed(int errorCode) {
-                }
-            };
-            bluetoothLeScanner.startScan(scanFilter, new ScanSettings.Builder().
-                    setScanMode(ScanSettings.SCAN_MODE_BALANCED).build(), scanCallback);
-        }
-    }
-
-    private long genStamp() {
-        // We use 8-byte stamp to reflect the current services of the current device.
-        //
-        // TODO(bjornick): 8-byte random number might not be good enough for
-        // global uniqueness. We might want to consider a better way to generate
-        // stamp like using a unique device id with sequence number.
-        return new BigInteger(64, random).longValue();
-    }
-
-    private void readvertise() {
-        if (advertiseCallback != null) {
-            bluetoothLeAdvertise.stopAdvertising(advertiseCallback);
-            advertiseCallback = null;
-        }
-        if (advertisements.size() == 0) {
-            return;
-        }
-
-        AdvertiseData.Builder builder = new AdvertiseData.Builder();
-        ByteBuffer buf = ByteBuffer.allocate(9);
-        buf.put((byte)8);
-        buf.putLong(genStamp());
-        builder.addManufacturerData(1001, buf.array());
-        AdvertiseSettings.Builder settingsBuilder = new AdvertiseSettings.Builder();
-        settingsBuilder.setAdvertiseMode(AdvertiseSettings.ADVERTISE_MODE_LOW_LATENCY);
-        settingsBuilder.setConnectable(true);
-        advertiseCallback = new AdvertiseCallback() {
-                    @Override
-                    public void onStartSuccess(AdvertiseSettings settingsInEffect) {
-                        Log.i("vanadium", "Successfully started " + settingsInEffect);
-                    }
-
-                    @Override
-                    public void onStartFailure(int errorCode) {
-                        Log.i("vanadium", "Failed to start advertising " + errorCode);
-                    }
-                };
-        bluetoothLeAdvertise.startAdvertising(settingsBuilder.build(), builder.build(),
-                advertiseCallback);
-    }
-}
diff --git a/android-lib/src/main/java/io/v/android/libs/discovery/ble/BluetoothGattClientCallback.java b/android-lib/src/main/java/io/v/android/libs/discovery/ble/BluetoothGattClientCallback.java
deleted file mode 100644
index 7b438cf..0000000
--- a/android-lib/src/main/java/io/v/android/libs/discovery/ble/BluetoothGattClientCallback.java
+++ /dev/null
@@ -1,112 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.android.libs.discovery.ble;
-
-import android.bluetooth.BluetoothGatt;
-import android.bluetooth.BluetoothGattCallback;
-import android.bluetooth.BluetoothGattCharacteristic;
-import android.bluetooth.BluetoothGattService;
-import android.util.Log;
-
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.Hashtable;
-import java.util.List;
-import java.util.Map;
-import java.util.UUID;
-
-/**
- * A handler for responses from a GattServer.
- */
-public class BluetoothGattClientCallback extends BluetoothGattCallback {
-    /**
-     * A handler that will get called when all the services from a gatt service
-     * are read.
-     */
-    public interface Callback {
-        /**
-         * Called with the map of service ids to their attributes.
-         * @param services A map from service id to (characteristics uuid to values).
-         */
-        void handle(Map<UUID, Map<UUID, byte[]>> services);
-    }
-    // We want to ignore the GATT and GAP services, which are 1800 and 1801 respectively.
-    static final String GATT_AND_GAP_PREFIX = "0000180";
-
-    private final Callback callback;
-
-    private final Map<UUID, Map<UUID, byte[]>> services = new HashMap<>();
-
-    private BluetoothGatt gatt;
-
-    private final List<BluetoothGattCharacteristic> chars = new ArrayList<>();
-    private int pos;
-
-    BluetoothGattClientCallback(Callback cb) {
-        callback = cb;
-    }
-
-    @Override
-    public void onServicesDiscovered(BluetoothGatt gatt, int status) {
-        for (BluetoothGattService service : gatt.getServices()) {
-            Log.d("vanadium", "Saw service" + service.getUuid().toString());
-            // Skip the GATT AND GAP Services.
-            if (service.getUuid().toString().startsWith(GATT_AND_GAP_PREFIX)) {
-                continue;
-            }
-            services.put(service.getUuid(), new HashMap<UUID, byte[]>());
-            // We only keep track of the characteristics that can be read.
-            for (BluetoothGattCharacteristic ch : service.getCharacteristics()) {
-                if ((ch.getProperties() & BluetoothGattCharacteristic.PROPERTY_READ) != 0) {
-                    chars.add(ch);
-                } else {
-                    Log.d("vanadium", "skipping non read property");
-                }
-            }
-        }
-        pos = 0;
-        maybeReadNextCharacteristic();
-    }
-
-    // Reads the next characteristic if there is one.  Otherwise calls callback and
-    // closes the gatt connection.
-    private void maybeReadNextCharacteristic() {
-        if (pos >= chars.size()) {
-            gatt.disconnect();
-            gatt.close();
-            callback.handle(services);
-            return;
-        }
-        BluetoothGattCharacteristic c = chars.get(pos++);
-        if (!gatt.readCharacteristic(c)) {
-            Log.d("vanadium", "Failed to read characteristic " + c.getUuid());
-            maybeReadNextCharacteristic();
-        }
-    }
-
-    @Override
-    public void onCharacteristicRead(BluetoothGatt gatt, BluetoothGattCharacteristic characteristic,
-                                     int status) {
-        UUID serviceUUID = characteristic.getService().getUuid();
-        Log.d("vanadium", "Got characteristic [" + serviceUUID + "]"
-                + characteristic.getUuid() + "=" + characteristic.getValue());
-        services.get(serviceUUID).put(characteristic.getUuid(), characteristic.getValue());
-        maybeReadNextCharacteristic();
-    }
-
-    @Override
-    public void onConnectionStateChange(BluetoothGatt gatt, int status, int newState) {
-        Log.d("vanadium", "new connections state is " + newState);
-
-        this.gatt = gatt;
-        if (status != BluetoothGatt.GATT_SUCCESS || newState != BluetoothGatt.STATE_CONNECTED) {
-            Log.d("vanadium", "failed to connect with status " + status + " state" + newState);
-            gatt.close();
-            callback.handle(null);
-            return;
-        }
-        gatt.discoverServices();
-    }
-}
diff --git a/android-lib/src/main/java/io/v/android/libs/discovery/ble/NativeScanHandler.java b/android-lib/src/main/java/io/v/android/libs/discovery/ble/NativeScanHandler.java
deleted file mode 100644
index e3995dc..0000000
--- a/android-lib/src/main/java/io/v/android/libs/discovery/ble/NativeScanHandler.java
+++ /dev/null
@@ -1,36 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.android.libs.discovery.ble;
-
-import io.v.impl.google.lib.discovery.ScanHandler;
-import io.v.x.ref.lib.discovery.Advertisement;
-
-/**
- * An implementation of the ScanHandler for use by the discovery framework.  This handler is used
- * to pass results from the BlePlugin to the go wrapper to passed on to the discovery instance.
- */
-class NativeScanHandler implements ScanHandler{
-    /**
-     * A pointer to the the native channel.
-     */
-    private long nativeChan;
-
-    NativeScanHandler(long nativeChan) {
-        this.nativeChan = nativeChan;
-    }
-
-    private native void nativeHandleUpdate(Advertisement adv, long chan);
-    private native void nativeFinalize(long chan);
-
-    @Override
-    public void handleUpdate(Advertisement advertisement) {
-        nativeHandleUpdate(advertisement, nativeChan);
-    }
-
-    @Override
-    protected void finalize() throws Throwable {
-        nativeFinalize(nativeChan);
-    }
-}
diff --git a/android-lib/src/test/java/io/v/android/impl/google/discovery/plugins/ble/ConvertUtilTest.java b/android-lib/src/test/java/io/v/android/impl/google/discovery/plugins/ble/ConvertUtilTest.java
new file mode 100644
index 0000000..d814455
--- /dev/null
+++ b/android-lib/src/test/java/io/v/android/impl/google/discovery/plugins/ble/ConvertUtilTest.java
@@ -0,0 +1,56 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.android.impl.google.discovery.plugins.ble;
+
+import junit.framework.TestCase;
+
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.UUID;
+
+import io.v.v23.V;
+
+import io.v.x.ref.lib.discovery.AdInfo;
+import io.v.x.ref.lib.discovery.plugins.ble.testdata.AdConversionTestCase;
+import io.v.x.ref.lib.discovery.plugins.ble.testdata.Constants;
+
+import static com.google.common.truth.Truth.assertThat;
+import static com.google.common.truth.Truth.assertWithMessage;
+import static io.v.impl.google.lib.discovery.DiscoveryTestUtil.assertThat;
+
+/**
+ * Tests for {@link ConvertUtil}
+ */
+public class ConvertUtilTest extends TestCase {
+    protected void setUp() {
+        V.init(); // V.init() sets up the jni bindings.
+    }
+
+    public void testToGattAttrs() throws IOException {
+        for (AdConversionTestCase test : Constants.CONVERSION_TEST_DATA) {
+            Map<UUID, byte[]> got = ConvertUtil.toGattAttrs(test.getAdInfo());
+            Map<String, byte[]> want = test.getGattAttrs();
+
+            assertThat(got.size()).isEqualTo(want.size());
+            for (Map.Entry<UUID, byte[]> entry : got.entrySet()) {
+                String uuid = entry.getKey().toString();
+                assertWithMessage(uuid).that(entry.getValue()).isEqualTo(want.get(uuid));
+            }
+        }
+    }
+
+    public void testToAdInfo() throws IOException {
+        for (AdConversionTestCase test : Constants.CONVERSION_TEST_DATA) {
+            Map<UUID, byte[]> attrs = new HashMap<>();
+            for (Map.Entry<String, byte[]> entry : test.getGattAttrs().entrySet()) {
+                attrs.put(UUID.fromString(entry.getKey()), entry.getValue());
+            }
+
+            AdInfo got = ConvertUtil.toAdInfo(attrs);
+            assertThat(got).isEqualTo(test.getAdInfo());
+        }
+    }
+}
diff --git a/android-lib/src/test/java/io/v/android/impl/google/discovery/plugins/ble/DeviceCacheTest.java b/android-lib/src/test/java/io/v/android/impl/google/discovery/plugins/ble/DeviceCacheTest.java
new file mode 100644
index 0000000..77683c0
--- /dev/null
+++ b/android-lib/src/test/java/io/v/android/impl/google/discovery/plugins/ble/DeviceCacheTest.java
@@ -0,0 +1,263 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.android.impl.google.discovery.plugins.ble;
+
+import com.google.common.base.Function;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Random;
+
+import junit.framework.TestCase;
+
+import org.joda.time.Duration;
+
+import org.junit.Test;
+
+import io.v.v23.discovery.AdId;
+import io.v.v23.discovery.Advertisement;
+import io.v.v23.discovery.Attributes;
+import io.v.v23.discovery.Attachments;
+
+import io.v.x.ref.lib.discovery.AdInfo;
+import io.v.x.ref.lib.discovery.AdHash;
+import io.v.x.ref.lib.discovery.EncryptionAlgorithm;
+import io.v.x.ref.lib.discovery.EncryptionKey;
+
+import static com.google.common.truth.Truth.assertThat;
+import static io.v.impl.google.lib.discovery.DiscoveryTestUtil.assertThat;
+
+/**
+ * Tests for {@link DeviceCache}.
+ */
+public class DeviceCacheTest extends TestCase {
+    private static Random rand = new Random();
+
+    private static byte[] randBytes(int size) {
+        byte[] bytes = new byte[size];
+        rand.nextBytes(bytes);
+        return bytes;
+    }
+
+    private static AdInfo newAdInfo(String interfaceName) {
+        return new AdInfo(
+                new Advertisement(
+                        new AdId(randBytes(AdId.VDL_TYPE.getLength())),
+                        interfaceName,
+                        ImmutableList.<String>of(),
+                        new Attributes(),
+                        new Attachments()),
+                new EncryptionAlgorithm(),
+                ImmutableList.<EncryptionKey>of(),
+                new AdHash(randBytes(AdHash.VDL_TYPE.getLength())),
+                ImmutableList.<String>of(),
+                false);
+    }
+
+    private static AdInfo copyAdInfo(AdInfo adinfo) {
+        return new AdInfo(
+                new Advertisement(
+                        adinfo.getAd().getId(),
+                        adinfo.getAd().getInterfaceName(),
+                        adinfo.getAd().getAddresses(),
+                        adinfo.getAd().getAttributes(),
+                        adinfo.getAd().getAttachments()),
+                adinfo.getEncryptionAlgorithm(),
+                adinfo.getEncryptionKeys(),
+                adinfo.getHash(),
+                adinfo.getDirAddrs(),
+                adinfo.getLost());
+    }
+
+    private static List<AdInfo> newAdInfoList(AdInfo... adinfos) {
+        return Lists.transform(
+                ImmutableList.copyOf(adinfos),
+                new Function<AdInfo, AdInfo>() {
+                    @Override
+                    public AdInfo apply(AdInfo adinfo) {
+                        return copyAdInfo(adinfo);
+                    }
+                });
+    }
+
+    private static class MockHandler implements Plugin.ScanHandler {
+        private List<AdInfo> updates = new ArrayList<>();
+
+        @Override
+        public synchronized void handleUpdate(AdInfo adinfo) {
+            updates.add(copyAdInfo(adinfo));
+            notifyAll();
+        }
+    }
+
+    public void testSaveDeveice() {
+        DeviceCache cache = new DeviceCache(Duration.standardMinutes(10));
+        // The advertisements here are not relevant since we are just checking
+        // the seen stamp function.
+        long stamp = 10001;
+        assertThat(cache.haveSeenStamp(stamp, "device")).isFalse();
+        cache.saveDevice(stamp, "device", ImmutableList.<AdInfo>of());
+        assertThat(cache.haveSeenStamp(stamp, "device")).isTrue();
+        cache.shutdownCache();
+    }
+
+    public void testSaveDeviceWithDifferentStampCode() {
+        DeviceCache cache = new DeviceCache(Duration.standardMinutes(10));
+        // The advertisements here are not relevant since we are just checking
+        // the seen stamp function.
+        long stamp = 10001;
+        assertThat(cache.haveSeenStamp(stamp, "device")).isFalse();
+        cache.saveDevice(stamp, "device", ImmutableList.<AdInfo>of());
+        assertThat(cache.haveSeenStamp(stamp, "device")).isTrue();
+        cache.saveDevice(stamp + 1, "device", ImmutableList.<AdInfo>of());
+        assertThat(cache.haveSeenStamp(stamp + 1, "device")).isTrue();
+        assertThat(cache.haveSeenStamp(stamp, "device")).isFalse();
+        cache.shutdownCache();
+    }
+
+    public void testAddingScannerBeforeSavingDevice() {
+        DeviceCache cache = new DeviceCache(Duration.standardMinutes(10));
+        long stamp = 10001;
+
+        AdInfo adinfo1 = newAdInfo("interface1");
+        AdInfo adinfo2 = newAdInfo("interface2");
+
+        MockHandler handler1 = new MockHandler();
+        cache.addScanner("interface1", handler1);
+
+        MockHandler handler2 = new MockHandler();
+        cache.addScanner("", handler2);
+
+        cache.saveDevice(stamp, "device", newAdInfoList(adinfo1, adinfo2));
+
+        // Make sure that the handlers are called;
+        assertThat(handler1.updates.size()).isEqualTo(1);
+        assertThat(handler1.updates.get(0)).isEqualTo(adinfo1);
+        assertThat(handler2.updates).isEqualTo(adinfo1, adinfo2);
+        cache.shutdownCache();
+    }
+
+    public void testAddingScannerAfterSavingDevice() {
+        DeviceCache cache = new DeviceCache(Duration.standardMinutes(10));
+        long stamp = 10001;
+
+        AdInfo adinfo1 = newAdInfo("interface1");
+        AdInfo adinfo2 = newAdInfo("interface2");
+
+        cache.saveDevice(stamp, "device", newAdInfoList(adinfo1, adinfo2));
+
+        MockHandler handler1 = new MockHandler();
+        cache.addScanner("interface1", handler1);
+
+        MockHandler handler2 = new MockHandler();
+        cache.addScanner("", handler2);
+
+        // Make sure that the handlers are called;
+        assertThat(handler1.updates.size()).isEqualTo(1);
+        assertThat(handler1.updates.get(0)).isEqualTo(adinfo1);
+        assertThat(handler2.updates).isEqualTo(adinfo1, adinfo2);
+        cache.shutdownCache();
+    }
+
+    public void testRemovingAdvertisement() {
+        DeviceCache cache = new DeviceCache(Duration.standardMinutes(10));
+        long stamp = 10001;
+
+        AdInfo adinfo1 = newAdInfo("interface1");
+        AdInfo adinfo2 = newAdInfo("interface2");
+
+        MockHandler handler = new MockHandler();
+        cache.addScanner("interface1", handler);
+
+        cache.saveDevice(stamp, "device", newAdInfoList(adinfo1, adinfo2));
+        cache.saveDevice(stamp + 1, "device", newAdInfoList(adinfo2));
+
+        // Make sure that the handler is called;
+        assertThat(handler.updates.size()).isEqualTo(2);
+        assertThat(handler.updates.get(0)).isEqualTo(adinfo1, false);
+        assertThat(handler.updates.get(1)).isEqualTo(adinfo1, true);
+        cache.shutdownCache();
+    }
+
+    public void testAddingSameAdvertisement() {
+        DeviceCache cache = new DeviceCache(Duration.standardMinutes(10));
+        long stamp = 10001;
+
+        AdInfo adinfo = newAdInfo("interface1");
+
+        MockHandler handler = new MockHandler();
+        cache.addScanner("interface1", handler);
+
+        cache.saveDevice(stamp, "device", newAdInfoList(adinfo));
+        cache.saveDevice(stamp + 1, "device", newAdInfoList(adinfo));
+
+        // Make sure that the handler is called;
+        assertThat(handler.updates.size()).isEqualTo(1);
+        assertThat(handler.updates.get(0)).isEqualTo(adinfo);
+        cache.shutdownCache();
+    }
+
+    public void testRemovingScanner() {
+        DeviceCache cache = new DeviceCache(Duration.standardMinutes(10));
+        long stamp = 10001;
+
+        AdInfo adinfo1 = newAdInfo("interface1");
+        AdInfo adinfo2 = newAdInfo("interface2");
+
+        MockHandler handler = new MockHandler();
+        cache.addScanner("interface1", handler);
+
+        cache.saveDevice(stamp, "device", newAdInfoList(adinfo1));
+
+        assertThat(handler.updates.size()).isEqualTo(1);
+        assertThat(handler.updates.get(0)).isEqualTo(adinfo1);
+
+        cache.removeScanner(handler);
+
+        cache.saveDevice(stamp, "device", newAdInfoList(adinfo2));
+
+        // Make sure that the handler is not called any more;
+        assertThat(handler.updates.size()).isEqualTo(1);
+        cache.shutdownCache();
+    }
+
+    @Test(timeout = 30000)
+    public void testCacheEviction() {
+        // TODO(jhahn): Use a fake ScheduledExecutorService.
+        DeviceCache cache = new DeviceCache(Duration.millis(2));
+        long stamp = 10001;
+
+        AdInfo adinfo = newAdInfo("interface1");
+
+        MockHandler handler = new MockHandler();
+        cache.addScanner("interface1", handler);
+
+        cache.saveDevice(stamp, "device", newAdInfoList(adinfo));
+
+        synchronized (handler) {
+            try {
+                while (handler.updates.size() < 2) {
+                    handler.wait();
+                }
+            } catch (InterruptedException e) {
+                // Keep waiting.
+            }
+        }
+
+        // Make sure that the handler is called;
+        assertThat(handler.updates.size()).isEqualTo(2);
+        assertThat(handler.updates.get(0)).isEqualTo(adinfo, false);
+        assertThat(handler.updates.get(1)).isEqualTo(adinfo, true);
+
+        // Make sure that there is no cached entries.
+        handler = new MockHandler();
+        cache.addScanner("interface1", handler);
+        assertThat(handler.updates.size()).isEqualTo(0);
+
+        cache.shutdownCache();
+    }
+}
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/DeviceCache.java b/lib/src/main/java/io/v/impl/google/lib/discovery/DeviceCache.java
deleted file mode 100644
index b6b7b80..0000000
--- a/lib/src/main/java/io/v/impl/google/lib/discovery/DeviceCache.java
+++ /dev/null
@@ -1,210 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.impl.google.lib.discovery;
-
-
-import com.google.common.collect.HashMultimap;
-import com.google.common.collect.SetMultimap;
-import com.google.common.collect.Sets;
-
-import org.joda.time.Duration;
-import org.joda.time.Instant;
-
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.Map;
-import java.util.Set;
-import java.util.HashSet;
-import java.util.concurrent.Executors;
-import java.util.concurrent.ScheduledExecutorService;
-import java.util.concurrent.TimeUnit;
-import java.util.concurrent.atomic.AtomicInteger;
-
-import io.v.x.ref.lib.discovery.Advertisement;
-
-/**
- * A cache of ble devices that were seen recently.  The current Vanadium BLE protocol requires
- * connecting to the advertiser to grab the attributes and the addrs.  This can be expensive
- * so we only refetch the data if its stamp changed.
- */
-public class DeviceCache {
-    private final Map<Long, CacheEntry> cachedDevices = new HashMap<>();
-    private final Map<String, CacheEntry> knownIds = new HashMap<>();
-
-    private final AtomicInteger nextScanner = new AtomicInteger(0);
-    private final SetMultimap<String, Advertisement> knownServices = HashMultimap.create();
-    private final Map<Integer, VScanner> scannersById = new HashMap<>();
-    private final SetMultimap<String, VScanner> scannersByInterfaceName = HashMultimap.create();
-    ScheduledExecutorService timer;
-
-    private final Duration maxAge;
-
-
-    public DeviceCache(final Duration maxAge) {
-        this.maxAge = maxAge;
-        this.timer = Executors.newSingleThreadScheduledExecutor();
-        long periodicity = maxAge.getMillis() / 2;
-        timer.scheduleAtFixedRate(new Runnable() {
-            @Override
-            public void run() {
-                removeStaleEntries();
-            }
-        }, periodicity, periodicity, TimeUnit.MILLISECONDS);
-    }
-
-    void removeStaleEntries() {
-        synchronized (this) {
-            Iterator<Map.Entry<Long, CacheEntry>> it = cachedDevices.entrySet().iterator();
-
-            while (it.hasNext()) {
-                Map.Entry<Long, CacheEntry> mapEntry = it.next();
-                CacheEntry entry = mapEntry.getValue();
-                if (entry.lastSeen.plus(maxAge).isBeforeNow()) {
-                    it.remove();
-                    knownIds.remove(entry.deviceId);
-                    for (Advertisement adv : entry.advertisements) {
-                        knownServices.remove(adv.getService().getInterfaceName(), adv);
-                        adv.setLost(true);
-                        handleUpdate(adv);
-                    }
-                }
-            }
-        }
-    }
-
-
-    /**
-     * Cleans up the cache's state and shutdowns the eviction thread.
-     */
-    public void shutdownCache() {
-        timer.shutdown();
-    }
-
-    /**
-     * Returns whether this stamp has been seen before.
-     *
-     * @param stamp the stamp of the advertisement
-     * @param deviceId the deviceId of the advertisement (used to handle rotating ids).
-     * @return true iff this stamp is in the cache.
-     */
-    public boolean haveSeenStamp(long stamp, String deviceId) {
-        synchronized (this) {
-            CacheEntry entry = cachedDevices.get(stamp);
-            if (entry != null) {
-                entry.lastSeen = new Instant();
-                if (!entry.deviceId.equals(deviceId)) {
-                    // This probably happened becuase a device has changed it's ble mac address.
-                    // We need to update the mac address for this entry.
-                    knownIds.remove(entry.deviceId);
-                    entry.deviceId = deviceId;
-                    knownIds.put(deviceId, entry);
-                }
-            }
-            return entry != null;
-        }
-    }
-
-    /**
-     * Saves the set of advertisements and stamp for this device.
-     *
-     * @param stamp the stamp provided by the device.
-     * @param advs the advertisements exposed by the device.
-     * @param deviceId the id of the device.
-     */
-    public void saveDevice(long stamp, Set<Advertisement> advs, String deviceId) {
-        CacheEntry entry = new CacheEntry(advs, stamp, deviceId);
-        synchronized (this) {
-            CacheEntry oldEntry = knownIds.get(deviceId);
-            Set<Advertisement> oldValues = null;
-            if (oldEntry != null) {
-                cachedDevices.remove(oldEntry.stamp);
-                knownIds.remove(oldEntry.deviceId);
-                oldValues = oldEntry.advertisements;
-            } else {
-                oldValues = new HashSet<>();
-            }
-            Set<Advertisement> removed = Sets.difference(oldValues, advs);
-            for (Advertisement adv : removed) {
-                knownServices.remove(adv.getService().getInterfaceName(), adv);
-                adv.setLost(true);
-                handleUpdate(adv);
-            }
-
-            Set<Advertisement> added = Sets.difference(advs, oldValues);
-            for (Advertisement adv: added) {
-                knownServices.put(adv.getService().getInterfaceName(), adv);
-                handleUpdate(adv);
-            }
-            cachedDevices.put(stamp, entry);
-            CacheEntry oldDeviceEntry = knownIds.get(deviceId);
-            if (oldDeviceEntry != null) {
-                // Delete the old stamp value.
-                cachedDevices.remove(stamp);
-            }
-            knownIds.put(deviceId, entry);
-        }
-    }
-
-    private void handleUpdate(Advertisement adv) {
-        Set<VScanner> scanners = scannersByInterfaceName.get(adv.getService().getInterfaceName());
-        if (scanners == null) {
-            return;
-        }
-        for (VScanner scanner : scanners) {
-            scanner.getHandler().handleUpdate(adv);
-        }
-    }
-
-    /**
-     * Adds a scanner that will be notified when advertisements that match its query have changed.
-     *
-     * @return the handle of the scanner that can be used to remove the scanner.
-     */
-    public int addScanner(VScanner scanner) {
-        synchronized (this) {
-            int id = nextScanner.addAndGet(1);
-            scannersById.put(id, scanner);
-            scannersByInterfaceName.put(scanner.getInterfaceName(), scanner);
-            Set<Advertisement> knownAdvs = knownServices.get(scanner.getInterfaceName());
-            if (knownAdvs != null) {
-                for (Advertisement adv : knownAdvs) {
-                    scanner.getHandler().handleUpdate(adv);
-                }
-            }
-            return id;
-        }
-    }
-
-    /**
-     * Removes the scanner matching this id.  This scanner will stop getting updates.
-     */
-    public void removeScanner(int id) {
-        synchronized (this) {
-            VScanner scanner = scannersById.get(id);
-            if (scanner != null) {
-                scannersByInterfaceName.remove(scanner.getInterfaceName(), scanner);
-                scannersById.remove(id);
-            }
-        }
-    }
-
-    private class CacheEntry {
-        Set<Advertisement> advertisements;
-
-        long stamp;
-
-        Instant lastSeen;
-
-        String deviceId;
-
-        CacheEntry(Set<Advertisement> advs, long stamp, String deviceId) {
-            advertisements = advs;
-            this.stamp = stamp;
-            lastSeen = new Instant();
-            this.deviceId = deviceId;
-        }
-    }
-
-}
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/DiscoveryImpl.java b/lib/src/main/java/io/v/impl/google/lib/discovery/DiscoveryImpl.java
new file mode 100644
index 0000000..89d918b
--- /dev/null
+++ b/lib/src/main/java/io/v/impl/google/lib/discovery/DiscoveryImpl.java
@@ -0,0 +1,71 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.impl.google.lib.discovery;
+
+import com.google.common.util.concurrent.ListenableFuture;
+import com.google.common.util.concurrent.FutureFallback;
+import com.google.common.util.concurrent.Futures;
+
+import java.util.List;
+import java.util.concurrent.CancellationException;
+
+import io.v.v23.InputChannel;
+import io.v.v23.context.VContext;
+import io.v.v23.discovery.Advertisement;
+import io.v.v23.discovery.Discovery;
+import io.v.v23.discovery.Update;
+import io.v.v23.security.BlessingPattern;
+import io.v.v23.verror.VException;
+
+import io.v.impl.google.ListenableFutureCallback;
+
+class DiscoveryImpl implements Discovery {
+    private final long nativePtr;
+
+    private native void nativeAdvertise(
+            long nativePtr,
+            VContext ctx,
+            Advertisement ad,
+            List<BlessingPattern> visibility,
+            ListenableFutureCallback<Void> cb)
+            throws VException;
+
+    private native InputChannel<Update> nativeScan(long nativePtr, VContext ctx, String query)
+            throws VException;
+
+    private native void nativeFinalize(long nativePtr);
+
+    private DiscoveryImpl(long nativePtr) {
+        this.nativePtr = nativePtr;
+    }
+
+    @Override
+    public ListenableFuture<Void> advertise(
+            VContext ctx, Advertisement ad, List<BlessingPattern> visibility) throws VException {
+        ListenableFutureCallback<Void> cb = new ListenableFutureCallback<>();
+        nativeAdvertise(nativePtr, ctx, ad, visibility, cb);
+        return Futures.withFallback(
+                cb.getFuture(ctx),
+                new FutureFallback<Void>() {
+                    public ListenableFuture<Void> create(Throwable t) {
+                        if (t instanceof CancellationException) {
+                            return Futures.immediateFuture(null);
+                        }
+                        return Futures.immediateFailedFuture(t);
+                    }
+                });
+    }
+
+    @Override
+    public InputChannel<Update> scan(VContext ctx, String query) throws VException {
+        return nativeScan(nativePtr, ctx, query);
+    }
+
+    @Override
+    protected void finalize() throws Throwable {
+        super.finalize();
+        nativeFinalize(nativePtr);
+    }
+}
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/EncodingUtil.java b/lib/src/main/java/io/v/impl/google/lib/discovery/EncodingUtil.java
index 94b9669..34b6c48 100644
--- a/lib/src/main/java/io/v/impl/google/lib/discovery/EncodingUtil.java
+++ b/lib/src/main/java/io/v/impl/google/lib/discovery/EncodingUtil.java
@@ -1,10 +1,9 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Copyright 2016 The Vanadium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 package io.v.impl.google.lib.discovery;
 
-
 import com.google.common.primitives.Bytes;
 
 import java.io.ByteArrayInputStream;
@@ -17,15 +16,15 @@
 import java.util.ArrayList;
 import java.util.List;
 
+import io.v.x.ref.lib.discovery.EncryptionAlgorithm;
 import io.v.x.ref.lib.discovery.EncryptionKey;
 
 /**
  * A utility to encode and decode fields in io.v.v23.Service fields for use in discovery.
- *
- * TODO(bjornick,jhahn): Consider to share v.io/x/ref/lib/discovery/encoding.go through jni.
  */
 public class EncodingUtil {
-    static final Charset UTF8_CHARSET = Charset.forName("UTF-8");
+    // We use "ISO8859-1" to preserve data in a string without interpretation.
+    private static final Charset ENC = Charset.forName("ISO8859-1");
 
     private static void writeUint(OutputStream out, int x) throws IOException {
         while ((x & 0xffffff80) != 0) {
@@ -36,7 +35,7 @@
     }
 
     private static int readUint(InputStream in) throws IOException {
-        for (int x = 0, s = 0; ;) {
+        for (int x = 0, s = 0; ; ) {
             int b = in.read();
             if (b == -1) {
                 throw new EOFException();
@@ -55,15 +54,15 @@
     /**
      * Encodes the addresses passed in.
      *
-     * @param addrs the list of addresses to encode.
-     * @return the byte representation of the encoded addresses.
-     * @throws IOException if the address can't be encoded.
+     * @param addrs         the list of addresses to encode
+     * @return              the byte representation of the encoded addresses
+     * @throws IOException  if the address can't be encoded
      */
     public static byte[] packAddresses(List<String> addrs) throws IOException {
         ByteArrayOutputStream stream = new ByteArrayOutputStream();
         for (String addr : addrs) {
             writeUint(stream, addr.length());
-            stream.write(addr.getBytes(UTF8_CHARSET));
+            stream.write(addr.getBytes(ENC));
         }
         return stream.toByteArray();
     }
@@ -71,9 +70,9 @@
     /**
      * Decodes addresses from a byte array that was encoded by packAddresses
      *
-     * @param input the byte array toe decode
-     * @return the list of addresses.
-     * @throws IOException if the addresses can't be decoded.
+     * @param input         the byte array to decode
+     * @return              the list of addresses.
+     * @throws IOException  if the addresses can't be decoded
      */
     public static List<String> unpackAddresses(byte[] input) throws IOException {
         ByteArrayInputStream stream = new ByteArrayInputStream(input);
@@ -85,24 +84,24 @@
             if (read != size) {
                 throw new EOFException();
             }
-            output.add(new String(data, UTF8_CHARSET));
+            output.add(new String(data, ENC));
         }
         return output;
     }
 
     /**
-     * Encode the encryption keys and algorithm passed in.
+     * Encodes the encryption algorithm and keys passed in.
      *
-     * @param encryptionAlgorithm the encryption algorithm to use.
-     *                            See io.v.x.ref.lib.discovery.Constants for valid values.
-     * @param keys the keys to encode
-     * @return the byte array that is the encoded form.
-     * @throws IOException if the keys can't be encoded.
+     * @param algo          the encryption algorithm to use; See
+     *                      {@link io.v.x.ref.lib.discovery.Constants} for valid values
+     * @param keys          the keys to encode
+     * @return              the byte array that is the encoded form
+     * @throws IOException  if the keys can't be encoded
      */
-    public static byte[] packEncryptionKeys(int encryptionAlgorithm, List<EncryptionKey> keys)
+    public static byte[] packEncryptionKeys(EncryptionAlgorithm algo, List<EncryptionKey> keys)
             throws IOException {
         ByteArrayOutputStream stream = new ByteArrayOutputStream();
-        writeUint(stream, encryptionAlgorithm);
+        writeUint(stream, algo.getValue());
         for (EncryptionKey key : keys) {
             byte[] byteKey = Bytes.toArray(key);
             writeUint(stream, byteKey.length);
@@ -114,14 +113,15 @@
     /**
      * Decodes the encryption algorithm and keys that was encoded by packEncryptionKeys.
      *
-     * @param input the byte array containg the keys.
-     * @return the keys and the encryption algorithm in input.
-     * @throws IOException if the keys can't be decoded.
+     * @param input         the byte array to decode
+     * @param keys          the keys where the decoded keys is stored
+     * @return              the encryption algorithm
+     * @throws IOException  if the keys can't be decoded
      */
-    public static KeysAndAlgorithm unpackEncryptionKeys(byte[] input) throws IOException {
+    public static EncryptionAlgorithm unpackEncryptionKeys(byte[] input, List<EncryptionKey> keys)
+            throws IOException {
         ByteArrayInputStream stream = new ByteArrayInputStream(input);
         int algo = readUint(stream);
-        List<EncryptionKey> keys = new ArrayList<>();
         while (stream.available() > 0) {
             int size = readUint(stream);
             byte[] key = new byte[size];
@@ -131,33 +131,6 @@
             }
             keys.add(new EncryptionKey(Bytes.asList(key)));
         }
-        return new KeysAndAlgorithm(algo, keys);
-    }
-
-    /**
-     * Stores {@link EncryptionKey}s and the encryption algorithm.
-     */
-    public static class KeysAndAlgorithm {
-        int encryptionAlgorithm;
-        List<EncryptionKey> keys;
-
-        /**
-         * Returns the stored encryption algorithm.
-         */
-        public int getEncryptionAlgorithm() {
-            return encryptionAlgorithm;
-        }
-
-        /**
-         * Returns the stored keys.
-         */
-        public List<EncryptionKey> getKeys() {
-            return keys;
-        }
-
-        KeysAndAlgorithm(int encryptionAlgo, List<EncryptionKey> keys) {
-            encryptionAlgorithm = encryptionAlgo;
-            this.keys = keys;
-        }
+        return new EncryptionAlgorithm(algo);
     }
 }
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/Plugin.java b/lib/src/main/java/io/v/impl/google/lib/discovery/Plugin.java
new file mode 100644
index 0000000..93219ab
--- /dev/null
+++ b/lib/src/main/java/io/v/impl/google/lib/discovery/Plugin.java
@@ -0,0 +1,67 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.impl.google.lib.discovery;
+
+import io.v.x.ref.lib.discovery.AdInfo;
+
+/**
+ * An interface for discovery plugins in Java.
+ */
+public interface Plugin {
+    /**
+     * Starts the advertisement of {@link adInfo}.
+     * <p>
+     * The advertisement will not be changed while it is being advertised.
+     * <p>
+     * If the advertisement is too large, the plugin may drop any information except
+     * {@code id}, {@code interfaceName}, {@code hash}, and {@code dirAddrs}.
+     * <p>
+     *
+     * @param adInfo      an advertisement to advertises
+     * @throws Exception  if advertising couldn't be started
+     */
+    void startAdvertising(AdInfo adInfo) throws Exception;
+
+    /**
+     * Stops the advertisement of {@link adInfo}.
+     *
+     * @param adInfo      the advertisement to stop advertising
+     * @throws Exception  if advertising couldn't be stopped
+     */
+    void stopAdvertising(AdInfo adInfo) throws Exception;
+
+    /**
+     * An interface for passing scanned advertisements.
+     */
+    public interface ScanHandler {
+        /**
+         * Called with each discovery update.
+         */
+        void handleUpdate(AdInfo adinfo);
+    }
+
+    /**
+     * Starts a scan looking for advertisements that match the interface name.
+     * <p>
+     * An empty interface name means any advertisements.
+     * <p>
+     * Advertisements that are returned through {@link handler} can be changed.
+     * The plugin should not reuse the returned advertisement.
+     * <p>
+     *
+     * @param interfaceName an interface name to scan
+     * @param handler       a handler to return updates of matched advertisements.
+     * @throws Exception    if scanning couldn't be started
+     */
+    void startScan(String interfaceName, ScanHandler handler) throws Exception;
+
+    /**
+     * Stops the scanning associated with the given handler.
+     *
+     * @param handler       the handler to stop scanning for.
+     * @throws Exception    if scanning couldn't be started
+     */
+    void stopScan(ScanHandler handler) throws Exception;
+}
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/ScanHandler.java b/lib/src/main/java/io/v/impl/google/lib/discovery/ScanHandler.java
deleted file mode 100644
index ec4268b..0000000
--- a/lib/src/main/java/io/v/impl/google/lib/discovery/ScanHandler.java
+++ /dev/null
@@ -1,19 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.impl.google.lib.discovery;
-
-import io.v.x.ref.lib.discovery.Advertisement;
-
-/**
- * An interface that is passed into a Vanadium Discovery Scan operation that will handle updates.
- */
-public interface ScanHandler {
-    /**
-     * Called when there is a new advertisement or an update to and old advertisement
-     */
-    void handleUpdate(Advertisement advertisement);
-}
-
-
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/UUIDUtil.java b/lib/src/main/java/io/v/impl/google/lib/discovery/UUIDUtil.java
index dce9b76..bd564df 100644
--- a/lib/src/main/java/io/v/impl/google/lib/discovery/UUIDUtil.java
+++ b/lib/src/main/java/io/v/impl/google/lib/discovery/UUIDUtil.java
@@ -1,4 +1,4 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Copyright 2016 The Vanadium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
@@ -7,9 +7,16 @@
 import java.util.UUID;
 
 /**
- * Utility functions for generating UUIDs from interface names and attribute keys.
+ * Utility functions for generating UUIDs from interface names and attribute names.
  */
 public class UUIDUtil {
-    public static native UUID UUIDForInterfaceName(String name);
-    public static native UUID UUIDForAttributeKey(String key);
+    /*
+     * Returns a version 5 UUID for the given interface name.
+     */
+    public static native UUID serviceUUID(String interfaceName);
+
+    /*
+     * returns a version 5 UUID for the given attribute name.
+     */
+    public static native UUID attributeUUID(String name);
 }
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/UpdateImpl.java b/lib/src/main/java/io/v/impl/google/lib/discovery/UpdateImpl.java
new file mode 100644
index 0000000..be4d8ad
--- /dev/null
+++ b/lib/src/main/java/io/v/impl/google/lib/discovery/UpdateImpl.java
@@ -0,0 +1,145 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.impl.google.lib.discovery;
+
+import com.google.common.base.Function;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
+import com.google.common.util.concurrent.Futures;
+import com.google.common.util.concurrent.ListenableFuture;
+
+import java.util.Arrays;
+import java.util.List;
+
+import io.v.v23.VFutures;
+import io.v.v23.context.VContext;
+import io.v.v23.discovery.AdId;
+import io.v.v23.discovery.Advertisement;
+import io.v.v23.discovery.Attachments;
+import io.v.v23.discovery.Attributes;
+import io.v.v23.discovery.Update;
+import io.v.v23.verror.VException;
+import io.v.v23.vom.VomUtil;
+
+import io.v.impl.google.ListenableFutureCallback;
+
+class UpdateImpl implements Update {
+    private final long nativePtr;
+
+    private boolean lost;
+    private Advertisement ad;
+
+    private native void nativeAttachment(
+            long nativePtr, VContext ctx, String name, ListenableFutureCallback<byte[]> callback)
+            throws VException;
+
+    private native void nativeFinalize(long nativePtr);
+
+    private UpdateImpl(long nativePtr, boolean lost, Advertisement ad) {
+        this.nativePtr = nativePtr;
+        this.lost = lost;
+        this.ad = ad;
+    }
+
+    @Override
+    public boolean isLost() {
+        return lost;
+    }
+
+    @Override
+    public AdId getId() {
+        return ad.getId();
+    }
+
+    @Override
+    public String getInterfaceName() {
+        return ad.getInterfaceName();
+    }
+
+    @Override
+    public List<String> getAddresses() {
+        return ImmutableList.copyOf(ad.getAddresses());
+    }
+
+    @Override
+    public String getAttribute(String name) {
+        Attributes attributes = ad.getAttributes();
+        if (attributes != null) {
+            return attributes.get(name);
+        }
+        return null;
+    }
+
+    @Override
+    public ListenableFuture<byte[]> getAttachment(VContext ctx, final String name)
+            throws VException {
+        synchronized (ad) {
+            Attachments attachments = ad.getAttachments();
+            if (attachments != null) {
+                if (attachments.containsKey(name)) {
+                    byte[] data = attachments.get(name);
+                    return Futures.immediateFuture(Arrays.copyOf(data, data.length));
+                }
+            }
+        }
+
+        ListenableFutureCallback<byte[]> callback = new ListenableFutureCallback<>();
+        nativeAttachment(nativePtr, ctx, name, callback);
+        return VFutures.withUserLandChecks(
+                ctx,
+                Futures.transform(
+                        callback.getVanillaFuture(),
+                        new Function<byte[], byte[]>() {
+                            @Override
+                            public byte[] apply(byte[] data) {
+                                synchronized (ad) {
+                                    Attachments attachments = ad.getAttachments();
+                                    if (attachments == null) {
+                                        attachments = new Attachments();
+                                        ad.setAttachments(attachments);
+                                    }
+                                    attachments.put(name, data);
+                                    return Arrays.copyOf(data, data.length);
+                                }
+                            }
+                        }));
+    }
+
+    @Override
+    public Advertisement getAdvertisement() {
+        return new Advertisement(
+                ad.getId(),
+                ad.getInterfaceName(),
+                ImmutableList.copyOf(ad.getAddresses()),
+                new Attributes(ImmutableMap.copyOf(ad.getAttributes())),
+                new Attachments(
+                        Maps.transformValues(
+                                ad.getAttachments(),
+                                new Function<byte[], byte[]>() {
+                                    @Override
+                                    public byte[] apply(byte[] data) {
+                                        return Arrays.copyOf(data, data.length);
+                                    }
+                                })));
+    }
+
+    @Override
+    public String toString() {
+        return String.format(
+                "{%b %s %s %s %s}",
+                lost,
+                VomUtil.bytesToHexString(ad.getId().toPrimitiveArray()),
+                ad.getInterfaceName(),
+                ad.getAddresses(),
+                ad.getAttributes());
+    }
+
+    @Override
+    protected void finalize() throws Throwable {
+        super.finalize();
+        nativeFinalize(nativePtr);
+    }
+}
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/VDiscoveryImpl.java b/lib/src/main/java/io/v/impl/google/lib/discovery/VDiscoveryImpl.java
deleted file mode 100644
index e0b71fb..0000000
--- a/lib/src/main/java/io/v/impl/google/lib/discovery/VDiscoveryImpl.java
+++ /dev/null
@@ -1,59 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.impl.google.lib.discovery;
-
-import com.google.common.util.concurrent.ListenableFuture;
-
-import java.util.List;
-
-import io.v.impl.google.ListenableFutureCallback;
-import io.v.v23.InputChannel;
-import io.v.v23.context.VContext;
-import io.v.v23.discovery.Service;
-import io.v.v23.discovery.Update;
-import io.v.v23.discovery.VDiscovery;
-import io.v.v23.security.BlessingPattern;
-import io.v.v23.verror.VException;
-
-class VDiscoveryImpl implements VDiscovery {
-    private long nativeDiscoveryPtr;
-    private long nativeTriggerPtr;
-
-    private native void nativeAdvertise(
-            long nativeDiscoveryPtr, long nativeTriggerPtr, VContext ctx, Service service,
-            List<BlessingPattern> visibility,
-            ListenableFutureCallback<ListenableFuture<Void>> startCallback,
-            ListenableFutureCallback<Void> doneCallback);
-    private native InputChannel<Update> nativeScan(
-            long nativeDiscoveryPtr, VContext ctx, String query) throws VException;
-    private native void nativeFinalize(long nativeDiscoveryPtr, long nativeTriggerPtr);
-
-    private VDiscoveryImpl(long nativeDiscoveryPtr, long nativeTriggerPtr) {
-        this.nativeDiscoveryPtr = nativeDiscoveryPtr;
-        this.nativeTriggerPtr = nativeTriggerPtr;
-    }
-    @Override
-    public ListenableFuture<ListenableFuture<Void>> advertise(VContext ctx, Service service,
-                                                              List<BlessingPattern> visibility) {
-        ListenableFutureCallback<ListenableFuture<Void>> startCallback = new ListenableFutureCallback<>();
-        ListenableFutureCallback<Void> doneCallback = new ListenableFutureCallback<>();
-        nativeAdvertise(nativeDiscoveryPtr, nativeTriggerPtr, ctx, service, visibility,
-                startCallback, doneCallback);
-        return startCallback.getFuture(ctx);
-    }
-    @Override
-    public InputChannel<Update> scan(VContext ctx, String query) {
-        try {
-            return nativeScan(nativeDiscoveryPtr, ctx, query);
-        } catch (VException e) {
-            throw new RuntimeException("Couldn't start discovery scan()", e);
-        }
-    }
-    @Override
-    protected void finalize() throws Throwable {
-        super.finalize();
-        nativeFinalize(nativeDiscoveryPtr, nativeTriggerPtr);
-    }
-}
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/VScanner.java b/lib/src/main/java/io/v/impl/google/lib/discovery/VScanner.java
deleted file mode 100644
index ab5ac8f..0000000
--- a/lib/src/main/java/io/v/impl/google/lib/discovery/VScanner.java
+++ /dev/null
@@ -1,28 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.impl.google.lib.discovery;
-
-/**
- * Stores an interfance name and a {@link ScanHandler}.
- */
-public class VScanner {
-    private String interfaceName;
-    private ScanHandler handler;
-
-    public VScanner(String interfaceName, ScanHandler handler) {
-        this.interfaceName = interfaceName;
-        this.handler = handler;
-    }
-
-    /** Returns the interface name */
-    public String getInterfaceName() {
-        return interfaceName;
-    }
-
-    /** Returns the {@link ScanHandler} */
-    public ScanHandler getHandler() {
-        return handler;
-    }
-}
diff --git a/lib/src/main/java/io/v/impl/google/lib/discovery/ble/BleAdvertisementConverter.java b/lib/src/main/java/io/v/impl/google/lib/discovery/ble/BleAdvertisementConverter.java
deleted file mode 100644
index 745e64c..0000000
--- a/lib/src/main/java/io/v/impl/google/lib/discovery/ble/BleAdvertisementConverter.java
+++ /dev/null
@@ -1,161 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.impl.google.lib.discovery.ble;
-
-import java.io.ByteArrayOutputStream;
-import java.io.IOException;
-import java.nio.charset.Charset;
-import java.util.Arrays;
-import java.util.HashMap;
-import java.util.List;
-import java.util.logging.Logger;
-import java.util.Map;
-import java.util.UUID;
-
-import io.v.impl.google.lib.discovery.EncodingUtil;
-import io.v.impl.google.lib.discovery.UUIDUtil;
-import io.v.x.ref.lib.discovery.Advertisement;
-import io.v.v23.discovery.Attachments;
-import io.v.v23.discovery.Attributes;
-import io.v.v23.discovery.Service;
-import io.v.x.ref.lib.discovery.EncryptionAlgorithm;
-import io.v.x.ref.lib.discovery.EncryptionKey;
-import io.v.x.ref.lib.discovery.plugins.ble.Constants;
-
-/**
- * Converts from {@link Advertisement} to the gatt services and vice-versa.
- */
-public class BleAdvertisementConverter {
-    private static final Logger logger = Logger.getLogger(BleAdvertisementConverter.class.getName());
-    private static final Charset enc = Charset.forName("UTF-8");
-
-    /**
-     * Converts from {@link Advertisement} to the ble representation.
-     *
-     * @return map of Characteristic UUIDs to their values.
-     * @throws IOException
-     */
-    public static Map<UUID, byte[]> vAdvertismentToBleAttr(Advertisement adv)
-            throws IOException {
-        Map<UUID, byte[]> bleAttr = new HashMap<>();
-        Service service = adv.getService();
-        bleAttr.put(UUID.fromString(Constants.INSTANCE_ID_UUID),
-                    service.getInstanceId().getBytes(enc));
-        bleAttr.put(UUID.fromString(Constants.INTERFACE_NAME_UUID),
-                    service.getInterfaceName().getBytes(enc));
-        bleAttr.put(UUID.fromString(Constants.ADDRS_UUID),
-                    EncodingUtil.packAddresses(service.getAddrs()));
-        bleAttr.put(UUID.fromString(Constants.HASH_UUID), adv.getHash());
-
-        String instanceName = service.getInstanceName();
-        if (instanceName != null && !instanceName.isEmpty()) {
-            bleAttr.put(UUID.fromString(Constants.INSTANCE_NAME_UUID),
-                        instanceName.getBytes(enc));
-        }
-        for (Map.Entry<String, String> entry : service.getAttrs().entrySet()) {
-            String key = entry.getKey();
-            String data = key + "=" + entry.getValue();
-            bleAttr.put(UUIDUtil.UUIDForAttributeKey(key), data.getBytes(enc));
-        }
-        for (Map.Entry<String, byte[]> entry : service.getAttachments().entrySet()) {
-            String key = Constants.ATTACHMENT_NAME_PREFIX + entry.getKey();
-            byte[] keyInBytes = key.getBytes(enc);
-            byte[] value = entry.getValue();
-            ByteArrayOutputStream buf =
-                new ByteArrayOutputStream(keyInBytes.length + 1 + value.length);
-            buf.write(keyInBytes);
-            buf.write((byte)'=');
-            buf.write(value);
-            bleAttr.put(UUIDUtil.UUIDForAttributeKey(key), buf.toByteArray());
-        }
-        if (adv.getEncryptionAlgorithm().getValue() != 0) {
-            bleAttr.put(UUID.fromString(Constants.ENCRYPTION_UUID),
-                        EncodingUtil.packEncryptionKeys(adv.getEncryptionAlgorithm().getValue(),
-                                                        adv.getEncryptionKeys()));
-        }
-        List<String> dirAddrs = adv.getDirAddrs();
-        if (dirAddrs != null && !dirAddrs.isEmpty()) {
-            bleAttr.put(UUID.fromString(Constants.DIR_ADDRS_UUID),
-                        EncodingUtil.packAddresses(dirAddrs));
-        }
-        return bleAttr;
-    }
-
-    /**
-     * Converts from map of characteristic {@link UUID}s -> values to an {@link Advertisement}.
-     *
-     * @param bleAttr      map of characteristic uuids to their values
-     * @return             Vanadium advertisement based on characteristics
-     * @throws IOException
-     */
-    public static Advertisement bleAttrToVAdvertisement(Map<UUID, byte[]> bleAttr)
-            throws IOException {
-        String instanceId = null;
-        String instanceName = null;
-        String interfaceName = null;
-        List<String> addrs = null;
-        Map<String, String> attrs = new HashMap<String, String>();
-        Map<String, byte[]> attachments = new HashMap<String, byte[]>();
-        int encryptionAlgo = 0;
-        List<EncryptionKey> encryptionKeys = null;
-        byte[] hash = null;
-        List<String> dirAddrs = null;
-
-        for (Map.Entry<UUID, byte[]> entry : bleAttr.entrySet()) {
-            String uuidKey = entry.getKey().toString();
-            byte[] data = entry.getValue();
-            if (uuidKey.equals(Constants.INSTANCE_ID_UUID)) {
-                instanceId = new String(data, enc);
-            } else if (uuidKey.equals(Constants.INSTANCE_NAME_UUID)) {
-                instanceName = new String(data, enc);
-            } else if (uuidKey.equals(Constants.INTERFACE_NAME_UUID)) {
-                interfaceName = new String(data, enc);
-            } else if (uuidKey.equals(Constants.ADDRS_UUID)) {
-                addrs = EncodingUtil.unpackAddresses(data);
-            } else if (uuidKey.equals(Constants.ENCRYPTION_UUID)) {
-                EncodingUtil.KeysAndAlgorithm res = EncodingUtil.unpackEncryptionKeys(data);
-                encryptionAlgo = res.getEncryptionAlgorithm();
-                encryptionKeys = res.getKeys();
-            } else if (uuidKey.equals(Constants.HASH_UUID)) {
-                hash = data;
-            } else if (uuidKey.equals(Constants.DIR_ADDRS_UUID)) {
-                dirAddrs = EncodingUtil.unpackAddresses(data);
-            } else {
-                int index = -1;
-                for (int i = 0; i < data.length; i++) {
-                  if (data[i] == (byte)'=') {
-                    index = i;
-                    break;
-                  }
-                }
-                if (index < 0) {
-                    logger.severe("Failed to parse data for " + uuidKey);
-                    continue;
-                }
-                String key = new String(data, 0, index, enc);
-                if (key.startsWith(Constants.ATTACHMENT_NAME_PREFIX)) {
-                  key = key.substring(Constants.ATTACHMENT_NAME_PREFIX.length());
-                  byte[] value = Arrays.copyOfRange(data, index + 1, data.length);
-                  attachments.put(key, value);
-                } else {
-                  String value = new String(data, index + 1, data.length - index - 1, enc);
-                  attrs.put(key, value);
-                }
-            }
-        }
-        return new Advertisement(
-                new Service(instanceId,
-                            instanceName,
-                            interfaceName,
-                            new Attributes(attrs),
-                            addrs,
-                            new Attachments(attachments)),
-                new EncryptionAlgorithm(encryptionAlgo),
-                encryptionKeys,
-                hash,
-                dirAddrs,
-                false);
-    }
-}
diff --git a/lib/src/main/java/io/v/impl/google/rt/VRuntimeImpl.java b/lib/src/main/java/io/v/impl/google/rt/VRuntimeImpl.java
index 0a40acf..eaf229f 100644
--- a/lib/src/main/java/io/v/impl/google/rt/VRuntimeImpl.java
+++ b/lib/src/main/java/io/v/impl/google/rt/VRuntimeImpl.java
@@ -18,7 +18,7 @@
 import io.v.v23.Options;
 import io.v.v23.VRuntime;
 import io.v.v23.context.VContext;
-import io.v.v23.discovery.VDiscovery;
+import io.v.v23.discovery.Discovery;
 import io.v.v23.namespace.Namespace;
 import io.v.v23.rpc.Callback;
 import io.v.v23.rpc.Client;
@@ -56,7 +56,7 @@
             throws VException;
     private static native ListenSpec nativeGetListenSpec(VContext ctx) throws VException;
 
-    private static native VDiscovery nativeNewDiscovery(VContext ctx) throws VException;
+    private static native Discovery nativeNewDiscovery(VContext ctx) throws VException;
 
     // Attaches a server to the given context.  Used by this class and other classes
     // that natively create a server.
@@ -161,7 +161,7 @@
         }
     }
     @Override
-    public VDiscovery newDiscovery(VContext ctx) throws VException {
+    public Discovery newDiscovery(VContext ctx) throws VException {
         return nativeNewDiscovery(ctx);
     }
     @Override
diff --git a/lib/src/main/java/io/v/v23/V.java b/lib/src/main/java/io/v/v23/V.java
index 9dce6b1..2f5d40a 100644
--- a/lib/src/main/java/io/v/v23/V.java
+++ b/lib/src/main/java/io/v/v23/V.java
@@ -18,7 +18,7 @@
 
 import io.v.impl.google.rt.VRuntimeImpl;
 import io.v.v23.context.VContext;
-import io.v.v23.discovery.VDiscovery;
+import io.v.v23.discovery.Discovery;
 import io.v.v23.namespace.Namespace;
 import io.v.v23.rpc.Client;
 import io.v.v23.rpc.Dispatcher;
@@ -450,12 +450,12 @@
     }
 
     /**
-     * Returns a new {@link VDiscovery} instance.
+     * Returns a new {@link Discovery} instance.
      *
      * @param  ctx             current context
      * @throws VException      if a new discovery instance cannot be created
      */
-    public static VDiscovery newDiscovery(VContext ctx) throws VException {
+    public static Discovery newDiscovery(VContext ctx) throws VException {
         return getRuntime(ctx).newDiscovery(ctx);
     }
 
diff --git a/lib/src/main/java/io/v/v23/VRuntime.java b/lib/src/main/java/io/v/v23/VRuntime.java
index 19f425a..76a4494 100644
--- a/lib/src/main/java/io/v/v23/VRuntime.java
+++ b/lib/src/main/java/io/v/v23/VRuntime.java
@@ -5,7 +5,7 @@
 package io.v.v23;
 
 import io.v.v23.context.VContext;
-import io.v.v23.discovery.VDiscovery;
+import io.v.v23.discovery.Discovery;
 import io.v.v23.namespace.Namespace;
 import io.v.v23.rpc.Client;
 import io.v.v23.rpc.Dispatcher;
@@ -198,10 +198,10 @@
     VContext getContext();
 
     /**
-     * Returns a new {@code VDiscovery} instance.
+     * Returns a new {@code Discovery} instance.
      *
      * @param  ctx             current context
      * @throws VException      if a new discovery instance cannot be created
      */
-    VDiscovery newDiscovery(VContext ctx) throws VException;
+    Discovery newDiscovery(VContext ctx) throws VException;
 }
diff --git a/lib/src/main/java/io/v/v23/discovery/Discovery.java b/lib/src/main/java/io/v/v23/discovery/Discovery.java
new file mode 100644
index 0000000..a6f846e
--- /dev/null
+++ b/lib/src/main/java/io/v/v23/discovery/Discovery.java
@@ -0,0 +1,82 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.v23.discovery;
+
+import com.google.common.util.concurrent.ListenableFuture;
+
+import java.util.List;
+
+import javax.annotation.CheckReturnValue;
+
+import io.v.v23.InputChannel;
+import io.v.v23.context.VContext;
+import io.v.v23.security.BlessingPattern;
+import io.v.v23.verror.VException;
+
+/**
+ * An interface for discovery operations; it is the client-side library for the discovery service.
+ */
+public interface Discovery {
+    /**
+     * Broadcasts the advertisement to be discovered by {@link #scan scan} operations.
+     * <p>
+     * Visibility is used to limit the principals that can see the advertisement. An
+     * empty list means that there are no restrictions on visibility (i.e, equivalent
+     * to {@link io.v.v23.security.Constants#ALL_PRINCIPALS}).
+     * <p>
+     * If {@link Advertisement#id} is not specified, a random unique a random unique
+     * identifier will be assigned. Any change to service will not be applied after
+     * advertising starts.
+     * <p>
+     * It is an error to have simultaneously active advertisements for two identical
+     * instances (i.e., {@link Advertisement#id}s).
+     * <p>
+     * Advertising will continue until the context is canceled or exceeds its deadline
+     * and the returned {@link ListenableFuture} will complete once it stops.
+     * <p>
+     * The returned future is guaranteed to be executed on an {@link java.util.concurrent.Executor}
+     * specified in {@code context} (see {@link io.v.v23.V#withExecutor}).
+     * <p>
+     *
+     * @param context     a context that will be used to stop advertising
+     * @param ad          an advertisement to advertises; this may be update with a random unique
+     *                    identifier if ad.id is not specified.
+     * @param visibility  a set of blessing patterns for whom this advertisement is meant; any entity
+     *                    not matching a pattern here won't know what the advertisement is
+     * @return            a new {@link ListenableFuture} that completes once advertising stops
+     * @throws VException if advertising couldn't be started
+     */
+    @CheckReturnValue
+    ListenableFuture<Void> advertise(
+            VContext context, Advertisement ad, List<BlessingPattern> visibility) throws VException;
+
+    /**
+     * Scans advertisements that match the query and returns an {@link InputChannel} of updates.
+     * <p>
+     * Scan excludes the advertisements that are advertised from the same discovery instance.
+     * <p>
+     * The query is a {@code WHERE} expression of a {@code syncQL} query against advertisements,
+     * where keys are {@link Advertisement#id}s and values are {@link Advertisement}s.
+     * <p>
+     * Examples:
+     * <p><blockquote><pre>
+     *     v.InstanceName = "v.io/i"
+     *     v.InstanceName = "v.io/i" AND v.Attributes["a"] = "v"
+     *     v.Attributes["a"] = "v1" OR v.Attributes["a"] = "v2"
+     * </pre></blockquote><p>
+     * You can find the {@code SyncQL} tutorial at:
+     *     https://vanadium.github.io/tutorials/syncbase/syncql-tutorial.html
+     * <p>
+     * Scanning will continue until the context is canceled or exceeds its deadline. Note that
+     * to avoid memory leaks, the caller should drain the channel after cancelling the context.
+     *
+     * @param context     a context that will be used to stop scanning
+     * @param query       a WHERE expression of {@code syncQL query} against scanned advertisements
+     * @return            a (potentially-infite) {@link InputChannel} of updates
+     * @throws VException if scanning couldn't be started
+     */
+    @CheckReturnValue
+    InputChannel<Update> scan(VContext context, String query) throws VException;
+}
diff --git a/lib/src/main/java/io/v/v23/discovery/Update.java b/lib/src/main/java/io/v/v23/discovery/Update.java
new file mode 100644
index 0000000..fa29e8a
--- /dev/null
+++ b/lib/src/main/java/io/v/v23/discovery/Update.java
@@ -0,0 +1,82 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.v23.discovery;
+
+import com.google.common.util.concurrent.ListenableFuture;
+
+import java.util.List;
+
+import javax.annotation.CheckReturnValue;
+
+import io.v.v23.context.VContext;
+import io.v.v23.verror.VException;
+
+/**
+ * Update is the interface for an update from Vanadium discovery scanning.
+ */
+public interface Update {
+    /**
+     * Returns true if this update represents a service that is lost during scan.
+     */
+    boolean isLost();
+
+    /**
+     * Returns the universal unique identifier of the discovered advertisement.
+     */
+    AdId getId();
+
+    /**
+     * Returns the interface name of the service.
+     */
+    String getInterfaceName();
+
+    /**
+     * Returns the addresses (vanadium object names) that the service is served on.
+     */
+    List<String> getAddresses();
+
+    /**
+     * Returns the named attribute of the service.
+     * <p>
+     * Returns null if the named attribute does not exist.
+     *
+     * @param name  the attachment name
+     * @return      the data of the named attribute
+     */
+    String getAttribute(String name);
+
+    /**
+     * Returns a new {@link ListenableFuture} whose result is the data for the named attachment.
+     * <p>
+     * The returned future completes immediately if the named attachment is already available;
+     * otherwise it completes once attachment fetching over RPC is done.
+     * <p>
+     * The result of future will be null if the named attachment does not exist.
+     * <p>
+     * The returned future is guaranteed to be executed on an {@link java.util.concurrent.Executor}
+     * specified in {@code context} (see {@link io.v.v23.V#withExecutor}).
+     * <p>
+     * The returned future will fail if the row doesn't exist.
+     * <p>
+     * The returned {@link ListenableFuture} will fail if there was an error fetching the
+     * attachments or {@code context} gets canceled.
+     *
+     * @param context     a context that will be used to stop fetching; the fetching will end
+     *                    when the context is cancelled or timed out
+     * @param name        the attachment name
+     * @return            a new {@link ListenableFuture} whose result is the data for the named
+     *                    attachment
+     * @throws VException if attachment couldn't be fetched
+     */
+    @CheckReturnValue
+    ListenableFuture<byte[]> getAttachment(VContext context, String name) throws VException;
+
+    /**
+     * Returns the advertisement that this update corresponds to.
+     * <p>
+     * The returned advertisement may not include all attachments.
+     */
+    Advertisement getAdvertisement();
+}
diff --git a/lib/src/main/java/io/v/v23/discovery/VDiscovery.java b/lib/src/main/java/io/v/v23/discovery/VDiscovery.java
deleted file mode 100644
index 234e952..0000000
--- a/lib/src/main/java/io/v/v23/discovery/VDiscovery.java
+++ /dev/null
@@ -1,87 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.v23.discovery;
-
-import com.google.common.util.concurrent.ListenableFuture;
-
-import java.util.List;
-
-import javax.annotation.CheckReturnValue;
-
-import io.v.v23.InputChannel;
-import io.v.v23.context.VContext;
-import io.v.v23.security.BlessingPattern;
-
-/**
- * An interface for discovery operations; it is the client-side library for the discovery service.
- */
-public interface VDiscovery {
-    /**
-     * Advertises the service to be discovered by {@link #scan scan} implementations.
-     * <p>
-     * Returns a new {@link ListenableFuture} that completes once advertising starts.  The result
-     * of this future is a new {@link ListenableFuture} that completes once advertising stops.
-     * Once successfully started, advertising will continue until the context is canceled or
-     * exceeds its deadline.  Note that the future signaling a completion of advertising can
-     * never fail.
-     * <p>
-     * Visibility is used to limit the principals that can see the advertisement. An
-     * empty list means that there are no restrictions on visibility (i.e, equivalent
-     * to {@link io.v.v23.security.Constants#ALL_PRINCIPALS}).
-     * <p>
-     * If {@link Service#instanceId} is not specified, a random 128 bit (16 byte) {@code UUID} will
-     * be assigned to it once advertising starts.  Any change to service will not be applied after
-     * advertising starts.
-     * <p>
-     * It is an error to have simultaneously active advertisements for two identical
-     * instances (i.e., {@link Service#instanceId}s).
-     * <p>
-     * The returned future is guaranteed to be executed on an {@link java.util.concurrent.Executor}
-     * specified in {@code context} (see {@link io.v.v23.V#withExecutor}).
-     * <p>
-     * The returned future will fail with {@link java.util.concurrent.CancellationException} if
-     * {@code context} gets canceled.
-     *
-     * @param context    a context that will be used to stop the advertisement; the advertisement
-     *                   will end when the context is cancelled or timed out
-     * @param service    the service with the attributes to advertises; this may be update with
-     *                   a random unique identifier if service.instanceId is not specified.
-     * @param visibility a set of blessing patterns for whom this advertisement is meant; any entity
-     *                   not matching a pattern here won't know what the advertisement is
-     * @return           a new {@link ListenableFuture} that completes once advertising starts;
-     *                   the result of this future is a second {@link ListenableFuture} that
-     *                   completes once advertising stops
-     */
-    @CheckReturnValue
-    ListenableFuture<ListenableFuture<Void>> advertise(
-            VContext context, Service service, List<BlessingPattern> visibility);
-
-    /**
-     * Scans services that match the query and returns an {@link InputChannel} of updates.
-     * <p>
-     * Scanning will continue until the context is canceled or exceeds its deadline.
-     * <p>
-     * Scanning will exclude the services that are advertised from the same VDiscovery instance.
-     * <p>
-     * The query is a {@code WHERE} expression of a {@code syncQL} query against advertised services,
-     * where keys are {@link Service#instanceId}s and values are {@link Service}s.
-     * <p>
-     * Examples:
-     * <p><blockquote><pre>
-     *     v.InstanceName = "v.io/i"
-     *     v.InstanceName = "v.io/i" AND v.Attrs["a"] = "v"
-     *     v.Attrs["a"] = "v1" OR v.Attrs["a"] = "v2"
-     * </pre></blockquote><p>
-     * You can find the {@code SyncQL} tutorial at:
-     *     https://vanadium.github.io/tutorials/syncbase/syncql-tutorial.html
-     *
-     * @param context  a context that will be used to stop the scan;  scan will end when the context
-     *                 is cancelled or timed out
-     * @param query    a WHERE expression of {@code syncQL query} against scanned services
-     * @return         a (potentially-infite) {@link InputChannel} of updates
-     */
-    @CheckReturnValue
-    InputChannel<Update> scan(VContext context, String query);
-}
diff --git a/lib/src/test/java/io/v/impl/google/lib/discovery/DeviceCacheTest.java b/lib/src/test/java/io/v/impl/google/lib/discovery/DeviceCacheTest.java
deleted file mode 100644
index ac53f6d..0000000
--- a/lib/src/test/java/io/v/impl/google/lib/discovery/DeviceCacheTest.java
+++ /dev/null
@@ -1,285 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.impl.google.lib.discovery;
-
-import java.util.Arrays;
-import java.util.HashSet;
-import java.util.Set;
-
-import junit.framework.TestCase;
-
-import org.joda.time.DateTimeUtils;
-import org.joda.time.Duration;
-
-import io.v.v23.discovery.Service;
-
-import io.v.x.ref.lib.discovery.Advertisement;
-import io.v.x.ref.lib.discovery.EncryptionAlgorithm;
-
-/**
- * Tests for {@link DeviceCache}.
- */
-public class DeviceCacheTest extends TestCase {
-    private abstract class CountingHandler implements ScanHandler {
-        protected int mNumCalls = 0;
-
-        @Override
-        public void handleUpdate(Advertisement adv) {}
-    }
-
-    public void tearDown() {
-        DateTimeUtils.setCurrentMillisSystem();
-    }
-
-    public void testSaveDeveice() {
-        DeviceCache cache = new DeviceCache(new Duration(1000 * 60 * 60));
-        // The advertisements here are not relevant since we are just checking
-        // the seen stamp function.
-        Set<Advertisement> advs = new HashSet<>();
-        long stamp = 10001;
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-        cache.saveDevice(stamp, advs, "newDevice");
-        assertTrue(cache.haveSeenStamp(stamp, "newDevice"));
-        cache.shutdownCache();
-    }
-
-    public void testSaveDeviceWithDifferentStampCode() {
-        DeviceCache cache = new DeviceCache(new Duration(1000 * 60 * 60));
-        // The advertisements here are not relevant since we are just checking
-        // the seen stamp function.
-        Set<Advertisement> advs = new HashSet<>();
-        long stamp = 10001;
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-        cache.saveDevice(stamp, advs, "newDevice");
-        assertTrue(cache.haveSeenStamp(stamp, "newDevice"));
-        cache.saveDevice(stamp + 1, advs, "newDevice");
-        assertTrue(cache.haveSeenStamp(stamp + 1, "newDevice"));
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-        cache.shutdownCache();
-    }
-
-    public void testAddingScannerBeforeSavingDevice() {
-        DeviceCache cache = new DeviceCache(new Duration(1000 * 60 * 60));
-        Set<Advertisement> advs = new HashSet<>();
-        long stamp = 10001;
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-
-        Service service1 = new Service();
-        service1.setInterfaceName("randomInterface");
-        final Advertisement adv1 = new Advertisement(
-            service1, new EncryptionAlgorithm(0), null,
-            new byte[]{1, 2, 3}, Arrays.asList("dir1", "dir2"), false);
-        advs.add(adv1);
-
-        CountingHandler handler = new CountingHandler() {
-            @Override
-            public void handleUpdate(Advertisement advertisement) {
-                assertEquals(adv1, advertisement);
-                assertEquals(mNumCalls, 0);
-                mNumCalls++;
-            }
-        };
-
-        cache.addScanner(new VScanner(service1.getInterfaceName(), handler));
-
-        Service service2 = new Service();
-        service2.setInterfaceName("randomInterface2");
-        Advertisement adv2 = new Advertisement(service2, new EncryptionAlgorithm(0), null, null, null, false);
-        advs.add(adv2);
-
-        cache.saveDevice(stamp, advs, "newDevice");
-
-        // Make sure that the handler is called;
-        assertEquals(1, handler.mNumCalls);
-        cache.shutdownCache();
-    }
-
-    public void testAddingScannerAfterSavingDevice() {
-        DeviceCache cache = new DeviceCache(new Duration(1000 * 60 * 60));
-        Set<Advertisement> advs = new HashSet<>();
-        long stamp = 10001;
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-
-        Service service1 = new Service();
-        service1.setInterfaceName("randomInterface");
-        final Advertisement adv1 = new Advertisement(service1, new EncryptionAlgorithm(0), null, null, null, false);
-
-        advs.add(adv1);
-
-        CountingHandler handler = new CountingHandler() {
-            @Override
-            public void handleUpdate(Advertisement advertisement) {
-                assertEquals(adv1, advertisement);
-                assertEquals(mNumCalls, 0);
-                mNumCalls++;
-            }
-        };
-
-        Service service2 = new Service();
-        service1.setInterfaceName("randomInterface2");
-        Advertisement adv2 = new Advertisement(service2, new EncryptionAlgorithm(0), null, null, null, false);
-        advs.add(adv2);
-        cache.saveDevice(stamp, advs, "newDevice");
-
-        cache.addScanner(new VScanner(service1.getInterfaceName(), handler));
-
-        // Make sure that the handler is called;
-        assertEquals(1, handler.mNumCalls);
-        cache.shutdownCache();
-    }
-
-    public void testRemovingAnAdvertisementCallsHandler() {
-        DeviceCache cache = new DeviceCache(new Duration(1000 * 60 * 60));
-        Set<Advertisement> advs = new HashSet<>();
-        long stamp = 10001;
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-
-        Service service1 = new Service();
-        service1.setInterfaceName("randomInterface");
-        final Advertisement adv1 = new Advertisement(service1, new EncryptionAlgorithm(0), null, null, null, false);
-        advs.add(adv1);
-
-        CountingHandler handler = new CountingHandler() {
-            @Override
-            public void handleUpdate(Advertisement advertisement) {
-                // The first call should be an add and the second call should be
-                // a remove.
-                if (mNumCalls == 0) {
-                    assertEquals(adv1, advertisement);
-                } else {
-                    Advertisement removed = new Advertisement(
-                        adv1.getService(), adv1.getEncryptionAlgorithm(), adv1.getEncryptionKeys(),
-                        adv1.getHash(), adv1.getDirAddrs(), true);
-                    assertEquals(removed, advertisement);
-                }
-                mNumCalls++;
-            }
-        };
-
-        cache.addScanner(new VScanner(service1.getInterfaceName(), handler));
-
-        Service service2 = new Service();
-        service2.setInterfaceName("randomInterface2");
-        Advertisement adv2 = new Advertisement(service2, new EncryptionAlgorithm(0), null, null, null, false);
-        advs.add(adv2);
-
-        cache.saveDevice(stamp, advs, "newDevice");
-
-        Set<Advertisement> newAdvs = new HashSet<>();
-        newAdvs.add(adv2);
-
-        cache.saveDevice(10002, newAdvs, "newDevice");
-
-        // Make sure that the handler is called;
-        assertEquals(2, handler.mNumCalls);
-        cache.shutdownCache();
-    }
-
-    public void testAddingtheSameAdvertisementDoesNotCallsHandler() {
-        DeviceCache cache = new DeviceCache(new Duration(1000 * 60 * 60));
-        Set<Advertisement> advs = new HashSet<>();
-        long stamp = 10001;
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-
-        Service service1 = new Service();
-        service1.setInterfaceName("randomInterface");
-        final Advertisement adv1 = new Advertisement(service1, new EncryptionAlgorithm(0), null, null, null, false);
-        advs.add(adv1);
-
-        CountingHandler handler = new CountingHandler() {
-            @Override
-            public void handleUpdate(Advertisement advertisement) {
-                assertEquals(adv1, advertisement);
-                mNumCalls++;
-            }
-        };
-
-        cache.addScanner(new VScanner(service1.getInterfaceName(), handler));
-
-        Service service2 = new Service();
-        service2.setInterfaceName("randomInterface2");
-        Advertisement adv2 = new Advertisement(service2, new EncryptionAlgorithm(0), null, null, null, false);
-        advs.add(adv2);
-
-        cache.saveDevice(stamp, advs, "newDevice");
-
-        Set<Advertisement> advs2 = new HashSet<>(advs);
-        cache.saveDevice(10002, advs2, "newDevice");
-
-        // Make sure that the handler is called;
-        assertEquals(1, handler.mNumCalls);
-        cache.shutdownCache();
-    }
-
-    public void testCacheEvictionCallsHandler() {
-        DeviceCache cache = new DeviceCache(new Duration(1000 * 60 * 60));
-        Set<Advertisement> advs = new HashSet<>();
-        long stamp = 10001;
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-
-        Service service1 = new Service();
-        service1.setInterfaceName("randomInterface");
-        final Advertisement adv1 = new Advertisement(service1, new EncryptionAlgorithm(0), null, null, null, false);
-        advs.add(adv1);
-
-        CountingHandler handler = new CountingHandler() {
-            @Override
-            public void handleUpdate(Advertisement advertisement) {
-                // The first call should be an add and the second call should be
-                // a remove.
-                if (mNumCalls == 0) {
-                    assertEquals(adv1, advertisement);
-                } else {
-                    Advertisement removed = new Advertisement(
-                            adv1.getService(), adv1.getEncryptionAlgorithm(), adv1.getEncryptionKeys(),
-                            adv1.getHash(), adv1.getDirAddrs(), true);
-                    assertEquals(removed, advertisement);
-                }
-                mNumCalls++;
-            }
-        };
-
-        long cacheTime = DateTimeUtils.currentTimeMillis();
-        cache.saveDevice(stamp, advs, "newDevice");
-        cache.addScanner(new VScanner(service1.getInterfaceName(), handler));
-
-        DateTimeUtils.setCurrentMillisFixed(cacheTime + 1000 * 60 * 61);
-        cache.removeStaleEntries();
-        // Make sure that the handler is called;
-        assertEquals(2, handler.mNumCalls);
-        cache.shutdownCache();
-    }
-
-    public void testCacheEvictionClearsAllState() {
-        DeviceCache cache = new DeviceCache(new Duration(1000 * 60 * 60));
-        Set<Advertisement> advs = new HashSet<>();
-        long stamp = 10001;
-        assertFalse(cache.haveSeenStamp(stamp, "newDevice"));
-
-        Service service1 = new Service();
-        service1.setInterfaceName("randomInterface");
-        final Advertisement adv1 = new Advertisement(service1, new EncryptionAlgorithm(0), null, null, null, false);
-        advs.add(adv1);
-
-        CountingHandler handler = new CountingHandler() {
-            @Override
-            public void handleUpdate(Advertisement advertisement) {
-               mNumCalls++;
-            }
-        };
-
-        long cacheTime = DateTimeUtils.currentTimeMillis();
-        cache.saveDevice(stamp, advs, "newDevice");
-
-        DateTimeUtils.setCurrentMillisFixed(cacheTime + 1000 * 60 * 61);
-        cache.removeStaleEntries();
-
-        cache.addScanner(new VScanner(service1.getInterfaceName(), handler));
-
-        // Make sure that the handler is never called.
-        assertEquals(0, handler.mNumCalls);
-        cache.shutdownCache();
-    }
-}
diff --git a/lib/src/test/java/io/v/impl/google/lib/discovery/DiscoveryTest.java b/lib/src/test/java/io/v/impl/google/lib/discovery/DiscoveryTest.java
new file mode 100644
index 0000000..ef853c1
--- /dev/null
+++ b/lib/src/test/java/io/v/impl/google/lib/discovery/DiscoveryTest.java
@@ -0,0 +1,70 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.impl.google.lib.discovery;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.common.util.concurrent.ListenableFuture;
+
+import java.util.Arrays;
+import java.util.Iterator;
+
+import junit.framework.TestCase;
+
+import io.v.v23.V;
+import io.v.v23.context.VContext;
+import io.v.v23.discovery.Discovery;
+import io.v.v23.discovery.Advertisement;
+import io.v.v23.discovery.Attributes;
+import io.v.v23.discovery.Attachments;
+import io.v.v23.discovery.Update;
+import io.v.v23.VFutures;
+import io.v.v23.verror.VException;
+import io.v.v23.InputChannel;
+import io.v.v23.InputChannels;
+
+import static com.google.common.truth.Truth.assertThat;
+import static io.v.impl.google.lib.discovery.DiscoveryTestUtil.assertThat;
+
+/**
+ * Tests for {@link Discovery} implementation.
+ */
+public class DiscoveryTest extends TestCase {
+    public void testBasicTest() throws VException {
+        VContext ctx = DiscoveryTestUtil.withMockDiscovery();
+        Discovery d1 = V.newDiscovery(ctx);
+
+        Advertisement ad = new Advertisement();
+        ad.setInterfaceName("v.io/v23/a");
+        ad.setAddresses(Arrays.asList("/h1:123/x"));
+        ad.setAttributes(new Attributes(ImmutableMap.of("a", "v")));
+        ad.setAttachments(new Attachments(ImmutableMap.of("a", new byte[] {1, 2, 3})));
+
+        VContext advCtx = ctx.withCancel();
+        ListenableFuture<Void> advFuture = d1.advertise(advCtx, ad, null);
+
+        Discovery d2 = V.newDiscovery(ctx);
+        VContext scanCtx = ctx.withCancel();
+
+        InputChannel<Update> updateCh = d2.scan(scanCtx, "");
+        Iterator<Update> it = InputChannels.asIterable(updateCh).iterator();
+
+        assertThat(it.hasNext()).isTrue();
+        Update update = it.next();
+        assertThat(update.isLost()).isFalse();
+        assertThat(update).isEqualTo(ctx, ad);
+
+        advCtx.cancel();
+        VFutures.sync(advFuture);
+
+        assertThat(it.hasNext()).isTrue();
+        update = it.next();
+        assertThat(update.isLost()).isTrue();
+        assertThat(update).isEqualTo(ctx, ad);
+        assertThat(update.getAdvertisement()).isEqualTo(ad);
+
+        scanCtx.cancel();
+        assertThat(it.hasNext()).isFalse();
+    }
+}
diff --git a/lib/src/test/java/io/v/impl/google/lib/discovery/DiscoveryTestUtil.java b/lib/src/test/java/io/v/impl/google/lib/discovery/DiscoveryTestUtil.java
new file mode 100644
index 0000000..3355097
--- /dev/null
+++ b/lib/src/test/java/io/v/impl/google/lib/discovery/DiscoveryTestUtil.java
@@ -0,0 +1,257 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.impl.google.lib.discovery;
+
+import com.google.common.base.Equivalence;
+import com.google.common.base.Function;
+import com.google.common.base.Objects;
+import com.google.common.collect.ImmutableMultiset;
+import com.google.common.collect.FluentIterable;
+import com.google.common.collect.Maps;
+import com.google.common.truth.FailureStrategy;
+import com.google.common.truth.Subject;
+import com.google.common.truth.SubjectFactory;
+import com.google.common.truth.Truth;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.Map;
+
+import io.v.v23.V;
+import io.v.v23.VFutures;
+import io.v.v23.context.VContext;
+import io.v.v23.discovery.Advertisement;
+import io.v.v23.discovery.Update;
+import io.v.v23.verror.VException;
+
+import io.v.x.ref.lib.discovery.AdInfo;
+
+/**
+ * Various test utilities for discovery.
+ */
+public class DiscoveryTestUtil {
+    /**
+     * Allows a runtime to use a mock discovery instance.
+     * <p>
+     * This should be called before V.newDiscovery() is called.
+     */
+    private static native void injectMockDiscovery(VContext ctx) throws VException;
+
+    /**
+     * Initializes a runtime with a mock discovery instance.
+     */
+    public static VContext withMockDiscovery() throws VException {
+        VContext ctx = V.init();
+        injectMockDiscovery(ctx);
+        return ctx;
+    }
+
+    private static final Equivalence<byte[]> BYTE_ARRAY_EQUIVALENCE =
+            new Equivalence<byte[]>() {
+                @Override
+                protected boolean doEquivalent(byte[] a, byte[] b) {
+                    return Arrays.equals(a, b);
+                }
+
+                @Override
+                protected int doHash(byte[] bytes) {
+                    return Arrays.hashCode(bytes);
+                }
+            };
+
+    private static final Equivalence<Advertisement> ADVERTISEMENT_EQUIVALENCE =
+            new Equivalence<Advertisement>() {
+                @Override
+                protected boolean doEquivalent(Advertisement a, Advertisement b) {
+                    return a.getId().equals(b.getId())
+                            && a.getInterfaceName().equals(b.getInterfaceName())
+                            && a.getAddresses().equals(b.getAddresses())
+                            && a.getAttributes().equals(b.getAttributes())
+                            && Maps.difference(
+                                            a.getAttachments(),
+                                            b.getAttachments(),
+                                            BYTE_ARRAY_EQUIVALENCE)
+                                    .areEqual();
+                }
+
+                @Override
+                protected int doHash(Advertisement ad) {
+                    return Objects.hashCode(ad.getId());
+                }
+            };
+
+    private static final Equivalence<AdInfo> ADINFO_EQUIVALENCE =
+            new Equivalence<AdInfo>() {
+                @Override
+                protected boolean doEquivalent(AdInfo a, AdInfo b) {
+                    return ADVERTISEMENT_EQUIVALENCE.equivalent(a.getAd(), b.getAd())
+                            && a.getEncryptionAlgorithm().equals(b.getEncryptionAlgorithm())
+                            && a.getEncryptionKeys().equals(b.getEncryptionKeys())
+                            && a.getHash().equals(b.getHash())
+                            && a.getDirAddrs().equals(b.getDirAddrs());
+                }
+
+                @Override
+                protected int doHash(AdInfo adInfo) {
+                    return Objects.hashCode(adInfo.getAd().getId(), adInfo.getHash());
+                }
+            };
+
+    private static final Function<AdInfo, Equivalence.Wrapper<AdInfo>> ADINFO_WRAPPER =
+            new Function<AdInfo, Equivalence.Wrapper<AdInfo>>() {
+                @Override
+                public Equivalence.Wrapper<AdInfo> apply(AdInfo adinfo) {
+                    return ADINFO_EQUIVALENCE.wrap(adinfo);
+                }
+            };
+
+    /**
+     * {@link SubjectFactory} for {@link Advertisement}.
+     */
+    public static class AdvertisementSubject extends Subject<AdvertisementSubject, Advertisement> {
+        public AdvertisementSubject(FailureStrategy fs, Advertisement subject) {
+            super(fs, subject);
+        }
+
+        public void isEqualTo(Advertisement expected) {
+            if (!ADVERTISEMENT_EQUIVALENCE.equivalent(getSubject(), expected)) {
+                fail("is equal to", expected);
+            }
+        }
+    }
+
+    private static final SubjectFactory<AdvertisementSubject, Advertisement> ADVERTISEMENT_SF =
+            new SubjectFactory<AdvertisementSubject, Advertisement>() {
+                @Override
+                public AdvertisementSubject getSubject(FailureStrategy fs, Advertisement target) {
+                    return new AdvertisementSubject(fs, target);
+                }
+            };
+
+    public static AdvertisementSubject assertThat(Advertisement actual) {
+        return Truth.assertAbout(ADVERTISEMENT_SF).that(actual);
+    }
+
+    /**
+     * {@link SubjectFactory} for {@link AdInfo}.
+     */
+    public static class AdInfoSubject extends Subject<AdInfoSubject, AdInfo> {
+        public AdInfoSubject(FailureStrategy fs, AdInfo subject) {
+            super(fs, subject);
+        }
+
+        public void isEqualTo(AdInfo expected) {
+            if (!ADINFO_EQUIVALENCE.equivalent(getSubject(), expected)
+                    || getSubject().getLost() != expected.getLost()) {
+                fail("is equal to", expected);
+            }
+        }
+
+        public void isEqualTo(AdInfo expected, boolean lost) {
+            if (!ADINFO_EQUIVALENCE.equivalent(getSubject(), expected)) {
+                fail("is equal to", expected, lost);
+            }
+            if (getSubject().getLost() != lost) {
+                failWithCustomSubject("is equal to", getSubject().getLost(), lost);
+            }
+        }
+    }
+
+    private static final SubjectFactory<AdInfoSubject, AdInfo> ADINFO_SF =
+            new SubjectFactory<AdInfoSubject, AdInfo>() {
+                @Override
+                public AdInfoSubject getSubject(FailureStrategy fs, AdInfo target) {
+                    return new AdInfoSubject(fs, target);
+                }
+            };
+
+    public static AdInfoSubject assertThat(AdInfo actual) {
+        return Truth.assertAbout(ADINFO_SF).that(actual);
+    }
+
+    /**
+     * {@link SubjectFactory} for {@link List<AdInfo>}.
+     */
+    public static class AdInfoListSubject extends Subject<AdInfoListSubject, List<AdInfo>> {
+        public AdInfoListSubject(FailureStrategy fs, List<AdInfo> subject) {
+            super(fs, subject);
+        }
+
+        public void isEqualTo(AdInfo... expected) {
+            List<Equivalence.Wrapper<AdInfo>> actualWrapped =
+                    FluentIterable.of(expected).transform(ADINFO_WRAPPER).toList();
+            List<Equivalence.Wrapper<AdInfo>> expectedWrapped =
+                    FluentIterable.from(getSubject()).transform(ADINFO_WRAPPER).toList();
+            if (!ImmutableMultiset.copyOf(actualWrapped)
+                    .equals(ImmutableMultiset.copyOf(expectedWrapped))) {
+                fail("is equal to", FluentIterable.of(expected));
+            }
+        }
+    }
+
+    private static final SubjectFactory<AdInfoListSubject, List<AdInfo>> ADINFO_LIST_SF =
+            new SubjectFactory<AdInfoListSubject, List<AdInfo>>() {
+                @Override
+                public AdInfoListSubject getSubject(FailureStrategy fs, List<AdInfo> target) {
+                    return new AdInfoListSubject(fs, target);
+                }
+            };
+
+    public static AdInfoListSubject assertThat(List<AdInfo> actual) {
+        return Truth.assertAbout(ADINFO_LIST_SF).that(actual);
+    }
+
+    /**
+     * {@link SubjectFactory} for {@link Update}.
+     */
+    public static class UpdateSubject extends Subject<UpdateSubject, Update> {
+        public UpdateSubject(FailureStrategy fs, Update subject) {
+            super(fs, subject);
+        }
+
+        public void isEqualTo(VContext ctx, Advertisement expected) throws VException {
+            if (!equivalent(ctx, getSubject(), expected)) {
+                fail("is equal to", expected);
+            }
+        }
+
+        private static boolean equivalent(VContext ctx, Update update, Advertisement ad)
+                throws VException {
+            if (!update.getId().equals(ad.getId())) {
+                return false;
+            }
+            if (!update.getInterfaceName().equals(ad.getInterfaceName())) {
+                return false;
+            }
+            if (!update.getAddresses().equals(ad.getAddresses())) {
+                return false;
+            }
+            for (Map.Entry<String, String> entry : ad.getAttributes().entrySet()) {
+                if (!entry.getValue().equals(update.getAttribute(entry.getKey()))) {
+                    return false;
+                }
+            }
+            for (Map.Entry<String, byte[]> e : ad.getAttachments().entrySet()) {
+                byte[] data = VFutures.sync(update.getAttachment(ctx, e.getKey()));
+                if (!Arrays.equals(e.getValue(), data)) {
+                    return false;
+                }
+            }
+            return true;
+        }
+    }
+
+    private static final SubjectFactory<UpdateSubject, Update> UPDATE_SF =
+            new SubjectFactory<UpdateSubject, Update>() {
+                @Override
+                public UpdateSubject getSubject(FailureStrategy fs, Update target) {
+                    return new UpdateSubject(fs, target);
+                }
+            };
+
+    public static UpdateSubject assertThat(Update actual) {
+        return Truth.assertAbout(UPDATE_SF).that(actual);
+    }
+}
diff --git a/lib/src/test/java/io/v/impl/google/lib/discovery/EncodingUtilTest.java b/lib/src/test/java/io/v/impl/google/lib/discovery/EncodingUtilTest.java
index 0c135ca..3e7f2c2 100644
--- a/lib/src/test/java/io/v/impl/google/lib/discovery/EncodingUtilTest.java
+++ b/lib/src/test/java/io/v/impl/google/lib/discovery/EncodingUtilTest.java
@@ -1,52 +1,52 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Copyright 2016 The Vanadium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 package io.v.impl.google.lib.discovery;
 
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
 import junit.framework.TestCase;
 
-import java.io.IOException;
-
-import java.util.Arrays;
-
 import io.v.x.ref.lib.discovery.EncryptionAlgorithm;
-import io.v.x.ref.lib.discovery.testdata.PackAddressTest;
+import io.v.x.ref.lib.discovery.EncryptionKey;
 import io.v.x.ref.lib.discovery.testdata.Constants;
+import io.v.x.ref.lib.discovery.testdata.PackAddressTest;
 import io.v.x.ref.lib.discovery.testdata.PackEncryptionKeysTest;
 
+import static com.google.common.truth.Truth.assertThat;
+
 /**
  * Tests for {@link EncodingUtil}.
  */
 public class EncodingUtilTest extends TestCase {
     public void testPackAddresses() throws IOException {
         for (PackAddressTest test : Constants.PACK_ADDRESS_TEST_DATA) {
-            assertEquals(Arrays.toString(test.getPacked()),
-                    Arrays.toString(EncodingUtil.packAddresses(test.getIn())));
+            assertThat(EncodingUtil.packAddresses(test.getIn())).isEqualTo(test.getPacked());
         }
     }
 
     public void testUnpackAddresses() throws IOException {
-         for (PackAddressTest test : Constants.PACK_ADDRESS_TEST_DATA) {
-            assertEquals(test.getIn(),
-                    EncodingUtil.unpackAddresses(test.getPacked()));
+        for (PackAddressTest test : Constants.PACK_ADDRESS_TEST_DATA) {
+            assertThat(EncodingUtil.unpackAddresses(test.getPacked())).isEqualTo(test.getIn());
         }
     }
 
     public void testPackEncryptionKeys() throws IOException {
         for (PackEncryptionKeysTest test : Constants.PACK_ENCRYPTION_KEYS_TEST_DATA) {
-            byte[] res = EncodingUtil.packEncryptionKeys(test.getAlgo().getValue(),
-                    test.getKeys());
-            assertEquals(Arrays.toString(test.getPacked()), Arrays.toString(res));
+            byte[] packed = EncodingUtil.packEncryptionKeys(test.getAlgo(), test.getKeys());
+            assertThat(packed).isEqualTo(test.getPacked());
         }
     }
 
     public void testUnpackEncryptionKeys() throws IOException {
-         for (PackEncryptionKeysTest test : Constants.PACK_ENCRYPTION_KEYS_TEST_DATA) {
-             EncodingUtil.KeysAndAlgorithm res = EncodingUtil.unpackEncryptionKeys(
-                     test.getPacked());
-             assertEquals(test.getAlgo(), new EncryptionAlgorithm(res.getEncryptionAlgorithm()));
-             assertEquals(test.getKeys(), res.getKeys());
+        for (PackEncryptionKeysTest test : Constants.PACK_ENCRYPTION_KEYS_TEST_DATA) {
+            List<EncryptionKey> keys = new ArrayList<>();
+            EncryptionAlgorithm algo = EncodingUtil.unpackEncryptionKeys(test.getPacked(), keys);
+            assertThat(algo).isEqualTo(test.getAlgo());
+            assertThat(keys).isEqualTo(test.getKeys());
         }
     }
 }
diff --git a/lib/src/test/java/io/v/impl/google/lib/discovery/UUIDUtilTest.java b/lib/src/test/java/io/v/impl/google/lib/discovery/UUIDUtilTest.java
index f28ea48..dfca526 100644
--- a/lib/src/test/java/io/v/impl/google/lib/discovery/UUIDUtilTest.java
+++ b/lib/src/test/java/io/v/impl/google/lib/discovery/UUIDUtilTest.java
@@ -1,27 +1,38 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Copyright 2016 The Vanadium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 package io.v.impl.google.lib.discovery;
 
-import junit.framework.TestCase;
-
 import java.util.UUID;
 
+import junit.framework.TestCase;
+
 import io.v.v23.V;
 import io.v.v23.context.VContext;
+
 import io.v.x.ref.lib.discovery.testdata.Constants;
 import io.v.x.ref.lib.discovery.testdata.UuidTestData;
 
+import static com.google.common.truth.Truth.assertThat;
+
 /**
  * Tests for {@link UUIDUtil}.
  */
 public class UUIDUtilTest extends TestCase {
-    public void testInterfaceNameUUID() {
+    public void testServiceUuidTest() {
         VContext ctx = V.init();
-        for (UuidTestData test: Constants.INTERFACE_NAME_TEST) {
-            UUID id = UUIDUtil.UUIDForInterfaceName(test.getIn());
-            assertEquals(test.getWant(), id.toString());
+        for (UuidTestData test : Constants.SERVICE_UUID_TEST) {
+            UUID uuid = UUIDUtil.serviceUUID(test.getIn());
+            assertThat(uuid.toString()).isEqualTo(test.getWant());
+        }
+    }
+
+    public void testAttributeUuidTest() {
+        VContext ctx = V.init();
+        for (UuidTestData test : Constants.ATTRIBUTE_UUID_TEST) {
+            UUID uuid = UUIDUtil.attributeUUID(test.getIn());
+            assertThat(uuid.toString()).isEqualTo(test.getWant());
         }
     }
 }
diff --git a/lib/src/test/java/io/v/impl/google/lib/discovery/ble/BleAdvertisementConverterTest.java b/lib/src/test/java/io/v/impl/google/lib/discovery/ble/BleAdvertisementConverterTest.java
deleted file mode 100644
index dfcd44b..0000000
--- a/lib/src/test/java/io/v/impl/google/lib/discovery/ble/BleAdvertisementConverterTest.java
+++ /dev/null
@@ -1,69 +0,0 @@
-// Copyright 2015 The Vanadium Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package io.v.impl.google.lib.discovery.ble;
-
-import junit.framework.TestCase;
-
-import java.io.IOException;
-import java.util.Arrays;
-import java.util.HashMap;
-import java.util.Map;
-import java.util.UUID;
-
-import io.v.v23.V;
-import io.v.v23.vom.VomUtil;
-import io.v.v23.verror.VException;
-
-import io.v.x.ref.lib.discovery.Advertisement;
-import io.v.x.ref.lib.discovery.plugins.ble.testdata.AdvertisementConversionTestCase;
-import io.v.x.ref.lib.discovery.plugins.ble.testdata.Constants;
-
-/**
- * Tests for {@link BleAdvertisementConverter}
- */
-public class BleAdvertisementConverterTest extends TestCase {
-    private static Map<UUID, byte[]> convertBAdv(Map<String, byte[]> in) {
-        Map<UUID, byte[]> res = new HashMap<>(in.size());
-        for (Map.Entry<String, byte[]> entry : in.entrySet()) {
-            res.put(UUID.fromString(entry.getKey()), entry.getValue());
-        }
-        return res;
-    }
-
-    public void testConversionToBle() throws IOException {
-        // V.init() sets up the jni bindings.
-        V.init();
-        for (AdvertisementConversionTestCase test : Constants.CONVERSION_TEST_DATA) {
-            Map<UUID, byte[]> res = BleAdvertisementConverter.vAdvertismentToBleAttr(
-                test.getAdvertisement());
-            Map<String, byte[]> want = test.getBleAdvertisement();
-            assertEquals(want.size(), res.size());
-            for (Map.Entry<UUID, byte[]> entry : res.entrySet()) {
-                String stringKey = entry.getKey().toString();
-                assertTrue(stringKey + " not matched",
-                           Arrays.equals(want.get(stringKey), entry.getValue()));
-            }
-        }
-    }
-
-    public void testConversionFromBle() throws IOException {
-        // V.init() sets up the jni bindings.
-        V.init();
-        for (AdvertisementConversionTestCase test : Constants.CONVERSION_TEST_DATA) {
-            Map<UUID, byte[]> bleAdv = convertBAdv(test.getBleAdvertisement());
-            Advertisement res = BleAdvertisementConverter.bleAttrToVAdvertisement(bleAdv);
-            // We can't use assertEquals here since we need a deep comparison.
-            // We compare them by serializing to vom.
-            try {
-                byte[] wantVom = VomUtil.encode(test.getAdvertisement(), test.getAdvertisement().VDL_TYPE);
-                byte[] resVom = VomUtil.encode(res, res.VDL_TYPE);
-                assertTrue("expected:<" + test.getAdvertisement() + "> but was:<" + res + ">",
-                           Arrays.equals(wantVom, resVom));
-            } catch (VException e) {
-              fail(e.toString());
-            }
-        }
-    }
-}