其它计算机科学 · 2026年9月30日(周三)

分布式计算、博弈论、信息论等。

★★★★☆ 值得关注
arXiv cs.GT

Generalized Prophet Inequalities for Online Auctions

说明在线拍卖中的广义先知不等式:考虑预算与多样化目标的代理人

简介该论文研究在线拍卖中的先知不等式问题。传统模型假设代理人只最大化拟线性效用,而现实中代理人常受预算约束,且目标可能不同(如自动竞价中的价值最大化者)。作者将代理人的目标类型与预算视为与估值分布类似的随机输入,分析了匿名定价机制,并推广了平衡价格框架。论文给出了一些核心设定下的常数竞争比,包括次可加估值函数,并刻画了竞争比与代理人价格敏感度之间的权衡,还给出了从有预算情形到无预算价值最大化者的一般归约。

看点将预言不等式拓展到预算约束与混合目标的随机代理,给出多种设定下的常数竞争比及从预算到无预算的归约,证明较完整。

Twan Kroll, Rebecca Reiffenh\"auser

arXiv cs.DC

From Pilots to Production: Lessons in Cross-Institutional Federated Training and Artificial Intelligence for Science

说明从试点到生产:跨机构联邦训练与科学人工智能的经验

简介许多有价值的科学数据因涉及专有、出口管制、保密或数据主权限制而无法集中存放,因此需要把模型移到数据所在处进行训练。论文综合美国能源部国家实验室、产业部署和开源社区的五项并行工作经验,提出将联邦人工智能从试点演示推进到多站点生产环境的结构化框架,涵盖数据架构、隐私与安全、信任与验证、治理以及运营等方面。论文还列出了内存效率、可靠性、同步等系统层面的经验,并提出异步联邦、泄露审计、验证标准和数据契约统一等待解决的问题。

Olivera Kotevska, Max Carlson, Yan Gao 等

arXiv cs.DC

Darpan: A Digital Twin Framework for the Next-Generation Computing Continuum

说明Darpan:面向下一代计算连续体的数字孪生框架

简介该论文提出名为Darpan的数字孪生框架,用于设备、边缘、雾与云构成的计算连续体。系统在物理侧运行真实应用并持续观测运行状态,在数字侧维护可执行的虚拟副本,用于从同一起点独立评估候选决策。被选中的决策需先在物理侧依据最新状态验证可行性,再实际执行。论文称,在真实DAG工作负载上,其预测响应时间的平均绝对误差为0.485秒,40节点时扩展效率为93.1%。

Zhiyu Wang, Rajkumar Buyya

arXiv cs.IT · cs.SY · eess.SY

Mission Efficiency Optimization in Low-Altitude Economy: Adaptive Power Allocation for Coordinating Heterogeneous Aircraft Swarms

说明低空经济中的任务效率优化:面向异构无人机集群协同的自适应功率分配

简介本文面向低空经济中多种异构低空飞行器协同执行任务的场景,将感知、通信、计算和执行分工构成的闭环视为协同系统。作者提出“作业能力熵”来量化各飞行器的有效作业能力,并结合信道条件,以最小化线性二次型调节器(LQR)代价作为任务效率指标建立功率分配问题。该问题被分解为两个凸子问题迭代求解,并给出闭式解。仿真结果表明,所提出的面向任务的自适应功率分配方案优于传统方法。

Jiarui Zhang, Wei Feng, Chao Dong 等

arXiv cs.DC

Exploring Adaptive Byzantine Quorum Systems to Improve Latency in the WAN

说明探索自适应拜占庭法定人数系统以降低广域网延迟

简介在拜占庭容错状态机复制中,法定人数系统要求一部分副本先投票,才能确定某个值。在广域网中,法定人数的大小与组成会影响副本推进速度,进而影响客户端感受到的延迟。本文在 BFT-SMaRt 中加入模块化的法定人数系统抽象,使多种法定人数构造可在同一框架内、与相同的优化技术配合运行,并通过网络模拟比较它们对广域网中客户端延迟的影响。

Linus Gnan, R\"udiger Kapitza, Christian Berger

arXiv cs.IT · cs.PF · math.IT

Distribution of Age of Information in the Erlang Loss System

