Internet-Draft Agent Consensus March 2026
Nennemann Expires 7 September 2026 [Page]
Workgroup:
NMOP
Internet-Draft:
draft-nennemann-agent-consensus-00
Published:
Intended Status:
Standards Track
Expires:
Author:
C. Nennemann
Independent Researcher

Multi-Agent Consensus and Capability Negotiation Protocols

Abstract

This document defines standardized protocols for multiple AI agents to reach consensus on shared decisions and negotiate capabilities dynamically during runtime collaboration. As autonomous agent systems increasingly operate in multi-agent configurations, the need for formal agreement mechanisms and capability discovery becomes critical. This specification addresses the lack of consensus protocols and capability negotiation standards identified in the gap analysis for AI agent infrastructure.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on 7 September 2026.

▲

Table of Contents

1. Introduction

When multiple AI agents collaborate on shared tasks such as network management, resource allocation, or policy enforcement, they must frequently agree on joint decisions. Currently, no standardized protocol exists for agents to propose actions, vote on alternatives, reach quorum, or handle disagreements.

This document addresses Gap 3 (Multi-Agent Consensus) and Gap 10 (Capability Negotiation) from the gap analysis [I-D.nennemann-agent-gap-analysis]. Gap 3 identifies the absence of formal consensus mechanisms for multi-agent coordination, while Gap 10 highlights the lack of dynamic capability negotiation during runtime collaboration.

The protocols defined here enable agents to:

The human-in-the-loop override protocol defined in [I-D.nennemann-agent-dag-hitl-safety] serves as the ultimate escalation path when consensus cannot be reached or when decisions exceed agent authority.

2. Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

The following terms are used throughout this document:

Consensus Round:

A bounded period during which agents exchange proposals and votes to reach agreement on a specific decision.

Quorum:

The minimum number of participating agents required for a consensus round to produce a valid outcome.

Proposal:

A structured message submitted by an agent that describes a candidate action or decision for group consideration.

Vote:

A response to a proposal indicating approval, rejection, or abstention, optionally accompanied by a rationale.

Leader Agent:

An agent designated as the coordinator for a consensus round, responsible for collecting votes and declaring outcomes.

Capability Advertisement:

A structured declaration by an agent of the capabilities it offers to other agents in a collaboration.

Capability Offer:

A message proposing the use of a specific capability under defined terms during a negotiation session.

Capability Acceptance:

A binding confirmation that an agent agrees to the terms of a capability offer.

Negotiation Session:

A bounded interaction between two or more agents for the purpose of agreeing on capability usage terms.

3. Consensus Protocols

3.1. Consensus Model Overview

The consensus protocol follows a three-phase commit model: propose, vote, and commit. The following diagram illustrates the message flow for a typical consensus round.

  Agent A          Leader           Agent B         Agent C
    |                 |                |                |
    |--- Propose ---->|                |                |
    |                 |-- Vote Req --->|                |
    |                 |-- Vote Req ------------------>  |
    |                 |                |                |
    |                 |<-- Vote -------|                |
    |                 |<-- Vote ----------------------  |
    |                 |                |                |
    |                 |--- Tally & Decide ---------->   |
    |<-- Commit ------|                |                |
    |                 |-- Commit ----->|                |
    |                 |-- Commit ------------------->   |
    |                 |                |                |
Figure 1: Consensus Round Message Flow

  1. Propose: An agent submits a proposal to the leader agent.

  2. Vote: The leader distributes the proposal to all participants and collects votes within the timeout window.

  3. Commit/Abort: The leader evaluates votes against the quorum and consensus mechanism rules, then issues a commit or abort signal to all participants.

3.2. Consensus Mechanisms

This specification defines four consensus mechanisms. Implementations MUST support simple majority voting and SHOULD support at least one additional mechanism.

3.2.1. Simple Majority Voting

A proposal is accepted if more than half of the votes received are approvals. Abstentions do not count toward the total.

  • Quorum: A minimum of ceil(N/2) votes must be received, where N is the number of eligible voters.

  • Ties result in rejection of the proposal.

3.2.2. Weighted Consensus

Each agent is assigned a weight reflecting its trust score, domain expertise, or capability level. A proposal is accepted if the sum of approval weights exceeds a configured threshold (default: 50% of total weight).

  • Weights MUST be distributed and agreed upon before the consensus round begins.

  • Weight assignments SHOULD be recorded in the ECT for auditability.

3.2.3. Leader-Based Consensus

A designated leader agent makes the final decision after soliciting input from participants. Participant votes serve as advisory input rather than binding decisions.

  • The leader MUST provide a rationale when overriding participant recommendations.

  • Leader designation SHOULD rotate or be determined by a higher-level policy.

  • This mechanism is appropriate for time-critical decisions where full consensus would introduce unacceptable delay.

