Multi-Agent Transactive Hierarchical Crawlable Memory Without Timestamps

Full report

On this page

Executive Summary

This report analyzes how to design a shared memory substrate for multiple agents that is transactive, hierarchical, crawlable, and explicitly does not rely on physical timestamps for ordering, conflict resolution, or synchronization. The strongest general conclusion is that the most robust design is layered: use content-addressed immutable artifacts and hash-linked causal metadata for durable history, CRDT-based replicated structures for high-availability shared state, causal dependency tracking for read-your-writes and workflow coherence, and consensus only for the small subset of coordination data that truly requires linearizable semantics. This composition fits both the classic distributed-systems literature and the newest agent-memory work better than any single consistency model or single metadata scheme.

For this report, “transactive memory” is treated as the system property that lets agents know who or what knows what, not just what raw content exists. In human teams, transactive memory is about distributed expertise plus coordination; in modern agent systems, recent work such as Multi-Agent Transactive Memory reframes it as a population-level repository of agent-generated trajectories, while G-Memory and DAMCS show that hierarchical structures outperform flat repositories for long-horizon, multi-agent reuse. Those lines of work strongly suggest that a good multi-agent memory layer must store both knowledge objects and routing cues about where useful expertise resides.

The central technical challenge in the user’s scenario is the phrase “without timestamps.” Physical clocks are attractive because they simplify “latest write wins,” but they are a poor foundation for open or asynchronous systems: clock skew, reordering, client mobility, and malicious participants all make wall-clock order an unreliable proxy for causal order. The alternative is not “no ordering,” but rather different ordering: logical clocks, version vectors, interval/tree clocks, content-addressed DAG histories, and replicated logs ordered by consensus terms and indices instead of wall time.

Under unspecified scale, network model, and consistency requirements, the best default architecture is:

The most important recommendation is therefore not to pick one global consistency mode. The recommended system is mixed-consistency and mixed-metadata: immutable content-addressed history at the bottom, causally ordered shared memory in the middle, and selectively linearizable coordination at the top. This is the design that best reconciles the tradeoffs documented in CRDT research, causal-consistency systems, content-addressed storage, and recent agent-memory architectures.

Conceptual Foundations

A transactive memory system was introduced by Daniel Wegner as a shared memory system formed by combining individual memories with communication among individuals; in practice, it is often summarized as knowledge of “who knows what.” Later work operationalized it around three dimensions: specialization, credibility, and coordination. Those three dimensions map unusually well onto multi-agent memory engineering: specialization becomes partitioning of expertise and ownership, credibility becomes trust or provenance, and coordination becomes the retrieval and synchronization layer that routes the right memory to the right agent at the right point in a workflow.

A multi-agent system in this report means a set of autonomous agents that produce artifacts, consume shared context, and may join or leave over time. Recent agent-memory work makes clear that flat “vector-store-only” approaches leave performance on the table. MATM treats the shared repository as population-level experience reuse, with producer agents contributing trajectories and consumer agents retrieving them. G-Memory uses a three-tier graph hierarchy of insight, query, and interaction graphs. DAMCS similarly organizes memory as a hierarchical knowledge graph plus structured communication. Across these papers, flat retrieval is consistently weaker than structured, multi-level memory.

In this report, hierarchical memory means a memory substrate with at least three explicit levels: raw events or steps, mid-level episodes or task traces, and high-level abstractions such as skills, insights, entities, or plans. This is not only a storage optimization; it is also a retrieval and governance optimization. Hierarchical agents and graph-based memory systems increasingly separate representation from retrieval policy, allowing the crawler to traverse fine-grained details only when the query warrants it. Recent systems such as MAGMA formalize this idea by representing each item across semantic, temporal, causal, and entity graphs, while HiGraAgent shows that hybrid semantic-plus-structural retrieval can outperform purely structural or purely iterative reasoning baselines.

In this report, crawlable memory means memory whose identifiers, links, summaries, and indexes allow a machine to deterministically or probabilistically traverse from one artifact to related artifacts without needing a central mutable catalog. Content-addressed structures such as Merkle DAGs are naturally crawlable because a root identifier lets a consumer fetch descendants by following links, and distributed content-routing layers such as IPFS DHT + Bitswap make that crawl network-visible. Merkle Search Trees extend that idea to ordered key spaces, turning crawlability into a practical anti-entropy and lookup primitive.