说明Erlang 损失系统中信息年龄的分布

简介本文研究无缓冲的 M/M/c/c(Erlang 损失系统)中信息年龄(AoI)与峰值信息年龄(PAoI)的精确分布。泊松到达的更新在 c 个服务器满载时,可采用阻塞、随机抢占同源更新或抢占最陈旧更新三种策略。作者用吸收马尔可夫链方法得到矩阵指数形式的精确分布,并可扩展到多个信息源共享服务器的情形。

Nail Akar, Sennur Ulukus

arXiv cs.DC

Kirin: Cloud-native WebAssembly Service Orchestration

说明Kirin:面向云原生的 WebAssembly 服务编排器

简介本文提出 Kirin,一个用于云原生 WebAssembly 服务的编排器,支持资源调度、生命周期管理、扩缩容和请求路由等核心功能。作者将其与基于容器的部署方式进行了对比评估。结果显示,在服务生命周期管理方面表现较好;在 CPU 密集型负载上则存在已知局限,而对于典型服务负载,Kirin 表现具有竞争力。

Joshua Bauer, Sebastian Werner, Maria C. Borges

★★★★★ 值得关注
arXiv cs.GT

Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality

说明基于线性规划对偶的预算约束拍卖紧致流动性福利保证

简介本文研究预算受限竞拍者的拍卖效率,针对粗相关均衡推导紧致的无政府代价(PoA)界。作者提出一个通用框架,把证明PoA保证归结为求解一个线性规划的对偶可行解,并引入适用于预算约束环境的新平滑性概念。基于该框架,作者得到多种拍卖形式的紧致流动性福利保证,并为无预算的统一价格拍卖和广义第二价格拍卖给出新的下界。

看点提出基于LP对偶的通用框架和新的平滑性概念,给出多种拍卖形式的紧致PoA界,并匹配已知上界,理论贡献突出。

Twan Kroll, Guido Sch\"afer, Artem Tsikiridis

arXiv cs.IT · math.IT

Version Age-of-Information-based Semantic Secrecy Region Analysis

说明基于版本信息年龄的语义保密区域分析:研究无线状态更新系统中语义层面的保密性能,兼顾信息新鲜度与窃听防护。

简介本文在无线状态更新系统中研究语义保密问题,采用版本信息年龄(VAoI)衡量更新的信息价值,并用三节点窃听信道刻画信息更新与保密性之间的权衡。作者提出语义保密区域(SSR)的概念并从几何角度进行分析,通过二维马尔可夫链推导出目的节点平均VAoI及窃听者出现语义不对称概率的闭式表达式。在瑞利衰落信道下,论文刻画了最优SSR边界与功率分配,数值结果表明优化功率分配比固定功率方案明显扩大了保密区域。

Qian Wang, Bohai Li, Chao Sun 等

arXiv cs.IT · cs.SY · eess.SP

Federated Calibration of Motion Uncertainty for UAV Tracking in Multi-Operator ISAC Systems

说明多运营商综合感知与通信系统中用于无人机跟踪的运动不确定性联邦校准

简介本文研究多运营商综合感知与通信(ISAC)系统中的无人机跟踪问题,各运营商的原始感知数据、信道信息和发射决策保留在本地。作者提出双时间尺度框架:慢时间尺度上基于本地雷达新息校准各跟踪器对未建模运动的不确定性,在线阶段用协方差交叉(CI)融合各本地估计并进行预测波束成形。仿真显示,在运动模型失配较大时跟踪不确定性一致性有所改善,使用当前融合预测相比仅为通信设计的发射方案,RMSE约降低31%,额外功耗不足2%。

Qiming Li, Lei Zhang, Muhammad Ali Imran 等

arXiv cs.GT

The prospect of a fair outcome triggers prosocial behaviour in the Centipede Game

说明公平结果的前景会促使蜜蜈蚣博弈中的亲社会行为

简介该研究通过行为实验考察人们在蜈蚣博弈(ICG)这类顺序资源交换中的决策,比较了无收益截止(zero-end)与最后一步给出公平分配(fair-end)两种设计。结果显示,即便公平结果具有不确定性,也能促使参与者超越自利。进化模型表明,当参与者足够亲社会并采用概率策略时,公平分配会使博弈走向互利策略;第二轮重复进一步强化了合作倾向。