3.2.4. Optimistic Consensus

A proposal is considered accepted unless an objection is raised within the timeout window. This mechanism minimizes communication overhead for routine decisions.

  • Any single objection blocks the proposal.

  • The objecting agent MUST provide a rationale.

  • Optimistic consensus SHOULD only be used for low-risk, reversible decisions.

3.3. Consensus Message Format

3.3.1. Proposal Message Structure

A proposal message MUST contain the following fields:

  • proposal_id: A globally unique identifier for the proposal (UUID format).

  • proposer: The identity of the proposing agent.

  • consensus_round_id: Identifier for the consensus round.

  • mechanism: The consensus mechanism to use (one of "majority", "weighted", "leader", "optimistic").

  • subject: A human-readable summary of the proposal.

  • action: A structured description of the proposed action.

  • timeout: The deadline for vote collection (as an absolute timestamp per [RFC9110] Section 5.6.7).

  • quorum: The minimum number of votes required.

  • participants: List of agent identifiers eligible to vote.

3.3.2. Vote Message Structure

A vote message MUST contain the following fields:

  • proposal_id: The identifier of the proposal being voted on.

  • voter: The identity of the voting agent.

  • decision: One of "approve", "reject", or "abstain".

  • rationale: A human-readable explanation for the vote (REQUIRED for "reject", OPTIONAL for others).

  • timestamp: The time the vote was cast.

  • signature: A JWS [RFC7515] signature over the vote content for non-repudiation.

3.3.3. Commit and Abort Signals

After vote collection, the leader issues either a commit or abort signal:

  • Commit: Indicates the proposal was accepted. All participants MUST execute the agreed action.

  • Abort: Indicates the proposal was rejected. Participants MUST NOT execute the proposed action.

Both signals MUST include the proposal_id, the final tally, and a JWS signature from the leader.

3.4. Quorum and Timeout Rules

3.4.1. Quorum Calculation

The quorum for a consensus round is determined by the consensus mechanism in use:

  • Simple majority: ceil(N/2) where N is the number of eligible voters.

  • Weighted: Agents representing at least 50% of total weight must participate.

  • Leader-based: No quorum required; leader decides independently.

  • Optimistic: All eligible agents are considered participants; silence counts as approval.

3.4.2. Timeout Semantics and Fallback Behavior

Each consensus round MUST specify a timeout. If quorum is not reached before the timeout:

  1. The leader MUST issue an abort signal.

  2. The proposing agent MAY re-submit the proposal with a longer timeout or reduced quorum.

  3. If the decision is time-critical, the leader MAY escalate to a human operator via the override protocol defined in [I-D.nennemann-agent-dag-hitl-safety].

Implementations SHOULD use exponential backoff for re-submissions with a maximum retry count of 3.

3.4.3. Split-Brain Prevention

In distributed deployments where network partitions may occur:

  • A consensus round is valid only if the leader can verify connectivity to a majority of participants.

  • If a partition is detected, all in-progress consensus rounds MUST be suspended until connectivity is restored.

  • Agents MUST NOT accept commit signals from multiple leaders for the same consensus round.

3.5. Conflict Resolution

3.5.1. Priority-Based Resolution

When multiple competing proposals address the same resource or decision:

  • Proposals are ranked by a priority score derived from the urgency of the decision, the authority level of the proposer, and the specificity of the proposed action.

  • Higher-priority proposals are evaluated first.

  • Lower-priority proposals that conflict with an accepted higher-priority proposal are automatically rejected.

3.5.2. Escalation to Human Operator

If consensus cannot be reached after the maximum number of retries, or if agents are deadlocked:

  • The leader MUST escalate to a human operator using the override protocol defined in [I-D.nennemann-agent-dag-hitl-safety].

  • The escalation message MUST include the proposal, all votes received, and the reason for escalation.

  • The human operator's decision is binding and MUST be recorded in the ECT.

3.5.3. Deadlock Detection and Breaking

A deadlock exists when:

  • Two or more proposals mutually block each other (circular dependency).

  • A consensus round cannot reach quorum due to persistent abstentions or non-responsive agents.

Deadlock breaking strategies:

  1. Timeout-based: The oldest proposal takes precedence.

  2. Random selection: A verifiable random function selects the winning proposal.

  3. Escalation: The deadlock is escalated to a human operator.

The leader MUST detect deadlocks within two consecutive failed consensus rounds on related proposals.

4. Capability Negotiation

4.1. Capability Advertisement Format

4.1.1. Extending Agent Discovery with Capability Descriptors