The phrase “without timestamps” should be interpreted narrowly and precisely: no dependence on physical or wall-clock timestamps in the memory metadata used for correctness. A deployment may still use timers for retries, leader election, or background maintenance, but safety and merge semantics should not depend on synchronized clocks. Lamport’s result that distributed systems admit only a partial order from message causality remains foundational here, and modern systems such as Raft explicitly note that safety can be preserved independently of timing even though liveness may still rely on timeouts.

erDiagram
    AGENT ||--o{ ARTIFACT : produces
    AGENT ||--o{ QUERY : submits
    ARTIFACT ||--o{ SUMMARY_NODE : abstracts_into
    SUMMARY_NODE ||--o{ INDEX_ENTRY : indexed_by
    ARTIFACT ||--o{ CAUSAL_EDGE : precedes
    ARTIFACT ||--o{ ENTITY_EDGE : mentions
    QUERY ||--o{ RETRIEVAL_PLAN : compiles_to
    RETRIEVAL_PLAN ||--o{ INDEX_ENTRY : traverses
    INDEX_ENTRY }o--|| BLOCK : points_to
    BLOCK }o--|| CID : identified_by

The entity model above captures the key design move: agents do not only write “facts.” They write artifacts with provenance, those artifacts are abstracted hierarchically, and the traversal layer uses indexes plus causal/entity edges instead of timestamps to discover relevant memory. That pattern is strongly aligned with MATM, G-Memory, MAGMA, and content-addressed DAG systems.

Design Goals and Constraints

The first design goal is specialization without isolation. A transactive system should let agents specialize, but those specializations must remain discoverable by others. MATM’s producer/consumer formulation is useful here because it turns memory into a reusable population-level asset instead of a per-agent private cache. In engineering terms, that means the system should preserve agent identity, capability, provenance, and artifact lineage so that retrieval can model which producer’s memory is worth trusting for a given consumer and task.

The second goal is credibility and trustability. Human transactive memory relies on credibility; machine transactive memory should make credibility machine-checkable. The strongest ways to do that without timestamps are content addressing, cryptographic signatures, hash-linked causal histories, and verifiable append-only feeds. IPFS gives self-certifying content via CIDs, Merkle-CRDTs show how Merkle DAGs can act as logical clocks, and Secure Scuttlebutt demonstrates how signed append-only feeds can converge through gossip without any central host.

The third goal is coordination under churn. In an open or large system, agents can join, leave, crash, or become partitioned. Designs whose metadata scales with a fixed replica set are therefore fragile. That is why many timestamp-free alternatives are really membership-aware metadata designs: dotted version vectors reduce irrelevant causality metadata, interval tree clocks handle dynamic participants without global IDs, Merkle clocks decouple causal identity from the explicit list of replicas, and Bloom/probabilistic causal contexts trade exactness for scalability when system size becomes extreme.

The fourth goal is crawlability with bounded work. A hierarchical shared memory is only useful if agents can find relevant content quickly. That requires at least three indexing layers: a primary integrity index such as content addressing or an ordered Merkle tree, a secondary retrieval index such as vector, lexical, or graph embeddings, and a structural traversal index that lets the system walk parent/child, causal, entity, and task-similarity edges. In modern agent systems, hybrid retrieval methods that combine semantic similarity with structural traversal are consistently outperforming one-dimensional memory access.

The fifth goal is minimal dependence on physical time. Physical timestamps make some policies easy, but they introduce correctness hazards in distributed settings. Even outside adversarial environments, unsynchronized clocks can yield anomalies; in open or partially trusted networks, timestamp-based schemes are additionally vulnerable to manipulation. The design implication is straightforward: use physical time, if at all, only for observability, expiration hints, or background scheduling, not for authoritative ordering or conflict resolution.

The main constraints follow directly from the literature. Exact causality tracking is expensive at large scale. CRDT metadata can grow faster than payloads. Full-history Merkle approaches are elegant but can become heavy without pruning or compaction. Byzantine tolerance is possible for CRDT-style systems, but the cost of signatures, access control, and encrypted fields can be substantial. Recent secure CRDT work shows overheads can rise dramatically, including large data-size multipliers in fine-grained encrypted designs.

flowchart TD
    A[Agent local working memory] --> B[Artifact encoder]
    B --> C[Immutable content-addressed block store]
    B --> D[Causal metadata layer]
    D --> E[Hierarchical summary graph]
    C --> F[Integrity crawl by CID]
    E --> G[Semantic index]
    E --> H[Structural graph index]
    D --> I[Session/causal frontier]
    G --> J[Retriever]
    H --> J
    F --> J
    I --> J
    J --> K[Context builder]
    K --> L[Consumer agent plan/execution]

This layered architecture makes the constraints manageable because the most expensive invariants are not imposed globally. Integrity comes from the immutable block layer, causality from the metadata layer, retrieval efficiency from the graph and secondary indexes, and strict coordination only where it is truly needed. That “small strong core, large weak shell” pattern is the most defensible design under the available evidence.

Timestamp-Free Metadata and Consistency Semantics

The most important metadata design choice is the replacement of physical timestamps with causal or structural metadata. The candidate families are not interchangeable. Lamport clocks give cheap ordering but cannot fully distinguish causality from concurrency. Version vectors and vector clocks are precise but grow with the number of participants. Dotted version vectors improve precision and scalability for optimistic replication, especially when clients are numerous. Interval tree clocks support dynamic membership without global IDs. Merkle clocks encode causality in the DAG shape itself. Bloom clocks and other probabilistic causal structures reduce metadata cost but allow false positives. Tree clocks reduce update costs relative to vector clocks in some settings.

The following comparison is the most relevant metadata matrix for a timestamp-free multi-agent memory:

A practical design should therefore avoid the false binary of “vector clocks or nothing.” For open agent ecosystems, the most compelling modern option is Merkle-clocked content-addressed history combined with smaller local causal summaries. Merkle-CRDTs show why: a root CID can announce the current frontier, peers can pull only missing DAG fragments, and immutable nodes make duplicate, reordered, or corrupted deliveries easier to detect. At the same time, the same paper candidly notes the downside: causal information grows with every event and therefore needs compaction strategies.

Consistency semantics should also be split by layer rather than treated globally. Eventual consistency guarantees convergence if updates stop, but says little about when replicas agree. Strong eventual consistency adds the crucial guarantee that replicas receiving the same set of updates will be in the same state. CRDTs are the canonical mechanism for SEC. This is a good fit for shared summaries, sets of entities, inverted indexes, reputation accumulators, and other “always available but convergent” structures in agent memory.

Causal consistency is the right fit when agents need coherent narratives across related writes, such as plan revisions, delegation chains, or evidence trails. Systems like COPS show how explicit dependency metadata can provide scalable causal+ consistency across keys, and more recent systems like CausalMesh show that causal guarantees remain important even in modern serverless and mobile execution environments. For multi-agent memory, this is the natural semantics for “an agent should not read the consequence of a plan without also reading the plan revision that caused it.”

Strong consistency—more precisely, linearizable or strictly serializable coordination—should be reserved for the narrow slice of memory where ambiguity is unacceptable: task leasing, lock ownership, budget allocation, one-writer leadership, or published “authoritative” world state. Consensus protocols such as Raft achieve this with logical terms and log indices rather than wall-clock timestamps, and the Raft paper is explicit that safety does not depend on timing even though availability can. That is exactly the right model for “timestamp-free strong memory” in this context.

Synchronization and coordination protocols then follow naturally from the chosen consistency layer. For high-availability replicated structures, the dominant approach is gossip or anti-entropy. Delta-CRDTs reduce synchronization cost by shipping deltas rather than full state, Merkle DAG sync reduces redundant transfer by content identity, and Merkle Search Trees provide an efficient anti-entropy primitive for state-based CRDTs in open networks. For strong coordination, use leader-based consensus rather than trying to force CRDTs to solve exclusive allocation.

sequenceDiagram
    participant P as Producer Agent
    participant L as Local Replica
    participant B as Broadcaster
    participant R as Remote Replica
    participant S as Shared Index

    P->>L: append artifact block + causal predecessors
    L->>L: compute CID and update local frontier
    L->>B: broadcast new root/frontier identifier
    B->>R: announce frontier
    R->>L: pull missing DAG nodes by CID
    R->>R: merge CRDT payloads and causal frontier
    R->>S: update summary/entity/semantic indexes
    Note over L,R: No wall-clock ordering required; causality comes from predecessors/frontiers

This sequence reflects the cleanest timestamp-free coordination pattern found across the literature: announce a frontier, pull immutable missing content, merge using join-semilattice or log rules, and only escalate to consensus when the update touches a resource that cannot be represented as a monotone merge. That pattern is much more robust than timestamped last-writer-wins.

Conflict resolution should likewise be data-type-aware. CRDTs work because conflicts are encoded into the data type rather than handled generically after the fact. Sets may use add-wins, remove-wins, causal lengths, or observed-remove semantics. Ordered sequences require more specialized designs. Relational views and integrity constraints are possible, but only with richer replicated semantics, as works such as CRDV and Synql demonstrate. The design rule is simple: if the application meaning of a conflict matters, do not rely on a universal timestamp rule; use a domain-specific replicated type or put the operation behind consensus.

Architecture Blueprints

The most practical timestamp-free blueprint is a four-plane architecture.

The artifact plane stores immutable blocks, trajectories, summaries, plans, and extracted entities in a content-addressed store. IPFS-like design is the canonical reference: CIDs identify content by hash rather than location, files are chunked into Merkle DAGs, root objects can have multiple parents, and retrieval can occur from any peer that advertises the blocks. This plane gives deduplication, tamper evidence, and deterministic crawlability.

The causal plane stores logical predecessor links, causal frontiers, version summaries, and optional per-object clocks. Here the best default is a hybrid: hash-linked event history for durable provenance and compact local causal summaries for fast sessions and queries. Merkle-CRDTs show that a Merkle DAG can encode the same causal information as more conventional logical clocks, while ITCs and dotted version vectors remain useful where per-object compactness matters more than whole-history verifiability.

The hierarchy plane organizes memory into multiple abstraction layers. A strong blueprint is: step/event → episode/trajectory → task/query → insight/skill/entity cluster. That matches G-Memory’s insight/query/interaction hierarchy, is compatible with MATM’s shared trajectory repository, and is conceptually close to MAGMA’s separation of semantic, entity, causal, and other relational views. This plane is what makes the memory genuinely transactive instead of merely archival.

The coordination plane keeps only the irreducibly exclusive state under strong consistency: leader leases, schema evolution, policy anchors, key-rotation manifests, quota ledgers, and “published truth” snapshots. This plane should be small and consensus-backed. Everything else should remain available under partitions. Raft’s term/index log is the cleanest timestamp-free control plane under crash faults. If Byzantine tolerance is required, that becomes a separate design decision; it should not infect the whole memory substrate by default.

A concrete logical schema can look like this:

Artifact {
  cid: CID
  kind: event | trajectory | summary | plan | entity | policy
  producer: AgentID
  parents: Set<CID>              // structural containment
  causal_prev: Set<CID>          // direct causal predecessors
  payload_ref: CID               // content block
  signatures: Set<Signature>
}

SummaryNode {
  sid: CID
  level: interaction | query | insight | skill | entity_cluster
  covers: Set<CID>               // artifacts summarized
  embeddings_ref: CID
  entity_refs: Set<EntityID>
  causal_frontier_ref: CID
}

IndexEntry {
  iid: CID
  key: lexical | vector | graph | route_hint
  points_to: CID
  scope: local | shard | global
}

SessionContext {
  agent: AgentID
  frontier: Set<CID>             // causal cut, not timestamp
  trust_profile: Map<AgentID, Score>
  retrieval_policy: PolicyID
}

That schema deliberately separates payload identity, causal identity, hierarchical abstraction, and retrieval metadata. This separation is one of the clearest lessons from both distributed systems and modern agent memory: representation, consistency, and retrieval should not be collapsed into one table or one vector index.

A concrete API surface can remain small:

POST /artifacts.append
GET  /artifacts/{cid}
POST /frontier.announce
POST /sync.pullMissing
POST /summaries.upsert
POST /index.upsert
POST /retrieve.plan
POST /retrieve.execute
POST /session.advanceFrontier
POST /policy.publish        // consensus-backed
GET  /proof.membership/{cid}

Semantically, append creates immutable artifacts, announce shares only the new frontier, pullMissing performs Merkle or DAG-based anti-entropy, advanceFrontier moves an agent’s causal cut, and policy.publish is the exceptional strongly consistent call. This style is directly inspired by Merkle-CRDTs’ DAG-Syncer/Broadcaster split and by content-addressed retrieval systems.

For indexing and crawl, the most robust design is multi-indexed:

This layered crawl path is especially important for multi-agent use because not every memory access should begin with a semantic vector lookup. Sometimes the correct entry point is a causal frontier, sometimes an entity cluster, and sometimes a producer reputation or policy scope. Recent graph-memory results strongly support this richer traversal model.

Evaluation Methodology and Metrics

A rigorous evaluation should validate correctness, retrieval quality, scalability, fault tolerance, and security overhead independently. Recent agent-memory evaluation work argues that memory should not be benchmarked only by end-to-end task success; it should be decomposed into representation/storage, extraction, retrieval/routing, and maintenance. That framing is highly appropriate here because timestamp-free designs often win on correctness and robustness while paying costs in metadata or maintenance that are invisible in a single task-success score.

Correctness evaluation should start with formal invariants rather than benchmarks. At minimum, the model should specify: immutable artifacts never change after publication; causal edges are acyclic; replicas that have integrated the same update set converge on the same CRDT state; a session frontier never regresses; and consensus-backed control-plane decisions always reflect a prefix of the authoritative log. Existing work on verifying strong eventual consistency and on model checking CRDT applications shows that these properties are tractable targets for formal reasoning and systematic randomized testing.

The experimental methodology should then separate three workload families. First, memory-construction workloads: append rate, summary compaction, graph growth, and causal frontier growth. Second, memory-retrieval workloads: semantic lookup, causal replay, hierarchical crawl depth, best-first graph traversal, and mixed retrieval plans. Third, memory-maintenance workloads: anti-entropy after partition, recovery after replica loss, key rotation, reindexing, and garbage-collection or compaction. That decomposition mirrors the newest system-level agent-memory evaluations and avoids overfitting to any one benchmark style.

For quantitative metrics, the following set is sufficient and well grounded:

A serious fault-injection campaign should vary replica count, churn rate, partition duration, Byzantine fraction, query locality, and producer/consumer heterogeneity. That is especially important because recent agent-memory work shows that no one architecture dominates all workloads; retrieval gains are often workload-dependent, and locality or update dynamics can reverse rankings between graph, append-only, and flat semantic designs.

The evaluation should also include cross-layer ablations. For example: replace Merkle-clocked causality with dotted version vectors; replace graph traversal with vector-only retrieval; replace causal sessions with eventual-only reads; replace CRDT summaries with consensus-managed mutable summaries; and measure both system metrics and agent-task metrics. MATM already shows that retrieval and reranking materially improve downstream performance, while G-Memory and HiGraAgent show the value of hierarchy and hybrid retrieval. A timestamp-free system should therefore be judged not just by correctness, but by whether its richer structure yields measurable gains in agent utility.

Comparative Assessment and Recommended Designs

At the design-pattern level, there are four serious candidates.

The first is the flat semantic memory store: vector index plus mutable records, usually with application-level rewriting. This is easy to prototype, but it is the weakest fit for the problem because it has poor provenance, weak causal semantics, and limited crawlability. It can answer “what looks similar?” but not reliably “what caused this?”, “what can I prove?”, or “which producer should I trust?” Recent graph-memory evaluations are effectively a running critique of this flat pattern.

The second is the CRDT-only shared memory pattern. This has excellent availability and convergence properties, and it is the right basis for many mutable summaries and indexes. However, by itself it is often insufficient for rich agent memory because it does not automatically provide audit-friendly history, content-addressed traversal, or efficient ordered diff over large artifact sets. As the literature repeatedly shows, the “hard parts” of CRDTs are not just convergence; they are metadata growth, move semantics, access control, and intent preservation.

The third is the Merkle/log-centric open-network design: signed append-only feeds or logs, content-addressed DAGs, and gossip anti-entropy. This is the strongest baseline for open or partially trusted agent ecosystems because it naturally supports provenance, repair after partitions, auditability, and decentralized crawl. Merkle-CRDTs, Secure Scuttlebutt, and Merkle Search Trees all point in this direction. Its main weakness is the need for careful compaction and secondary indexing.

The fourth is the mixed-consistency hierarchical memory fabric: immutable artifact history, CRDT-derived hierarchical summaries, semantic plus structural traversal, and a tiny consensus-backed control plane. This is the recommended architecture for most serious multi-agent systems because it combines the strengths of the other three while confining their weaknesses. It is also the design most consistent with the latest agent-memory systems, which increasingly separate raw memory, abstracted memory, retrieval policy, and maintenance.

The following recommendation table summarizes the trade space:

The default recommendation, then, is:

Recommended baseline architecture

Use content-addressed immutable artifacts as the source of truth, with signed per-agent append-only feeds or equivalent author-scoped logs; encode causal history through hash-linked predecessors plus causal frontiers; maintain hierarchical summaries as CRDTs; expose multi-index retrieval over semantic, structural, entity, and causal dimensions; and reserve consensus for policy anchors, exclusive coordination, and publish-once authoritative snapshots. This recommendation is the best fit for the research record and is resilient to the unspecified assumptions in the prompt.

Recommended variants by assumption

If the target network is small and stable, exact vector-style causality remains viable and may be simpler. If the network is large and dynamic, prefer Merkle clocks, ITCs, or probabilistic causal contexts over replica-list metadata. If the system is privacy-sensitive or adversarial, use signed/hash-linked histories and consider secure or Byzantine-tolerant CRDT techniques, while budgeting for the overhead. If the system is task-critical and coordination-heavy, push a slightly larger portion of state into the consensus plane rather than overburdening CRDT conflict semantics.

Open Research Questions

The first major open question is how to compact timestamp-free causal history without destroying crawlability or proofability. Merkle-clock designs elegantly preserve causality and auditability, but their histories grow with events. The literature is clear on the upside and downside, but not yet on a universally good compaction regime for agent memory with rich summaries, partial replication, and selective forgetting.

A second open question is how to combine transactive trust with retrieval quality. MATM already hints that producer metadata and producer capability matter for downstream utility, effectively turning retrieval into a trust-modeling problem. That opens a large research space around reputation, expertise routing, negative evidence, and adversarial retrieval poisoning in shared agent memory.

A third open question is how to support privacy-preserving search over encrypted, content-addressed, causally ordered memory. Secure CRDT work shows that confidentiality, integrity, dynamic membership, and SEC can coexist, but at meaningful overhead. Efficient encrypted secondary indexes, private semantic retrieval, and privacy-preserving graph traversal remain far from solved in practice.

A fourth open question is how much exact causality agents really need. The current toolbox ranges from exact vectors and ITCs to Bloom clocks and probabilistic causal contexts. For human-facing applications or exploratory agent swarms, approximate causality may be perfectly acceptable if it materially improves scale. For regulated or safety-critical domains, it may not be. The right choice is therefore workload-dependent, and this remains under-evaluated in agent-memory research.

A fifth open question is evaluation itself. Recent work on agent memory argues that current benchmarks still overweight end-to-end task metrics and underweight update correctness, maintenance cost, and long-horizon stability. That critique applies even more strongly to distributed, shared, timestamp-free memory. The field still lacks a de facto standard benchmark suite that jointly measures convergence, retrieval utility, compaction quality, trust robustness, and privacy overhead for multi-agent shared memory.

The highest-confidence conclusion, despite those open questions, is straightforward: a timestamp-free multi-agent transactive memory is not only feasible, but better engineered when built from causal structure rather than wall-clock order. The best current evidence favors a hierarchical, content-addressed, graph-and-CRDT-backed design with selective consensus, not a timestamped last-writer-wins store. That is the design most likely to remain correct under churn, partitions, partial trust, and long-horizon agent collaboration.