Marco Saponara, Ant\'onio M. Fernandes, Elias Fern\'andez Domingos 等

arXiv cs.DC

FissionReady: Joint Workload and Power Scheduling for Data Centers Powered by Small Modular Reactors

说明FissionReady:小型模块化反应堆供电数据中心的负载与电力联合调度

简介本文提出FissionReady,一种为小型模块化核反应堆(SMR)供电的数据中心调度器。它跟踪每个反应堆模块的燃料年限、氙状态和剩余灵活性,据此确定各模块的运行范围,并通过两时间尺度优化协调负载跟随、批处理任务延后和电网购电。文中报告,与同等规模的基准配置相比,该方法实现了零非自愿停机和零批处理截止期限错过,同时用水量约减少三分之一,电网成本约减半。

Raghavendra Kanakagiri, Rohan Basu Roy, Yankai Jiang 等

arXiv cs.IT · math.IT

Coded Computing for Dynamic System via Cartesian Products

说明基于笛卡尔积的动态系统编码计算

简介编码分布式计算通过编码组播缓解 Shuffle 通信瓶颈,但既有方案假设工作节点数量固定,难以适应节点加入与断开。本文提出一种动态编码分布式计算方案,保留存活节点的缓存与 Reduce 任务分配,并利用新加入集群带来的存储。文件放置采用各集群放置交付数组的笛卡尔积;贪心算法为被放弃的 Reduce 函数重新分配,通信数组使无 Reduce 函数的节点可作为编码发送方。文中给出任意可行断开情形下的精确通信负载,并在一次性通信与非编码放置假设下证明:无断开时,新集群到达的情形下与下界相差不超过两倍,否则不超过四倍。

Chenglin Li, Minquan Cheng, Youlong Wu

★★★★☆ 值得关注
arXiv cs.DC

Communication-Efficient (1+ǎrepsilon)Δ-Edge Coloring and Lovász Local Lemma

说明通信高效的 (1+ε)Δ 边着色与 Lovász 局部引理

简介本文研究双方边划分模型下的边着色问题:Alice 和 Bob 各持有部分边,需以较少通信共同给出正常着色。作者给出一个公共随机币的 Las Vegas 协议,对足够大的 Δ 用期望 O(ne^{-γΔ}+1) 比特和 O(log n/Δ+1) 期望轮数得到 (1+ε)Δ 边着色。此外,文中还提出一个双方构造性 Lovász 局部引理,并将其应用于若干经典问题。

看点提出新的随机着色过程并构造两方可通信高效的LLL,将颜色数降至(1+ε)Δ并显著减少通信;证明与协议设计较完整,适用于子领域。

Yi-Jun Chang, Nima Dolatabadi, Hung Thuan Nguyen

arXiv cs.IT · math.CO · math.IT

Multi-View Block Distance Distributions and Linear Programming Bounds for Locally Recoverable Codes with Availability

说明具有可用性的局部可恢复码:多视角块距离分布与线性规划界

简介本文针对可用性为任意固定值 a 的局部可恢复码,提出多视角线性规划框架。通过记录各块上的汉明距离,构造联合分布并施加计数恒等式、积-Krawtchouk 正性及碰撞不等式等约束,得到多项式规模的松弛。作者详细分析了 s=2、a=2 的四块情形,并给出精确有理原始-对偶证书,证明了 M_max(2,8,4,2,2,2)=8、M_max(3,7,3,2,2,2)=27 与 M_max(4,7,3,2,2,2)=64,且四块界严格强于两种粗化模型。

Ming-Hsuan Kang, Maosheng Xiong, Yu Hsuan Hsieh 等

arXiv cs.GT

Mechanism Design for Bridge Location with Optional Preferences

说明带可选偏好的桥梁选址机制设计

简介本文研究两个分隔区域各有一个预设设施、每位个体可选择其感兴趣设施子集的桥梁选址问题。个体成本分为最大、求和、最小三种形式,设计者需设计确定性的策略防操纵机制,选定连接桥位置,以近似最小化社会成本或最大成本。文中给出了各类成本下的最优机制、近似比及下界结果。