Agents MUST advertise their capabilities using a structured descriptor format. Capability advertisements extend the agent discovery mechanism and SHOULD be published during agent registration.

A capability descriptor MUST include:

  • agent_id: The identity of the advertising agent.

  • capabilities: An array of capability objects, each containing:

    • type: The capability type from the capability registry (see Section 4.3).

    • version: The version of the capability implementation.

    • parameters: Capability-specific configuration parameters.

    • constraints: Limitations on capability usage (e.g., rate limits, maximum payload size).

    • availability: Current availability status ("available", "busy", "degraded", "unavailable").

4.1.2. Capability Categories

Capabilities are organized into the following categories:

  • Compute: Processing power, model inference, data transformation.

  • Knowledge: Domain expertise, access to knowledge bases, training data coverage.

  • Tool Access: Integration with external tools, APIs, or services.

  • Authorization Scope: Permissions and access levels the agent holds in various systems.

4.1.3. Version and Compatibility Metadata

Each capability advertisement MUST include version information to enable compatibility checking:

  • min_version: The minimum protocol version supported.

  • max_version: The maximum protocol version supported.

  • deprecated_versions: A list of versions that are supported but deprecated.

Agents MUST negotiate a mutually supported version before initiating capability usage.

4.2. Dynamic Negotiation Protocol

4.2.1. Negotiation Initiation and Session Management

A negotiation session is initiated when an agent requires a capability that it does not possess but has identified in another agent's advertisement.

  1. The initiating agent sends a Negotiation Request specifying the desired capability type and parameters.

  2. The target agent responds with a Negotiation Response indicating willingness to negotiate.

  3. A session_id is established for tracking the negotiation.

Sessions have a configurable timeout (default: 60 seconds) and MUST be explicitly closed by either party.

4.2.2. Offer/Counter-Offer Exchange

Once a session is established:

  1. The initiating agent sends a Capability Offer specifying the desired terms of use (duration, rate limits, data handling requirements).

  2. The target agent may respond with:

    • Accept: Agreement to the offered terms.

    • Counter-Offer: Modified terms for the initiator to consider.

    • Reject: Refusal to provide the capability, with a rationale.

  3. Counter-offers may continue for a maximum of 5 rounds before the negotiation MUST be concluded or abandoned.

4.2.3. Acceptance and Binding

When both parties agree on terms:

  • A Capability Agreement is created containing the final terms, signed by both parties using JWS [RFC7515].

  • The agreement includes a unique agreement_id, the agreed capability parameters, duration, and any usage constraints.

  • Both agents MUST honor the agreement until its expiration or explicit revocation.

4.2.4. Re-Negotiation During Runtime

Either party MAY initiate re-negotiation of an active agreement when:

  • Resource availability changes.

  • New constraints are imposed by external factors.

  • The original terms are no longer adequate.

Re-negotiation follows the same offer/counter-offer protocol but references the existing agreement_id.

4.3. Capability Registry

4.3.1. Well-Known Capability Types

The following capability types are defined as initial entries in the capability registry:

Table 1: Well-Known Capability Types
Type ID Category Description
compute.inference Compute Model inference execution
compute.transform Compute Data transformation and processing
knowledge.domain Knowledge Domain-specific expertise
knowledge.retrieval Knowledge Information retrieval from knowledge bases
tool.api Tool Access External API integration
tool.execution Tool Access Tool or script execution
authz.delegate Authorization Delegated authorization scope
authz.verify Authorization Credential and permission verification

4.3.2. Extension Mechanism for Custom Capabilities

Organizations MAY define custom capability types using a reverse domain name prefix (e.g., "com.example.custom-capability"). Custom capability types:

  • MUST NOT conflict with well-known capability type identifiers.

  • SHOULD be registered with IANA for interoperability when intended for broad use.

  • MUST include a human-readable description and a machine-readable schema for parameters.

5. ECT Integration

Consensus and capability negotiation events MUST be recorded in the Execution Chain Trace (ECT) framework defined in [I-D.nennemann-wimse-ect] to provide a verifiable audit trail.

5.1. Consensus Evidence in ECT Nodes

The following exec_act values are defined for consensus operations:

  • consensus_propose: Records the submission of a proposal. The ECT node MUST include the proposal_id, proposer identity, and proposal summary.

  • consensus_vote: Records a vote cast by an agent. The ECT node MUST include the proposal_id, voter identity, decision, and rationale (if provided).

  • consensus_commit: Records the outcome of a consensus round. The ECT node MUST include the proposal_id, final tally, outcome (commit or abort), and the leader's signature.

5.2. Capability Negotiation Records in ECT

