diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMapping.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMapping.java
new file mode 100644
index 0000000..804f1d7
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMapping.java
@@ -0,0 +1,11 @@
+// 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.todos.persistence.syncbase;
+
+public interface DigitMapping {
+    char encode(int digit);
+    int decode(char encoded);
+    int radix();
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMappings.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMappings.java
new file mode 100644
index 0000000..925b40e
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMappings.java
@@ -0,0 +1,88 @@
+// 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.todos.persistence.syncbase;
+
+import android.support.annotation.NonNull;
+
+import com.google.common.base.Function;
+import com.google.common.collect.Collections2;
+import com.google.common.collect.ContiguousSet;
+import com.google.common.collect.DiscreteDomain;
+import com.google.common.collect.ImmutableRangeSet;
+import com.google.common.collect.Range;
+import com.google.common.collect.RangeSet;
+
+public final class DigitMappings {
+    private DigitMappings() {
+    }
+
+    public static final DiscreteDomain<Character> DOMAIN = new DiscreteDomain<Character>() {
+        @Override
+        public Character next(@NonNull Character value) {
+            return value == Character.MAX_VALUE ? null : (char) (value + 1);
+        }
+
+        @Override
+        public Character previous(@NonNull Character value) {
+            return value == Character.MIN_VALUE ? null : (char) (value - 1);
+        }
+
+        @Override
+        public long distance(@NonNull Character start, @NonNull Character end) {
+            return end - start;
+        }
+
+        @Override
+        public Character maxValue() {
+            return Character.MAX_VALUE;
+        }
+
+        @Override
+        public Character minValue() {
+            return Character.MIN_VALUE;
+        }
+    };
+
+    public static final DigitMapping ALL = fromRangeSet(Range.<Character>all());
+
+    /**
+     * Constructs a {@link DigitMapping} from the given ranges, where the ranges are given in order
+     * of increasing significance. Although the ranges may jump around in significance, within each
+     * range, characters are still mapped to digits in ascending order. Out-of-order ranges may be
+     * used as well but cannot be optimized in this way.
+     *
+     * @see DigitRangeMapping
+     */
+    public static DigitMapping fromRanges(Iterable<ContiguousSet<Character>> ranges) {
+        return new DigitRangeMapping(ranges);
+    }
+
+    /**
+     * @see #fromRangeSet(RangeSet)
+     */
+    @SafeVarargs
+    public static DigitMapping fromRangeSet(Range<Character>... ranges) {
+        ImmutableRangeSet.Builder<Character> builder = ImmutableRangeSet.builder();
+        for (Range<Character> range : ranges) {
+            builder.add(range);
+        }
+        return fromRangeSet(builder.build());
+    }
+
+    /**
+     * Constructs a {@link DigitMapping} from a {@link RangeSet}, ordering the ranges in ascending
+     * order (regardless of input order). If out-of-order ranges are desired, use the
+     * {@link #fromRanges(Iterable)} factory method instead to provide explicit ordering.
+     */
+    public static DigitMapping fromRangeSet(RangeSet<Character> spec) {
+        return fromRanges(Collections2.transform(spec.asRanges(),
+                new Function<Range<Character>, ContiguousSet<Character>>() {
+                    @Override
+                    public ContiguousSet<Character> apply(Range<Character> input) {
+                        return ContiguousSet.create(input, DOMAIN);
+                    }
+                }));
+    }
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitRangeMapping.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitRangeMapping.java
new file mode 100644
index 0000000..3f3f140
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitRangeMapping.java
@@ -0,0 +1,57 @@
+// 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.todos.persistence.syncbase;
+
+import com.google.common.collect.ContiguousSet;
+import com.google.common.collect.ImmutableList;
+
+/**
+ * A {@link DigitMapping} optimized for mappings where ranges of consecutive characters map to
+ * consecutive values. The overall mapping need not be monotonic to take advantage of this
+ * optimization.
+ */
+public class DigitRangeMapping implements DigitMapping {
+    private final ImmutableList<ContiguousSet<Character>> mRanges;
+    private final int mRadix;
+
+    public DigitRangeMapping(Iterable<ContiguousSet<Character>> ranges) {
+        mRanges = ImmutableList.copyOf(ranges);
+        int size = 0;
+        for (ContiguousSet<Character> range : mRanges) {
+            size += range.size();
+        }
+        mRadix = size;
+    }
+
+    @Override
+    public char encode(int digit) {
+        for (ContiguousSet<Character> range : mRanges) {
+            if (digit < range.size()) {
+                return range.asList().get(digit);
+            } else {
+                digit -= range.size();
+            }
+        }
+        throw new IllegalArgumentException("No encoding for digit " + digit + " (radix " + radix() +
+                ")");
+    }
+
+    @Override
+    public int decode(char encoded) {
+        int digit = 0;
+        for (ContiguousSet<Character> range : mRanges) {
+            if (range.contains(encoded)) {
+                return digit + encoded - range.first();
+            }
+            digit += range.size();
+        }
+        throw new IllegalArgumentException();
+    }
+
+    @Override
+    public int radix() {
+        return mRadix;
+    }
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabet.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabet.java
new file mode 100644
index 0000000..a42ef4e
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabet.java
@@ -0,0 +1,16 @@
+// 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.todos.persistence.syncbase;
+
+public interface IdAlphabet {
+    char encodeDigit(int digit);
+    int decodeDigit(char encoded);
+
+    char encodeLeadingDigit(int digit);
+    int decodeLeadingDigit(char encoded);
+
+    int radix();
+    int leadingRadix();
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabets.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabets.java
new file mode 100644
index 0000000..673ce4b
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabets.java
@@ -0,0 +1,63 @@
+// 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.todos.persistence.syncbase;
+
+import com.google.common.collect.Range;
+
+public final class IdAlphabets {
+    private IdAlphabets() {
+    }
+
+    public static final IdAlphabet
+            COLLECTION_ID = fromDigitMappings(
+            DigitMappings.fromRangeSet(
+                    Range.closed('0', '9'),
+                    Range.closed('A', 'Z'),
+                    Range.singleton('_'),
+                    Range.closed('a', 'z')),
+            DigitMappings.fromRangeSet(
+                    Range.closed('A', 'Z'),
+                    Range.closed('a', 'z'))),
+            ROW_NAME = fromDigitMapping(DigitMappings.ALL);
+
+    public static IdAlphabet fromDigitMapping(final DigitMapping digitMapping) {
+        return fromDigitMappings(digitMapping, digitMapping);
+    }
+
+    public static IdAlphabet fromDigitMappings(final DigitMapping digitMapping,
+                                               final DigitMapping leadingDigitMapping) {
+        return new IdAlphabet() {
+            @Override
+            public char encodeDigit(int digit) {
+                return digitMapping.encode(digit);
+            }
+
+            @Override
+            public int decodeDigit(char encoded) {
+                return digitMapping.decode(encoded);
+            }
+
+            @Override
+            public char encodeLeadingDigit(int digit) {
+                return leadingDigitMapping.encode(digit);
+            }
+
+            @Override
+            public int decodeLeadingDigit(char encoded) {
+                return leadingDigitMapping.decode(encoded);
+            }
+
+            @Override
+            public int radix() {
+                return digitMapping.radix();
+            }
+
+            @Override
+            public int leadingRadix() {
+                return leadingDigitMapping.radix();
+            }
+        };
+    }
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdGenerator.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdGenerator.java
new file mode 100644
index 0000000..10e77c7
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdGenerator.java
@@ -0,0 +1,257 @@
+// 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.todos.persistence.syncbase;
+
+import java.util.UUID;
+
+public class IdGenerator {
+    // TODO(rosswang): Escape collection IDs to allow any character. A lot of this logic can be
+    // simplified if we can use any character.
+    // TODO(rosswang): Put this into Syncbase utils.
+
+    private final IdAlphabet mAlphabet;
+
+    /**
+     * the length we *would* need if we could use an underscore for the first character
+     */
+    private final int mLongUniformRadixLength;
+    private final int mLongEncodedLength;
+
+    /**
+     * This is related to unsigned division.
+     * @see #transformToSignedDivision(long)
+     */
+    private final int mMaxSafeMostSignificantDigit;
+    /**
+     * This is related to unsigned division.
+     * @see #transformToSignedDivision(long)
+     */
+    private final long mMostSignificantUnit, mMaxSafeMostSignificantValue;
+
+    private static final double LOG_LONG = Long.SIZE * Math.log(2);
+
+    /**
+     * @param alphabet the alphabet of legal characters for IDs generated by this generator
+     * @param perturb whether or not to perturb generated IDs by a random perturbation to avoid
+     *                collisions in distributed key generation. Pass {@code false} if this generator
+     *                is used to generate a sort key that is a secondary key where ordering
+     *                conflicts can be deterministically resolved by the primary key. This setting
+     *                only applies to the {@code generate...} methods.
+     */
+    public IdGenerator(IdAlphabet alphabet, boolean perturb) {
+        mAlphabet = alphabet;
+        mPerturb = perturb;
+
+        // ceil(log_RADIX(Long.MAX + 1))
+        mLongUniformRadixLength = (int)Math.ceil(LOG_LONG / Math.log(alphabet.radix()));
+
+        // int pow, msu = radix ^ url
+        long mostSignificantUnit = alphabet.radix();
+        for (int i = 2; i < mLongUniformRadixLength; i++) {
+            mostSignificantUnit *= alphabet.radix();
+        }
+        mMostSignificantUnit = mostSignificantUnit;
+
+        mMaxSafeMostSignificantDigit = (int)(Long.MAX_VALUE / mMostSignificantUnit);
+        mMaxSafeMostSignificantValue = mMaxSafeMostSignificantDigit * mMostSignificantUnit;
+
+        // The first character may have additional restrictions, so we have less chars to work with
+        // for the first digit. If we still have enough digits, we'll proceed and just use a special
+        // mapping for the leading digit. Otherwise, we'll pad by a leading 0, thus making the
+        // remaining encoding the common case.
+
+        // So, what most-significant digit do we need to encode the max unsigned value?
+        PartialDivisionResult div = transformToSignedDivision(-1);
+        int maxMostSignfiicantDigit = div.partialMostSignificantDigit +
+                (int)(div.partialRemainder / mMostSignificantUnit);
+        mLongEncodedLength = maxMostSignfiicantDigit < alphabet.leadingRadix() ?
+                mLongUniformRadixLength : mLongUniformRadixLength + 1;
+    }
+
+    private static class PartialDivisionResult {
+        public int partialMostSignificantDigit;
+        public long partialRemainder;
+
+        public PartialDivisionResult(int partialMostSignificantDigit, long partialRemainder) {
+            this.partialMostSignificantDigit = partialMostSignificantDigit;
+            this.partialRemainder = partialRemainder;
+        }
+    }
+
+    /**
+     * Performs partial calculation of the most significant digit for the alphabet-radix
+     * representation of {@code unsigned}. To achieve unsigned division, we first assume the
+     * most significant digit is at least as large as the max safe most significant digit for signed
+     * division, add one more if neccessary to push the "remainder" positive, and then do normal
+     * division for the rest.
+     */
+    private PartialDivisionResult transformToSignedDivision(long unsigned) {
+        if (unsigned < 0) {
+            long naiveRemainder = unsigned - mMaxSafeMostSignificantValue;
+            return naiveRemainder < 0 ?
+                    // need one more
+                    new PartialDivisionResult(mMaxSafeMostSignificantDigit + 1,
+                            naiveRemainder - mMostSignificantUnit) :
+                    new PartialDivisionResult(mMaxSafeMostSignificantDigit, naiveRemainder);
+        } else {
+            // Already positive; handle with normal arithmetic.
+            return new PartialDivisionResult(0, unsigned);
+        }
+    }
+
+    /**
+     * Converts a signed {@code long} to a {@code String} consistent with the pattern
+     * {@code [0-9A-Za-z][0-9A-Za-z_]*}, required by Syncbase for
+     * {@link io.v.v23.services.syncbase.Id} names, with lexicographic ordering consistent with the
+     * numeric ordering.
+     * <p>
+     * Example transformations using {@link IdAlphabets#COLLECTION_ID}:
+     * <pre>
+     * -9223372036854775808 -> 00000000000
+     * -9223372036854775807 -> 00000000001
+     * -9223372036854775806 -> 00000000002
+     *                   -1 -> 9MxfBQuKjH7
+     *                    0 -> 9MxfBQuKjH8
+     *                    1 -> 9MxfBQuKjH9
+     *  9223372036854775805 -> IivLMqoeTYD
+     *  9223372036854775806 -> IivLMqoeTYE
+     *  9223372036854775807 -> IivLMqoeTYF
+     * </pre>
+     */
+    public String longToPaddedIdentifier(long x) {
+        StringBuilder s = new StringBuilder(mLongEncodedLength);
+        long unsignedWithSameOrdering = x - Long.MIN_VALUE;
+        PartialDivisionResult signedSubproblem =
+                transformToSignedDivision(unsignedWithSameOrdering);
+        long leftToEncode = signedSubproblem.partialRemainder;
+
+        for (int placeValue = 0; placeValue < mLongUniformRadixLength - 1; placeValue++) {
+            if (leftToEncode > 0) {
+                s.append(mAlphabet.encodeDigit((int) (leftToEncode % mAlphabet.radix())));
+                leftToEncode /= mAlphabet.radix();
+            } else {
+                s.append(mAlphabet.encodeDigit(0));
+            }
+        }
+
+        // The most-significant digit needs to be handled specially, accounting for the signed
+        // division adjustment and using a possibly different character mapping.
+        int mostSignificantDigit = signedSubproblem.partialMostSignificantDigit + (int)leftToEncode;
+        if (mLongEncodedLength > mLongUniformRadixLength) {
+            // just 0-pad
+            s.append(mAlphabet.encodeDigit(mostSignificantDigit))
+                    .append(mAlphabet.encodeLeadingDigit(0));
+        } else {
+            // use the special leading-digit mapping
+            s.append(mAlphabet.encodeLeadingDigit(mostSignificantDigit));
+        }
+
+        return s.reverse().toString();
+    }
+
+    /**
+     * Perturbs IDs to mitigate collision during distributed, eventually consistent insertion.
+     * {@link UUID#randomUUID()} is used for perturbation. The perturbed ID is strictly greater than
+     * the base ID but less than the next increment from the base ID except in the degenerate case
+     * where the base ID must be extended to increment.
+     */
+    public String perturb(String baseId) {
+        UUID uuid = UUID.randomUUID();
+        return baseId +
+                longToPaddedIdentifier(uuid.getMostSignificantBits()) +
+                longToPaddedIdentifier(uuid.getLeastSignificantBits());
+    }
+
+    /**
+     * Increments an ID with a proposed base length. If the increment cannot be done under these
+     * constraints, the ID is extended. The incremented ID is guaranteed to be greater than the
+     * given {@code fullId}.
+     * <p>
+     * Example transformations:
+     * <pre>
+     * 0000 -> 01
+     * AZ00 -> A_
+     * Az00 -> B0
+     * Zz00 -> a0
+     * zz00 -> zz1
+     * zzz0 -> zzz1
+     * zzzz -> zzzz0
+     * </pre>
+     */
+    public String increment(String fullId, int proposedCutoff) {
+        StringBuilder mutable = new StringBuilder(fullId);
+
+        if (proposedCutoff > fullId.length()) {
+            proposedCutoff = fullId.length();
+        }
+
+        // First try normal incrementing
+        for (int i = proposedCutoff - 1; i > 0; i--) {
+            int newValue = mAlphabet.decodeDigit(mutable.charAt(i)) + 1;
+            if (newValue < mAlphabet.radix()) {
+                mutable.setCharAt(i, mAlphabet.encodeDigit(newValue));
+                mutable.setLength(proposedCutoff);
+                return mutable.toString();
+            } else {
+                mutable.setCharAt(i, mAlphabet.encodeDigit(0));
+            }
+        }
+
+        // Process the leading digit specially
+        if (proposedCutoff > 0){
+            int newValue = mAlphabet.decodeLeadingDigit(mutable.charAt(0)) + 1;
+            if (newValue < mAlphabet.leadingRadix()) {
+                mutable.setCharAt(0, mAlphabet.encodeLeadingDigit(newValue));
+                mutable.setLength(proposedCutoff);
+                return mutable.toString();
+            }
+        }
+
+        // If we've gotten to this point, we can't increment the prefix; start looking at the
+        // suffix.
+
+        // Reset mutable
+        mutable.setLength(0);
+        mutable.append(fullId);
+
+        for (int i = proposedCutoff; i < fullId.length(); i++) {
+            int newValue = mAlphabet.decodeDigit(mutable.charAt(i)) + 1;
+            if (newValue < mAlphabet.radix()) {
+                mutable.setCharAt(i, mAlphabet.encodeDigit(newValue));
+                mutable.setLength(i + 1);
+                return mutable.toString();
+            }
+        }
+        // By this point, we just have to extend the string.
+        mutable.append(mAlphabet.encodeDigit(0));
+        return mutable.toString();
+    }
+
+    public String increment(String previous) {
+        return increment(previous, mLongEncodedLength);
+    }
+
+    private final Object mLargestKnownIdMutex = new Object();
+    private String mLargestKnownId;
+    private final boolean mPerturb;
+
+    public String generateTailId() {
+        String candidate = longToPaddedIdentifier(System.currentTimeMillis());
+        synchronized (mLargestKnownIdMutex) {
+            if (mLargestKnownId != null && candidate.compareTo(mLargestKnownId) <= 0) {
+                candidate = increment(mLargestKnownId);
+            }
+            return mLargestKnownId = mPerturb? perturb(candidate) : candidate;
+        }
+    }
+
+    public void registerId(String id) {
+        synchronized (mLargestKnownIdMutex) {
+            if (mLargestKnownId == null || id.compareTo(mLargestKnownId) > 0) {
+                mLargestKnownId = id;
+            }
+        }
+    }
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/MainListTracker.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/MainListTracker.java
index be1f568..11545d3 100644
--- a/app/src/syncbase/java/io/v/todos/persistence/syncbase/MainListTracker.java
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/MainListTracker.java
@@ -85,7 +85,7 @@
     private void processWatchChange(WatchChange change) {
         String rowName = change.getRowName();
 
-        if (rowName.equals(SyncbaseTodoList.LIST_ROW_NAME)) {
+        if (rowName.equals(SyncbaseTodoList.LIST_METADATA_ROW_NAME)) {
             mListSpec = SyncbasePersistence.castWatchValue(change.getValue(), ListSpec.class);
         } else if (change.getChangeType() == ChangeType.DELETE_CHANGE) {
             if (mIsTaskCompleted.remove(rowName)) {
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseMain.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseMain.java
index 8d6b190..9e77ae3 100644
--- a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseMain.java
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseMain.java
@@ -45,6 +45,7 @@
             TAG = SyncbaseMain.class.getSimpleName(),
             LISTS_PREFIX = "lists_";
 
+    private final IdGenerator mIdGenerator = new IdGenerator(IdAlphabets.COLLECTION_ID, true);
     private final Map<String, MainListTracker> mTaskTrackers = new HashMap<>();
 
     /**
@@ -64,6 +65,8 @@
                 if (change.getChangeType() == ChangeType.DELETE_CHANGE) {
                     trap(mTaskTrackers.remove(listId).deleteList(mVContext));
                 } else {
+                    mIdGenerator.registerId(change.getRowName().substring(LISTS_PREFIX.length()));
+
                     MainListTracker listTracker = new MainListTracker(
                             mVContext, getDatabase(), listId, listener);
                     if (mTaskTrackers.put(listId, listTracker) != null) {
@@ -82,7 +85,7 @@
 
     @Override
     public void addTodoList(final ListSpec listSpec) {
-        final String listName = LISTS_PREFIX + randomName();
+        final String listName = LISTS_PREFIX + mIdGenerator.generateTailId();
         final Collection listCollection = getDatabase().getCollection(mVContext, listName);
         Futures.addCallback(listCollection.create(mVContext, null),
                 new TrappingCallback<Void>(mActivity) {
@@ -90,8 +93,8 @@
                     public void onSuccess(@Nullable Void result) {
                         // These can happen in either order
                         trap(getUserCollection().put(mVContext, listName, null, VdlAny.class));
-                        trap(listCollection.put(mVContext, SyncbaseTodoList.LIST_ROW_NAME, listSpec,
-                                ListSpec.class));
+                        trap(listCollection.put(mVContext, SyncbaseTodoList.LIST_METADATA_ROW_NAME,
+                                listSpec, ListSpec.class));
                     }
                 });
     }
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbasePersistence.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbasePersistence.java
index b2b0db9..e475d3d 100644
--- a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbasePersistence.java
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbasePersistence.java
@@ -24,7 +24,6 @@
 import com.google.common.util.concurrent.SettableFuture;
 
 import java.io.File;
-import java.util.UUID;
 import java.util.concurrent.Executors;
 
 import javax.annotation.Nullable;
@@ -186,10 +185,6 @@
         return sUserCollection != null;
     }
 
-    protected static String randomName() {
-        return UUID.randomUUID().toString().replace('-', '_');
-    }
-
     /**
      * A {@link FutureCallback} that reports persistence errors by toasting a short message to the
      * user and logging the exception trace and the call stack from where the future was invoked.
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseTodoList.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseTodoList.java
index 49a4a14..beb8fc5 100644
--- a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseTodoList.java
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseTodoList.java
@@ -32,7 +32,7 @@
 
 public class SyncbaseTodoList extends SyncbasePersistence implements TodoListPersistence {
     public static final String
-            LIST_ROW_NAME = "list",
+            LIST_METADATA_ROW_NAME = "list",
             TASKS_PREFIX = "tasks_";
 
     private static final String
@@ -40,6 +40,7 @@
 
     private final Collection mList;
     private final TodoListListener mListener;
+    private final IdGenerator mIdGenerator = new IdGenerator(IdAlphabets.ROW_NAME, true);
     private final Set<String> mTaskIds = new HashSet<>();
 
     /**
@@ -88,7 +89,7 @@
     private void processWatchChange(WatchChange change) {
         String rowName = change.getRowName();
 
-        if (rowName.equals(SyncbaseTodoList.LIST_ROW_NAME)) {
+        if (rowName.equals(SyncbaseTodoList.LIST_METADATA_ROW_NAME)) {
             ListSpec listSpec = SyncbasePersistence.castWatchValue(change.getValue(),
                     ListSpec.class);
             mListener.onUpdate(listSpec);
@@ -96,6 +97,8 @@
             mTaskIds.remove(rowName);
             mListener.onItemDelete(rowName);
         } else {
+            mIdGenerator.registerId(change.getRowName().substring(TASKS_PREFIX.length()));
+
             TaskSpec taskSpec = SyncbasePersistence.castWatchValue(change.getValue(),
                     TaskSpec.class);
             Task task = new Task(rowName, taskSpec);
@@ -110,7 +113,7 @@
 
     @Override
     public void updateTodoList(ListSpec listSpec) {
-        trap(mList.put(mVContext, LIST_ROW_NAME, listSpec, ListSpec.class));
+        trap(mList.put(mVContext, LIST_METADATA_ROW_NAME, listSpec, ListSpec.class));
     }
 
     @Override
@@ -121,13 +124,13 @@
 
     public static ListenableFuture<Void> updateListTimestamp(final VContext vContext,
                                                              final Collection list) {
-        ListenableFuture<Object> get = list.get(vContext, LIST_ROW_NAME, ListSpec.class);
-        return Futures.transform(get, new AsyncFunction<Object, Void>() {
+        ListenableFuture<Object> get = list.get(vContext, LIST_METADATA_ROW_NAME, ListSpec.class);
+        return Futures.transformAsync(get, new AsyncFunction<Object, Void>() {
             @Override
             public ListenableFuture<Void> apply(Object oldValue) throws Exception {
                 ListSpec listSpec = (ListSpec) oldValue;
                 listSpec.setUpdatedAt(System.currentTimeMillis());
-                return list.put(vContext, LIST_ROW_NAME, listSpec, ListSpec.class);
+                return list.put(vContext, LIST_METADATA_ROW_NAME, listSpec, ListSpec.class);
             }
         });
     }
@@ -138,7 +141,8 @@
 
     @Override
     public void addTask(TaskSpec task) {
-        trap(mList.put(mVContext, TASKS_PREFIX + randomName(), task, TaskSpec.class));
+        trap(mList.put(mVContext, TASKS_PREFIX + mIdGenerator.generateTailId(), task,
+                TaskSpec.class));
         updateListTimestamp();
     }
 
diff --git a/app/src/testSyncbase/java/io/v/todos/persistence/syncbase/IdGeneratorTest.java b/app/src/testSyncbase/java/io/v/todos/persistence/syncbase/IdGeneratorTest.java
new file mode 100644
index 0000000..996db6d
--- /dev/null
+++ b/app/src/testSyncbase/java/io/v/todos/persistence/syncbase/IdGeneratorTest.java
@@ -0,0 +1,100 @@
+// 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.todos.persistence.syncbase;
+
+import org.junit.Test;
+
+import java.util.Random;
+import java.util.regex.Pattern;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+public class IdGeneratorTest {
+    private static final Pattern COLLECTION_ID_PATTERN = Pattern.compile("[0-9A-Za-z][0-9A-Za-z_]*");
+    private static final Random RANDOM = new Random();
+
+    @Test
+    public void testLongToPaddedIdentifier() {
+        IdGenerator
+                testGeneratorA = new IdGenerator(IdAlphabets.COLLECTION_ID, true),
+                testGeneratorB = new IdGenerator(IdAlphabets.ROW_NAME, true);
+
+        long[] sortedInputs = new long[]{
+                Long.MIN_VALUE,
+                Long.MIN_VALUE + 1,
+                Long.MIN_VALUE + 2,
+                -1,
+                0,
+                1,
+                Long.MAX_VALUE - 2,
+                Long.MAX_VALUE - 1,
+                Long.MAX_VALUE
+        };
+        String lastIdA = null, lastIdB = null;
+        for (long input : sortedInputs) {
+            String testId = testGeneratorA.longToPaddedIdentifier(input);
+            if (lastIdA != null) {
+                assertTrue("IdGenerator.longToPaddedIdentifier generates IDs consistent with " +
+                        "input ordering", testId.compareTo(lastIdA) > 0);
+            }
+            lastIdA = testId;
+
+            testId = testGeneratorB.longToPaddedIdentifier(input);
+            if (lastIdB != null) {
+                assertTrue("IdGenerator.longToPaddedIdentifier generates IDs consistent with " +
+                        "input ordering", testId.compareTo(lastIdB) > 0);
+            }
+            lastIdB = testId;
+        }
+
+        for (int i = 0; i < 50; i++) {
+            // Smoke fuzz test
+            testGeneratorA.longToPaddedIdentifier(RANDOM.nextLong());
+            testGeneratorB.longToPaddedIdentifier(RANDOM.nextLong());
+        }
+    }
+
+    @Test
+    public void testDecodeChar() {
+        for (int i = 0; i < IdAlphabets.COLLECTION_ID.radix(); i++) {
+            char testChar = IdAlphabets.COLLECTION_ID.encodeDigit(i);
+            assertEquals("IdGenerator.decodeChar('" + testChar + "')",
+                    i, IdAlphabets.COLLECTION_ID.decodeDigit(testChar));
+        }
+    }
+
+    private void verifyIncrement(String input, String incremented) {
+        String diagnostic = input + " + 1 = " + incremented;
+        assertTrue("IdGenerator.increment generates larger IDs than the input (" + diagnostic + ")",
+                incremented.compareTo(input) > 0);
+        assertTrue("IdGenerator.increment generates legal IDs (" + diagnostic + ")",
+                COLLECTION_ID_PATTERN.matcher(incremented).matches());
+    }
+
+    @Test
+    public void testIncrement() {
+        IdGenerator testGenerator = new IdGenerator(IdAlphabets.COLLECTION_ID, true);
+
+        String[] inputs = new String[]{
+                "0000",
+                "AZ00",
+                "Az00",
+                "Zz00",
+                "zz00",
+                "zzz0",
+                "zzzz"
+        };
+
+        for (String input : inputs) {
+            verifyIncrement(input, testGenerator.increment(input, 2));
+        }
+
+        for (int i = 0; i < 50; i++) {
+            String input = testGenerator.longToPaddedIdentifier(RANDOM.nextLong());
+            verifyIncrement(input, testGenerator.increment(input, RANDOM.nextInt(input.length())));
+        }
+    }
+}
\ No newline at end of file