Xiaoshuang Geng, Wenjing Liu, Genjie Qin 等

★★★★☆ 值得关注
arXiv cs.DC · cs.PL

Vosti: Specifying, Implementing, and Verifying Deterministic LLM Inference

说明Vosti:确定性大模型推理的规范、实现与形式化验证

简介论文给出“确定性大模型推理”的形式化定义:在模型与部署配置固定时,相同提示和初始采样状态的请求,在不同执行方式下于对应输出位置产生逐位相同的 logits。作者测试发现 vLLM 批次不变模式和 SGLang 确定性模式在某些执行变化下会产生不同结果。为此提出推理引擎 Vosti,用 Verus 归纳证明调度与分页前缀共享 KV 缓存保持输出不变,并用 Triton 分析器证明所选内核在不同批次、查询长度和缓存布局下输出逐位相等。

看点提出形式化的确定性LLM推理规范,并用Verus归纳证明与Triton分析器分层验证调度与内核,超越现有批次不变模式的经验保证。

Jianxing Qin, Alexander Du, Danfeng Zhang 等

★★★★☆ 值得关注
arXiv cs.IT · math.IT

Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance

说明完全二分图的信息距离嵌入、格点不可嵌入性与信息距离的非欧幂次

简介本文将每个有限完全二分图的顶点在各尺度上编码为二进制串,使串间的信息距离以与尺度无关的常数误差逼近缩放后的图距离,并为每个顶点分配一个固定无限二进制序列。作者借此解决了Hutter关于有限完全二分图尺度嵌入的公开问题,并证明任何正幂次的信息距离都不能在实希尔伯特空间中被精确表示。此外,论文还证明整数格点的嵌入不存在,并对(R^m, ||·||_1)给出相同结论。

看点解决了Hutter提出的完全二分图嵌入与格点嵌入两个公开问题,给出信息距离幂的非欧几里得性结论,证明严格,理论意义突出。

Fengqi Hou

arXiv cs.IT · math.IT

Joint Source-Channel Coding of Gaussian Sources over Block Erasure Channels: Nonasymptotic Bounds and Channel-Uniform Normal Approximations

说明高斯源在块擦除信道上的联合信源信道编码:非渐近界与信道一致的正态近似

简介本文研究高斯无记忆信源在无记忆(可能非平稳)块擦除信道上、有限块长下的有损传输,采用超额均方失真准则。作者给出可计算的非渐近可达界与逆界,并建立相互匹配的三阶、信道一致的正态近似。数值结果将非渐近联合信源信道编码界及其共同的三阶近似,与经过优化的对称化分离信源信道编码可达基准进行比较。

Adeel Mahmood

arXiv cs.DC

Towards Efficient HPC Systems for Agents: Challenges and Opportunities

说明面向智能体的高效高性能计算系统:挑战与机遇

简介该论文关注编码智能体已成为高性能计算系统的真实用户,而现有的HPC抽象、接口和策略仍针对人工工作流设计。原文测量显示,使用编码智能体的用户占观测人群的19.5%,却占作业提交数的55.8%、CPU核心小时数的29.1%和GPU小时数的42.7%。作者主张设施应将智能体视为一等主体并进行协同设计,并概述了计算、存储、智能体记忆和安全方面的挑战与机遇。

Yunjia Zheng, Bintang Dwi Marthen, Zachary Pan 等

★★★★☆ 值得关注
arXiv cs.DC

Preserving Provenance in Shared KV Caches for LLM Serving

说明共享KV缓存中的来源保留:避免LLM服务中的错误复用

简介论文指出,大模型服务中本地前缀缓存会区分适配器、权重配置等来源信息,但共享KV缓存层只按token内容和粗粒度模型元数据建键,导致不同计算上下文的相同token可能被错误复用。作者在vLLM与SGLang多个版本、多种模型上进行实验,发现跨适配器冲突会使准确率从0.94降至0.64。论文提出“KV来源契约”,通过规范化描述符将来源信息绑定到查找与存储键中,并在三条缓存路径上实现,消除了不安全复用且保留了合法共享,命中路径的延迟变化在0.34毫秒以内。