Capability negotiation events are recorded using the ECT ext (extension) claims mechanism:

  • The ext claim MUST include a "capability_negotiation" object containing the session_id, capability type, and negotiation outcome.

  • Agreement creation and revocation events MUST each produce an ECT node with the agreement_id and relevant terms.

  • Re-negotiation events MUST reference the original agreement_id and include both the previous and updated terms.

6. Security Considerations

6.1. Sybil Resistance

To prevent an attacker from creating multiple fake agent identities to influence consensus outcomes:

  • Agents MUST authenticate using verifiable credentials bound to their operational identity.

  • The leader MUST verify agent identities before accepting votes.

  • Consensus mechanisms SHOULD incorporate identity verification scores that penalize newly registered or unverified agents.

  • Rate limiting on agent registration prevents rapid creation of sybil identities.

6.2. Byzantine Fault Tolerance Considerations

The consensus mechanisms defined in this document do not provide full Byzantine fault tolerance (BFT). Deployments requiring BFT guarantees SHOULD:

  • Use weighted consensus with trust scores that reflect agent reliability history.

  • Implement cross-validation of votes through independent verification channels.

  • Set quorum thresholds to at least 2f+1 where f is the maximum number of potentially faulty agents.

  • Consider established BFT protocols (e.g., PBFT) as an alternative consensus mechanism for high-security environments.

6.3. Capability Spoofing

Agents MUST NOT advertise capabilities they do not possess. Mitigations include:

  • Capability advertisements MUST be signed using the agent's verified credentials.

  • Consumers SHOULD validate capability claims through test invocations before relying on them for critical operations.

  • Agents that fail to deliver advertised capabilities MUST have their trust scores reduced.

  • Repeated capability spoofing SHOULD result in exclusion from future consensus rounds and negotiation sessions.

6.4. Coercion and Collusion Detection

To detect coordinated manipulation of consensus outcomes:

  • Vote patterns SHOULD be analyzed for statistical anomalies (e.g., identical rationales, synchronized timing).

  • Agents SHOULD be required to submit votes independently without knowledge of other agents' votes until the tally is complete (sealed-bid voting).

  • The ECT audit trail enables post-hoc analysis of voting patterns to identify potential collusion.

  • Human operators SHOULD be notified when anomalous voting patterns are detected.

7. IANA Considerations

7.1. Consensus exec_act Values

This document requests registration of the following exec_act values in the ECT exec_act registry:

Table 2: Consensus exec_act Values
Value Description Reference
consensus_propose Agent submits a consensus proposal This document
consensus_vote Agent casts a vote on a proposal This document
consensus_commit Leader commits or aborts a consensus round This document

7.2. Capability Type Registry

This document requests IANA to create a new "Agent Capability Types" registry with the following initial entries as defined in Table 1.

New entries in this registry require Specification Required (per [RFC8126]) and MUST include:

  • A unique type identifier.

  • The capability category.

  • A human-readable description.

  • A reference to the defining specification.

8. References

8.1. Normative References

[I-D.nennemann-agent-dag-hitl-safety]
"Agent Context Policy Token: DAG Delegation with Human Override", n.d., <https://datatracker.ietf.org/doc/draft-nennemann-agent-dag-hitl-safety/>.
[I-D.nennemann-wimse-ect]
"Execution Context Tokens for Distributed Agentic Workflows", n.d., <https://datatracker.ietf.org/doc/draft-nennemann-wimse-ect/>.
[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/rfc/rfc2119>.
[RFC7515]
Jones, M., Bradley, J., and N. Sakimura, "JSON Web Signature (JWS)", RFC 7515, DOI 10.17487/RFC7515, , <https://www.rfc-editor.org/rfc/rfc7515>.
[RFC7519]
Jones, M., Bradley, J., and N. Sakimura, "JSON Web Token (JWT)", RFC 7519, DOI 10.17487/RFC7519, , <https://www.rfc-editor.org/rfc/rfc7519>.
[RFC8174]
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/rfc/rfc8174>.
[RFC9110]
Fielding, R., Ed., Nottingham, M., Ed., and J. Reschke, Ed., "HTTP Semantics", STD 97, RFC 9110, DOI 10.17487/RFC9110, , <https://www.rfc-editor.org/rfc/rfc9110>.

8.2. Informative References

[I-D.nennemann-agent-gap-analysis]
"Gap Analysis for Autonomous Agent Protocols", n.d., <https://datatracker.ietf.org/doc/draft-nennemann-agent-gap-analysis/>.
[RFC8126]
Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, , <https://www.rfc-editor.org/rfc/rfc8126>.

Acknowledgments

The author thanks the contributors to the NMOP working group discussions on AI agent orchestration and multi-agent coordination challenges.

Author's Address

Christian Nennemann
Independent Researcher