Kefli - CBAA/CBBA Library for Rust

Kefli is a Rust implementation of the Consensus-Based Auction Algorithm (CBAA) and Consensus-Based Bundle Algorithm (CBBA) for distributed task allocation. These algorithms are particularly useful in multi-agent systems where autonomous agents need to coordinate and agree on task assignments without centralized control.

Acknowledgment

The algorithms implemented in this crate were originally developed and published by:

H.-L. Choi, L. Brunet, and J. P. How,
Consensus-Based Decentralized Auctions for Robust Task Allocation,
IEEE Transactions on Robotics, vol. 25, no. 4, pp. 912-926, Aug. 2009.
DOI: 10.1109/TRO.2009.2022423 | IEEE Xplore Link

This crate is an independent, from-scratch reimplementation of the algorithms in Rust.
It does not redistribute or copy any of the original article's text, figures, or code; only the algorithmic ideas have been re-expressed.
If you use this crate in academic work, please cite the original paper above.

Name

The crate is named Kefli after the Old Norse word kefli, meaning a wooden staff, stick, or cylinder.
In medieval Scandinavian law texts, laga-kefli referred to a law-staff — a symbol of authority and decision-making.

This is a fitting metaphor for a library that provides consensus-based auction algorithms:
just as the kefli represented authority and resolution in legal assemblies, the algorithms here
serve as the mechanism for reaching agreement and assigning tasks in distributed multi-agent systems.

Features

• CBAA: Single-assignment consensus-based auctions
• CBBA: Multi-assignment consensus-based bundle auctions
• Generic Design: Works with any task and agent types
• Configurable: Flexible cost functions and network topologies
• Async-Ready: Designed to work with async/await patterns
• Lightweight core: optional dependencies only

Installation

Add this to your Cargo.toml:

[dependencies]
kefli = "0.1.0"

Quick Start

use kefli::*;

// Define your task and agent types
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Task(u32);

#[derive(Debug, Clone, PartialEq, Eq, Hash, Copy)]  
struct Agent(u32);

// Implement a cost function
struct SimpleCostFunction;

impl CostFunction<Task, Agent> for SimpleCostFunction {
    fn calculate_cost(&self, agent: Agent, task: &Task, _context: &AssignmentContext<Task, Agent>) -> f64 {
        // Simple example: prefer lower task IDs
        100.0 - task.0 as f64
    }
}

// Create and run CBAA
let agent_id = Agent(1);
let cost_function = SimpleCostFunction;
let available_tasks = vec![Task(1), Task(2), Task(3)];

let mut cbaa = CBAA::new(agent_id, cost_function, available_tasks, None);

// Phase 1: Auction
let result = cbaa.auction_phase()?;

// Phase 2: Consensus (process messages from network)
let messages = vec![]; // Get from your network handler
cbaa.consensus_phase(messages)?;

// Get result
if let Some(assigned_task) = cbaa.get_assignment() {
    println!("Agent {:?} assigned to task {:?}", agent_id, assigned_task);
}

Library Structure

The library is organized into several modules:

Core Modules

• types - Core types and traits (Task, AgentId, CostFunction, etc.)
• error - Error types and handling
• config - Configuration structures for algorithms
• network - Network communication abstractions
• cbaa - Single-assignment CBAA implementation
• cbba - Multi-assignment CBBA implementation

Key Types

• CBAA<T, A, C> - Single-assignment algorithm
• CBBA<T, A, C> - Multi-assignment algorithm
• AuctionConfig - Configuration parameters
• ConsensusMessage<A, T> - Messages for consensus
• NetworkHandler<A, T> - Trait for network communication

Examples

The library includes several examples:

Simple Auction

// Run with: cargo run --example simple_auction
// Shows basic CBAA usage with delivery tasks

Elevator Dispatch System

// Run with: cargo run --example elevator_system
// Comprehensive P2P elevator dispatch implementation

Algorithm Background

The algorithms are based on the paper:

Choi, H. L., Brunet, L., & How, J. P. (2009). Consensus-based decentralized auctions for robust task allocation. IEEE Transactions on Robotics, 25(4), 912-926.

CBAA (Single Assignment)

1. Auction Phase: Agents bid on tasks with highest reward
2. Consensus Phase: Exchange winning bids and resolve conflicts
3. Convergence: Repeat until stable assignment reached

CBBA (Multi Assignment)

1. Bundle Construction: Build bundle of tasks greedily
2. Conflict Resolution: Handle complex multi-task conflicts
3. Convergence: Account for task dependencies

Configuration

Configure algorithms via AuctionConfig:

use std::time::Duration;

let config = AuctionConfig::cbba(3)  // Max 3 tasks per agent
    .with_network_diameter(5)        // Network diameter of 5
    .with_timeout(Duration::from_secs(2))  // 2 second timeout
    .with_async_resolution(true);    // Enable async conflict resolution

// Or use convenience methods:
let config = AuctionConfig::cbba(3)
    .with_timeout_secs(2)           // 2 seconds
    .with_timeout_ms(1500);         // 1.5 seconds

Network Integration

Implement NetworkHandler for your network:

impl NetworkHandler<AgentId, TaskType> for MyNetworkHandler {
    fn send_message(&mut self, message: ConsensusMessage<AgentId, TaskType>) -> Result<(), AuctionError> {
        // Send over your network protocol
    }
    
    fn receive_messages(&mut self) -> Result<Vec<ConsensusMessage<AgentId, TaskType>>, AuctionError> {
        // Receive pending messages  
    }
    
    fn get_neighbors(&self) -> Vec<AgentId> {
        // Return neighbor list
    }
}

Performance Guarantees

As shown in Choi, Brunet & How (2009), both CBAA and CBBA provide theoretical guarantees:

• Convergence: Finite time to conflict-free assignment
• Optimality: At least 50% optimal solutions
• Robustness: Tolerant to network changes and failures

Use Cases

• Robotics: Multi-robot task allocation and coordination
• Elevators: Distributed elevator dispatch (see example)
• Logistics: Vehicle routing and delivery optimization
• Cloud Computing: Distributed task scheduling
• IoT: Sensor network coordination

Testing

Run tests with:

cargo test                    # Unit tests
cargo test --test integration # Integration tests

License

Dual-licensed under either:

• MIT license (see LICENSE), or
• Apache-2.0 license (see LICENSE-APACHE)

You may choose either license at your option.

Citation

If you use Kefli, please cite this software (see CITATION.cff) and the original paper:

Choi, H.-L., Brunet, L., & How, J. P. (2009). 'Consensus-Based Decentralized Auctions for Robust Task Allocation.' IEEE Transactions on Robotics, 25(4), 912–926. DOI: 10.1109/TRO.2009.2022423

Notice

See NOTICE for attribution details. The NOTICE file is informational and does not modify the license terms.

Contributing

Contributions welcome! Please feel free to submit issues and pull requests.