看点论文首次系统研究共享KV缓存中的来源信息丢失问题,并提出可注入的来源契约,实验覆盖多个引擎与模型,证据较充分,对实际服务系统影响较大。

Wei Song, Yuxin Cao, Xi Zheng 等

★★★★☆ 值得关注
arXiv cs.GT

Efficiency of Generalized Proportional First-Price Auctions Under Auto-bidding

说明自动出价下广义比例一价拍卖的效率

简介本文研究在线广告中自动出价(广告主以投资回报率约束设定总体目标)情形下,比例一价拍卖的效率损失(无政府代价,PoA)。作者证明,两个竞标者时标准比例一价拍卖(r=1)的PoA至多为1.5,且这一上界是紧的;对于n个竞标者,取r=2n可达到2-1/(4n+1)的PoA,突破了确定性机制的2的界限。

看点证明双竞标者情形下比例一价拍卖PoA紧致为1.5并给出匹配下界,并首次突破任意n下的2障碍,理论贡献显著。

Yang Cai, Vineet Gupta, Yanchen Jiang 等

arXiv cs.NI · cs.DC

Enabling Efficient Client Selection in FL-as-a-Service for Multi-Application based Society 5.0

说明面向社会5.0多应用场景的FL即服务中高效客户端选择方法

简介本文研究物联网中的联邦学习即服务(FLaaS),即在不共享原始数据的前提下,跨应用协作训练模型。作者提出依据延迟、能耗和链路状态等参数挑选合适的客户端节点进行模型训练,并在人体活动识别数据集及模拟物联网网络环境中,与随机选择和基于Q学习的选择策略进行比较。文中报告延迟和能效有所改善,同时保持通信性能。

Prachi Nandi, Sonakshi Satpathy, Timam Ghosh 等

★★★★☆ 值得关注
arXiv cs.GT

Auctions with Price Predictions

说明带价格预测的拍卖:利用预测收益最大化统一价格的单品拍卖设计

简介论文研究单件无限供应商品的拍卖设计,拍卖方仅获得对收益最大化统一价格的一个预测,而非每位竞拍者的估值。作者刻画了任何普遍真实拍卖在一致性与稳健性之间可达到的帕累托前沿,并证明一种以预测价格发布与无先验后备拍卖之间随机选择的机制是帕累托最优的。论文还讨论了收入随预测精度平滑下降的扩展,并从历史市场数据学习预测的角度给出了端到端的分析。

看点提出仅依赖单一收益最大化价格预测的拍卖设计,刻画了一致性与鲁棒性的帕累托前沿,并给出从历史数据学习预测的理论框架,证明较为完整。

Muthu Sundar, Alec Sun, Siddharth Prasad 等

★★★★☆ 值得关注
arXiv cs.GT 有代码

Why Last-Iterate Scale-Invariant Regret Matching Converges Linearly?

说明为何尺度不变的遗憾匹配算法在末次迭代处线性收敛?

简介本文研究IREG-PRM+算法:它把累计遗憾向量按自身范数归一化,无需知道收益尺度即可达到最优遗憾,在零和矩阵博弈上末次迭代线性收敛。作者指出其机制是范数饱和,即遗憾范数升至有限极限,使步长冻结,并证明该现象在每个矩阵博弈上都会发生,从而使末次迭代的纳什间隙趋于零。在唯一的严格互补均衡附近,文章给出了闭式线性收敛速率,并提出可观测的范数增量比率证书。

看点该文首次解释无需调参的归一化遗憾匹配为何线性收敛,提出范数饱和机制并给出显式界与闭式速率,证据较充分,对该子领域影响较大。

Boning Li, Longbo Huang

★★★★☆ 值得关注
arXiv cs.IT · math.IT

An information identity reveals the geometry of deviation events

说明一个信息恒等式揭示偏差事件的几何结构

简介本文研究 n 个独立样本经验分布落入某集合这类偏差事件的概率指数。该指数在每个 n 下都分解为两个非负项:一项是速率,即 n 乘以典型样本分布相对于总体的相对熵;另一项是条件化引起的样本间依赖,用总相关度衡量。两项的相对大小取决于集合的几何性质,文章探讨了这种分解及其揭示的几何特征。

看点给出大偏差指数在速率项与总相关性之间的精确分解,揭示集合几何与依赖项的关系,理论上有新意,证明严格但适用范围偏理论。

Akshay Balsubramani

arXiv physics.optics · cs.IT · math.IT

Receiver-Informed Transmitter for 200Gbps C-Band Direct-Detection PON With FFE-Free ONU

说明面向200Gbps C波段直接检测无源光网络的接收端感知发射机

简介本文提出并以数值仿真验证了一种接收端感知发射机(RITX)波形设计方法,用于200 Gb/s PAM-4 C波段直接检测无源光网络。采用50 GHz光电器件,RITX可在免FFE的光网络单元(ONU)条件下达到N1/E1损耗等级,支持40公里传输距离。在1:64和1:128分光比下,全网络复杂度分别降低48.1%和66.7%。

Safiya Dabwan, Geraldo Gomes, Stylianos Sygletos

★★★★☆ 值得关注
arXiv cs.GT

The Price of Strategyproofness in Fair Multi-Resource Allocation for Cloud Computing

说明云计算多资源公平分配中防策略操纵的代价

简介本文研究云计算场景下,多种可分资源(Leontief效用)的公平且防策略操纵的分配问题。作者采用近期提出的公平比基准,提出自适应速度公平框架(ASF)与修正资源平衡机制(CRB),并给出了相应的近似比上界与下界。文中给出的主要结论包括:两种资源时,CRB机制可达到至多1+1/n的公平比,且渐近阶为1+Θ(1/n);m≥3时,满足共享激励与防策略操纵的确定性机制公平比恰为m。

看点提出自适应速度公平框架及修正资源平衡机制,将两资源公平比从1.268改进到渐近1+Θ(1/n),并给出匹配下界,证明严格且结果显著改进。

Yunpeng Lou, Junjie Luo

★★★★★ 值得关注
arXiv cs.GT

The Power of Simple Mechanisms: A Tight e-Approximation for Gains from Trade in Matching Markets

说明简单机制的力量:匹配市场中贸易收益的紧致 e 近似

简介本文研究简单机制在双边匹配市场中逼近贸易收益(GFT)的能力,买方估值与卖方成本相互独立,可行结果为任意向下封闭的匹配族。作者证明广义随机出价者机制(GRO,为 GSOM 与 GBOM 的等权混合)相对最优贸易收益的精确最坏情况近似比为 e,改进了此前 3.15 的界。论文还构造了满足正则分布、互不相交交易边及单一背包约束的市场,表明该界是紧的。

看点给出GRO机制在匹配市场中达到的精确最坏情况近似比e,并证明紧性,改进了此前3.15的保证,理论突破明显。

Xiaohui Bei, Wenhao Wu, Shengwei Zhou

arXiv cs.DC

Joint Effects of GPU Server Topology, Parallelism, and Congestion Control on MoE Inference: A Controlled Simulation Study

说明GPU服务器拓扑、并行方式与拥塞控制对MoE推理的联合影响:受控仿真研究

简介该论文使用ASTRA-sim与NS-3离散事件后端,在32个GPU rank的受控仿真中比较了MoE模型推理的通信与完成时间。研究覆盖6种服务器拓扑、4种TP/EP划分、2种TP集合通信算法和4种网络与拥塞控制模式,共768次确定性仿真。结果显示,暴露的通信开销占平均完成时间的89.9%至95.8%,拓扑、并行方式、集合通信实现和拥塞控制共同决定通信开销与完成时间。

Kaikai Yuan, Rui Xi, Yu Liu

arXiv cs.IT · cs.SY · eess.SP

Innovation-Based Sampling for New Information

说明基于新信息的创新采样:通过信息的方向与时机传递信息

简介该论文提出一种连续随机过程的创新采样方法:只有当过程相对于所有先前样本出现“足够新”的信息时才生成样本。针对维纳过程,论文刻画了创新的方向、时机与频率,并指出创新会越来越稀疏,采样率渐近趋于零。论文还研究了基于稀疏创新的远程估计,指出“没有创新”本身也携带信息,其最小均方误差估计能显著降低相对于传统零阶保持估计器的均方误差。

Jiping Luo, Anthony Ephremides, Nikolaos Pappas